{"raw_statement":[{"iden":"statement","content":"给定一张包含 $n$ 个点、$m$ 条边的有向图，点标号从 $1$ 至 $n$，边标号从 $1$ 至 $m$。\n\n这张图的主人 Yazid 将先后执行 $Q$ 次操作，每个操作的形式为：在一个节点 $x$ 放置一个棋子，并设定一个整数 $s$，同时该棋子不停地沿着**编号最小**的出边移动，其中当第 $i$ 条边被经过 $w_i$ 次后就会立刻从图中被删除。棋子会不停移动直到**无出边可走**或**棋子已移动了 $s$ 步**。对于最终棋子停留的节点，我们把它叫做这次操作的**终点**。做完这些后，Yazid 会将该棋子移出游戏。\n\n你需要预测 Yazid 每次操作的终点编号。\n\n需要注意的是，所有操作都是有后效性的。也就是说，在前 $Q-1$ 步操作时**消失的边**、**经过的次数**都**不会**在第 $Q$ 次操作时被重置，即下一步操作在上一步操作基础上进行。"},{"iden":"input","content":"第一行两个用空格隔开的整数 $n,m$。\n\n接下来 $m$ 行描述有向图。这部分中第 $i$ 行（$1\\leq i\\leq m$）包含三个用空格隔开的整数 $u_i,v_i,w_i$，描述一条 $u_i$ 到 $v_i$ 的经过 $w_i$ 次会被删除的有向边。\n\n* 这里保证 $1\\leq u_i,v_i\\leq n$，$w_i\\leq 10^{18}$。\n\n接下来一行一个整数 $Q$。\n\n接下来 $Q$ 行依次描述各操作，每行两个用空格隔开的整数 $x,s$，描述一个操作。\n\n* 这里保证 $1\\leq x\\leq n$，$1\\leq s\\leq 10^{9}$。"},{"iden":"output","content":"输出 $Q$ 行，每行一个整数，依次输出各操作的终点。其中第 $i$ 行输出的是第 $i$ 个操作的终点。"},{"iden":"note","content":"**【样例解释 #1】**\n\n第一次操作，棋子的移动步骤如下：\n\n1. 在 $7$ 号节点放置一个棋子。\n2. $7$ 号节点编号最小的出边是第 $7$ 条边，棋子通过该边移动到 $5$ 号节点。\n3. $5$ 号节点编号最小的出边是第 $5$ 条边，棋子通过该边移动到 $2$ 号节点。\n4. $2$ 号节点编号最小的出边是第 $3$ 条边，棋子通过该边移动到 $3$ 号节点。\n5. $3$ 号节点编号最小的出边是第 $1$ 条边，棋子通过该边移动到 $1$ 号节点。\n6. $1$ 号节点编号最小的出边是第 $2$ 条边，棋子通过该边移动到 $2$ 号节点。\n7. $2$ 号节点编号最小的出边是第 $3$ 条边，棋子通过该边移动到 $3$ 号节点。此时，第 $3$ 条边已被经过了 $2$ 次，被从图中删去。\n8. $3$ 号节点编号最小的出边是第 $1$ 条边，棋子通过该边移动到 $1$ 号节点。\n9. 棋子停留在 $1$ 号节点，故 $1$ 号节点就是此次操作的终点。\n\n第二次操作，棋子的移动步骤如下：\n\n1. 在 $6$ 号节点放置一个棋子。\n2. $6$ 号节点编号最小的出边是第 $4$ 条边，棋子通过该边移动到 $3$ 号节点。此时，第 $4$ 条边已被经过了 $1$ 次，被从图中删去。\n3. $3$ 号节点编号最小的出边是第 $1$ 条边，棋子通过该边移动到 $1$ 号节点。此时，第 $1$ 条边已被经过了 $1$ 次，被从图中删去。\n4. 棋子已移动了 $7$ 步，故停留在 $1$ 号节点，$1$ 号节点是此次操作的终点。\n\n第三次操作，棋子的移动步骤如下：\n\n1. 在 $6$ 号节点放置一个棋子。\n2. $6$ 号节点已没有出边，故棋子只能停留在 $6$ 号节点，故 $6$ 号节点是此次操作的终点。\n\n**【子任务】**\n\n本题有多个子任务，每个子任务可能包含多个测试点，只有通过了一个子任务中的所有测试点才能得到该子任务的分数。\n\n每个子任务的测试点满足一些特殊的限制，具体如下表：\n\n \n\t\n\n|子任务编号|$n \\le$|$m \\le$|$Q \\le$|$s \\le$|$w \\le$|性质|分值|\n|----|----|----|----|----|----|----|----|\n|1|$10^5$|$1.5 \\times 10^5$|$5000$|$5000$|$10^{18}$|$0$|8|\n|2|$10^5$|$1.5 \\times 10^5$|$5000$|$10^9$|$5000$|$0$|8|\n|3|$10^5$|$1.5 \\times 10^5$|$10^5$|$10^9$|$10^{18}$|$1$|8|\n|4|$10^5$|$1.5 \\times 10^5$|$10^5$|$10^9$|$10^{18}$|$2$|$12$|\n|5|$10^5$|$n - 1$|$10^5$|$10^9$|$10^{18}$|$3$|13|\n|6|$10^5$|$n$|$10^5$|$10^9$|$10^{18}$|$4$|15|\n|7|$10^5$|$n + 50$|$10^5$|$10^9$|$10^{18}$|$5$|8|\n|8|$10^5$|$1.5 \\times 10^5$|$10^5$|$10^9$|$10^{18}$|$0$|28|\n \n\n对于所有测试点，保证 $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}$。\n\n- 性质 0：无特殊性质；\n- 性质 1：图为随机生成，每条边 $(u, v)$ 出现的概率为 $1 / n^2$；\n- 性质 2：保证 $w_i = 10^{18}$；\n- 性质 3：保证图构成了一棵有根树。\n- 性质 4：保证图构成了一棵环套树。\n- 性质 5：保证前 $n$ 条边构成了一棵环套树。"}],"translated_statement":null,"sample_group":[["7 8\n3 1 3\n1 2 5\n2 3 2\n6 3 1\n5 2 2\n4 2 1\n7 5 3\n2 2 2\n3\n7 7\n6 2\n6 2\n","1\n1\n6\n"],["见附件中的 2.in。","见附件中的 2.ans。"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}