C. 【GENOIP#39】小K的外挂

题目描述

​ 小K是一个挂B，他很喜欢开挂，但是有一天，他的挂坏了，这让他很是头疼。

​ 小K在下飞行棋，棋盘是一行共 $n$ 个格子，编号依次为 $1\sim n$ 。小K有外挂，所以他会通过外挂来前进，他共有 $m$ 个外挂，第 $i$ 个外挂能让他从第 $l_i$ 格瞬移到第 $r_i$ 格，并花费 $1$ 的时间，并且小K很D，所以他不需要外挂就能往回走（即从第 $i$ 格走到第 $i-1$ 格，且往回走不需要时间）。

​ 但是小K的 rp 不太好，现在发生了 $q$ 次事件，每次事件中，小K的某一个挂会坏（这次事件结束后又会恢复），而你需要帮他求出此时他从 $s$ 走到 $t$ 要花费的最小时间。

输入格式

​ 第一行两个整数 $n,m$ ，表示格子数量和外挂数量。

​ 接下来 $m$ 行，每行两个整数 $l_i,r_i$ ，表示一个外挂。

​ 接下来一个整数 $q$ ，表示询问数量。

​ 接下来 $q$ 行，每行三个整数 $id,s,t$ ，表示第 $id$ 个挂坏了，你需要求出从 $s$ 走到 $t$ 所需的最小时间。

输出格式

​ 输出共 $q$ 行，每行一个整数表示最小时间，如果无法到达，输出 $-1$ 。

样例 1

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

-1
1
2

样例 2

10 6
1 3
2 2
2 4
3 8
5 7
6 10
5
1 1 2
3 1 4
4 2 8
6 2 8
5 2 9

-1
2
-1
2
3

数据范围与提示

​ 对于 $100\%$ 的数据，满足 $1\le n,m,q\le 2\times 10^5$ ， $1\leq l_i\leq r_i\leq n$ ， $1\leq s,t\leq n$ ， $1\leq id\leq m$ 。

sample