题目描述

圣塞里夫观鸟者协会有着一个异常臃肿且不断变化的内部结构。协会由 $n$ 个分会组成，每名协会成员都恰好属于其中一个分会。各分会依次编号为 $1$ 至 $n$，其中第 $i$ 个分会有 $m_i$ 名成员。因此，协会共有 $M=m_1+m_2+\cdots+m_n$ 名成员。

每个分会均由本分会的一名成员领导，该成员在这一职务下称为分会的干事。干事的编号与分会编号相同，因此对于每个 $i=1,\ldots,n$，编号为 $i$ 的干事负责第 $i$ 个分会。

此外，所有干事通过导师制度形成层级结构：除一人外，每名干事都有一位导师，其导师是另一个分会的干事。唯一没有导师的干事是协会主席。若干事 $a$ 是干事 $b$ 的导师，我们也称干事 $b$ 是干事 $a$ 的门生。任何干事都不能直接或间接成为自己的导师；因此，从一名干事开始，依次沿着其导师、导师的导师等关系不断向上追溯，最终一定会到达主席。

我们将一名干事的影响力定义为：其所在分会的成员数，加上其所有门生的影响力之和（若其有门生）。不难看出，影响力最大的干事是主席，其影响力始终等于 $M$。若一名干事的影响力满足 $\ge M/2$，则称其为资深干事。

协会章程规定，在所有资深干事中，影响力最小者应担任协会的财务主管。

有时，一名干事（主席除外）可以改变归属，从此不再是原导师的门生，而改为另一位导师的门生（前提是新导师不是其门生、门生的门生，依此类推）。因此，部分干事的影响力可能发生变化，财务主管一职也可能转由另一名干事担任。

任务

编写一个程序，读入协会的初始状态以及一系列归属变更。程序必须输出协会初始状态下的财务主管，并在每次归属变更后输出当时的财务主管。

输入格式

第一行包含两个以空格分隔的整数 $n$ 和 $q$；$n$ 表示分会数量，$q$ 表示归属变更次数。

接下来的 $n$ 行描述协会的初始状态。其中第 $i$ 行包含两个以空格分隔的整数 $s_i$ 和 $m_i$；$s_i$ 表示干事 $i$（即负责第 $i$ 个分会的干事）的导师，$m_i$ 表示第 $i$ 个分会的成员数。$s_i=0$ 表示干事 $i$ 是协会主席，因此没有导师。

余下的 $q$ 行描述归属变更。其中第 $j$ 行包含两个以空格分隔的整数 $\hat{x}_j$ 和 $\hat{z}_j$。这些整数的含义如下。以 $t_j$（$j=0,\ldots,q$）表示前 $j$ 次归属变更后的财务主管（因此，$t_0$ 表示第一次归属变更前的初始财务主管）。第 $j$ 次归属变更为：干事 $z_j$ 成为干事 $x_j$ 的新导师，其中 $x_j=1+((t_{j-1}+\hat{x}_j)\bmod n)$，$z_j=1+((t_{j-1}+\hat{z}_j)\bmod n)$。采用这种方式表示 $x_j$ 和 $z_j$，是为了强制程序按照输入中归属变更出现的顺序依次处理。

输入数据中的归属变更始终合法，即 $z_j$ 不会等于 $x_j$，也不会是 $x_j$ 的门生、门生的门生，依此类推。不过，在第 $j$ 次变更之前，$z_j$ 可能已经是 $x_j$ 的导师（此时该次操作实际上不会产生任何变化）。

请注意，如果程序在某一时刻计算出了错误的 $t_j$，那么它也会错误地解码后续输入 $\hat{x}_{j+1}$、$\hat{z}_{j+1}$ 等，并且可能得到运行时错误（RTE）而非答案错误（WA）的评测结果。这是因为错误解码后的输入可能并不合法，例如，程序可能错误地得到一个作为 $x_{j+1}$ 门生的 $z_{j+1}$。

输出格式

依次输出 $t_0,t_1,\ldots,t_q$，每个数单独占一行，其中 $t_j$ 表示前 $j$ 次归属变更后的财务主管。显然，每个 $t_j$ 都必须是满足 $1\le t_j\le n$ 的整数。

7 2
0 1
1 3
1 3
2 3
2 1
5 2
5 1
3 7
2 7

2
2
3

提示

样例说明

初始时，干事 $2$ 是财务主管（因此 $t_0=2$）。第一次归属变更中，读入 $\hat{x}_1=3$ 和 $\hat{z}_1=7$，并计算出 $x_1=1+((2+3)\bmod 7)=6$、$z_1=1+((2+7)\bmod 7)=3$；因此，干事 $3$ 成为干事 $6$ 的新导师，干事 $2$ 仍然是财务主管（因此 $t_1=2$）。第二次归属变更中，读入 $\hat{x}_2=2$ 和 $\hat{z}_2=7$，并计算出 $x_2=1+((2+2)\bmod 7)=5$、$z_2=1+((2+7)\bmod 7)=3$；因此，干事 $3$ 成为干事 $5$ 的新导师，同时也成为新的财务主管（因此 $t_2=3$）。

限制条件

• $1\le n\le 1\,000\,000$
• $1\le q\le 30\,000$
• 对每个 $i=1,\ldots,n$，均有 $1\le m_i$
• $m_1+m_2+\cdots+m_n\le 10^9$
• 对每个 $j=1,\ldots,q$，均有 $1\le\hat{x}_j\le n$ 且 $1\le\hat{z}_j\le n$。

子任务

• 子任务 $1$（$15$ 分）：$n\le 100$
• 子任务 $2$（$10$ 分）：$n\le 1000$
• 子任务 $3$（$50$ 分）：$n\le 300\,000$
• 子任务 $4$（$25$ 分）：无额外限制。

翻译由 ChatGPT-5.6 完成