P17163 [CEOI 2026] Birdwatchers

圣塞里夫观鸟者协会有着一个异常臃肿且不断变化的内部结构。协会由 $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$ 的整数。

### 样例说明 初始时，干事 $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 完成