Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:1024 MB
Statistics

文件名:cheat

题目描述

小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$。

样例一

input

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

output

-1
1
2

样例二

input

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

output

-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$。

子任务编号 分值 $n,m\le$ $q\leq$ 特殊性质
$1$ 5 $1000$ $10$
$2$ 15 $1000$ $2\times 10^5$
$3$ 20 $2\times 10^5$ $20$
$4$ 20 $2\times 10^5$ $2\times 10^5$ $r_i-l_i<=5$
$5$ 40 $2\times 10^5$ $2\times 10^5$