P11554 [ROIR 2016] 假期旅行 (Day 1)

翻译自 [ROIR 2016 D1T4](https://neerc.ifmo.ru/school/archive/2015-2016/ru-olymp-regional-2016-day1.pdf)。

某地铁路是一条直线，沿线有 $n$ 个车站。我们称从某个车站到下一个车站之间的路段为一个区段。 一列火车从车站 $1$ 开始，最终到达车站 $n$，在每个车站都会停靠。火车上有 $k$ 个座位，座位编号从 $1$ 到 $k$。每张火车票上由三个数字 $s, t, a$，表示持有这张票的乘客允许从车站 $s$ 到车站 $t$，坐在编号为 $a$ 的座位上。 暑假的一天，Vasya 计划乘坐火车从一个车站到另一个车站。他发现当天已经售出了 $m$ 张票，并且可能在他感兴趣的车站之间已经没有空座位。直接从某个车站到另一个车站的票只能在每个区段的对应座位都空闲时购买。 Vasya 想到，有时即便如此，他仍然可以通过购买几张票，在某些中途车站换座位再继续乘坐。因此，他希望购买最少的票数，让他在每个区段都有座位。 Vasya 还没有完全确定下来要从哪个车站出发，也没有决定最终到达哪个车站。他记录了 $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$，表示一张已售出的票的起始车站 $s_i$，目的车站 $t_i$ 和座位号 $a_i$ （$1 \leq s_i < t_i \leq n$，$1 \leq a_i \leq k$）。保证在任意区段，每个座位最多只被一张票占用。 接下来一行输入一个整数 $q$，表示查询的数量（$1 \leq q \leq 200000$）。 接下来 $q$ 行，每行输入两个整数 $f_j,d_j$（$1 \leq f_j < d_j \leq n$），分别表示 Vasya 想要出发的车站和目的地车站。

输出共 $q$ 行。对于每个查询，输出 Vasya 完成这次旅行所需的最少票数。如果无法完成旅行，输出 `-1`。

### 样例解释 - 在车站 $2$ 到车站 $3$ 的区段，所有座位都已经被占用，因此从车站 $1$ 到车站 $5$ 的旅程无法进行。 - 从车站 $3$ 到车站 $5$，需要购买两张票：从车站 $3$ 到车站 $4$ 坐座位 $2$，从车站 $4$ 到车站 $5$ 坐座位 $1$。 - 从车站 $4$ 到车站 $5$ 只需要一张座位 $1$ 的票。 ### 数据范围 | 子任务 | 是否捆绑 | 分值 | $n,m,k\le$ | $q\le$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | 是 | $33$ | $100$ | $1$ | | $2$ | 是 | $30$ | $200000$ | $1$ | | $3$ | 是 | $37$ | $200000$ | $200000$ |