题目描述

译自 ROIR 2016 Day1 T4. Поездка на каникулах

弗拉特兰的铁路是一条直线，沿线有 $n$ 个车站。我们将从某个车站到下一车站的铁路段称为区间。

一列火车从车站 $1$ 开往车站 $n$，在每站都会停靠。火车共有 $k$ 个座位，编号从 $1$ 到 $k$。火车票以三个数字描述：$s, t, a$，表示从车站 $s$ 到车站 $t$ 的座位 $a$。

瓦西计划在暑假的某一天乘坐火车从一个车站到另一个车站。他了解到在那天已经有 $m$ 张票售出，可能在感兴趣的车站区间内已经没有空余座位。只有在所选座位在起点到终点的所有区间内都空闲时，才能购买从一个车站到另一个车站的特定座位的票。

瓦西意识到，有时仍然可以通过购买多张票并在某些中间车站换座位的方式从一个车站到另一个车站。由于换座位不方便，他希望购买最少数量的票，确保在每个区间都有自己的座位。

瓦西尚未决定从哪个车站到哪个车站旅行。他列出了 $q$ 个旅行方案，对于每个方案，他想知道如果选择该方案，需要购买的最少票数是多少。

你的任务是编写一个程序，根据已售出的票信息和瓦西的旅行方案，确定每个方案所需购买的最少票数。

输入格式

输入文件的第一行包含三个整数 $n, m, k$ $(2 \leq n \leq 200000, 0 \leq m \leq 200000, 1 \leq k \leq 200000)$，分别表示车站数量、已售票数量和火车座位数量。

接下来的 $m$ 行包含已售票信息，每行包含三个整数 $s_i, t_i, a_i$ $(1 \leq s_i < t_i \leq n, 1 \leq a_i \leq k)$，表示从车站 $s_i$ 到车站 $t_i$ 的座位 $a_i$。保证在任何区间内，任何座位上最多只有一张票。

再下一行包含一个整数 $q$ $(1 \leq q \leq 200000)$。接下来的 $q$ 行描述瓦西的旅行方案，每行包含两个整数 $f_j, d_j$ $(1 \leq f_j < d_j \leq n)$，表示瓦西在该方案中希望从车站 $f_j$ 到车站 $d_j$。

输出格式

输出文件应包含 $q$ 个整数：对于每个旅行方案，输出瓦西需要购买的最少票数以完成相应旅行。如果无法完成旅行，则对于该方案输出 $-1$。

5 4 3
1 4 1
2 5 3
2 3 2
4 5 2
3
1 5
3 5
4 5

-1
2
1

在从车站 $2$ 到车站 $3$ 的区间内，所有座位都被占用，因此无法从车站 $1$ 到车站 $5$ 旅行。从车站 $3$ 到车站 $5$ 可以用两张票完成旅行：从车站 $3$ 到车站 $4$ 使用座位 $2$，从车站 $4$ 到车站 $5$ 使用座位 $1$。从车站 $4$ 到车站 $5$ 可以用一张票完成旅行，使用座位 $1$。

数据范围与提示

详细子任务附加限制及分值如下表所示：