题目描述

给定一张包含 $n$ 个点、$m$ 条边的有向图，点标号从 $1$ 至 $n$，边标号从 $1$ 至 $m$。

这张图的主人 Yazid 将先后执行 $Q$ 次操作，每个操作的形式为：在一个节点 $x$ 放置一个棋子，并设定一个整数 $s$，同时该棋子不停地沿着编号最小的出边移动，其中当第 $i$ 条边被经过 $w_i$ 次后就会立刻从图中被删除。棋子会不停移动直到无出边可走或棋子已移动了 $s$ 步。对于最终棋子停留的节点，我们把它叫做这次操作的终点。做完这些后，Yazid 会将该棋子移出游戏。

你需要预测 Yazid 每次操作的终点编号。

需要注意的是，所有操作都是有后效性的。也就是说，在前 $Q-1$ 步操作时消失的边、经过的次数都不会在第 $Q$ 次操作时被重置，即下一步操作在上一步操作基础上进行。

输入格式

第一行两个用空格隔开的整数 $n,m$。

接下来 $m$ 行描述有向图。这部分中第 $i$ 行（$1\leq i\leq m$）包含三个用空格隔开的整数 $u_i,v_i,w_i$，描述一条 $u_i$ 到 $v_i$ 的经过 $w_i$ 次会被删除的有向边。

• 这里保证 $1\leq u_i,v_i\leq n$，$w_i\leq 10^{18}$。

接下来一行一个整数 $Q$。

接下来 $Q$ 行依次描述各操作，每行两个用空格隔开的整数 $x,s$，描述一个操作。

• 这里保证 $1\leq x\leq n$，$1\leq s\leq 10^{9}$。

输出格式

输出 $Q$ 行，每行一个整数，依次输出各操作的终点。其中第 $i$ 行输出的是第 $i$ 个操作的终点。

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

1
1
6

见附件中的 2.in。

见附件中的 2.ans。

提示

【样例解释 #1】

第一次操作，棋子的移动步骤如下：

1. 在 $7$ 号节点放置一个棋子。
2. $7$ 号节点编号最小的出边是第 $7$ 条边，棋子通过该边移动到 $5$ 号节点。
3. $5$ 号节点编号最小的出边是第 $5$ 条边，棋子通过该边移动到 $2$ 号节点。
4. $2$ 号节点编号最小的出边是第 $3$ 条边，棋子通过该边移动到 $3$ 号节点。
5. $3$ 号节点编号最小的出边是第 $1$ 条边，棋子通过该边移动到 $1$ 号节点。
6. $1$ 号节点编号最小的出边是第 $2$ 条边，棋子通过该边移动到 $2$ 号节点。
7. $2$ 号节点编号最小的出边是第 $3$ 条边，棋子通过该边移动到 $3$ 号节点。此时，第 $3$ 条边已被经过了 $2$ 次，被从图中删去。
8. $3$ 号节点编号最小的出边是第 $1$ 条边，棋子通过该边移动到 $1$ 号节点。
9. 棋子停留在 $1$ 号节点，故 $1$ 号节点就是此次操作的终点。

第二次操作，棋子的移动步骤如下：

1. 在 $6$ 号节点放置一个棋子。
2. $6$ 号节点编号最小的出边是第 $4$ 条边，棋子通过该边移动到 $3$ 号节点。此时，第 $4$ 条边已被经过了 $1$ 次，被从图中删去。
3. $3$ 号节点编号最小的出边是第 $1$ 条边，棋子通过该边移动到 $1$ 号节点。此时，第 $1$ 条边已被经过了 $1$ 次，被从图中删去。
4. 棋子已移动了 $7$ 步，故停留在 $1$ 号节点，$1$ 号节点是此次操作的终点。

第三次操作，棋子的移动步骤如下：

1. 在 $6$ 号节点放置一个棋子。
2. $6$ 号节点已没有出边，故棋子只能停留在 $6$ 号节点，故 $6$ 号节点是此次操作的终点。

【子任务】

本题有多个子任务，每个子任务可能包含多个测试点，只有通过了一个子任务中的所有测试点才能得到该子任务的分数。

每个子任务的测试点满足一些特殊的限制，具体如下表：

子任务编号	$n \le$	$m \le$	$Q \le$	$s \le$	$w \le$	性质	分值
1	$10^5$	$1.5 \times 10^5$	$5000$	$5000$	$10^{18}$	$0$	8
2				$10^9$	$5000$
3			$10^5$		$10^{18}$	$1$
4						$2$	$12$
5		$n - 1$				$3$	13
6		$n$				$4$	15
7		$n + 50$				$5$	8
8		$1.5 \times 10^5$				$0$	28

对于所有测试点，保证 $1 \leq n\leq 10^5$，$1 \leq m\leq 1.5\times 10^5$，$1 \leq Q \leq 10^5$，$1 \leq s \leq 10^9$，$1 \leq w_i \leq 10^{18}$。

• 性质 0：无特殊性质；
• 性质 1：图为随机生成，每条边 $(u, v)$ 出现的概率为 $1 / n^2$；
• 性质 2：保证 $w_i = 10^{18}$；
• 性质 3：保证图构成了一棵有根树。
• 性质 4：保证图构成了一棵环套树。
• 性质 5：保证前 $n$ 条边构成了一棵环套树。