题目描述

圣塞里夫观鸟协会的内部结构十分庞大，并且会不断发生变化。

协会共有 $n$ 个分会，每名成员恰好属于一个分会。分会编号为 $1,2,\ldots,n$，第 $i$ 个分会有 $m_i$ 名成员，因此协会的成员总数为

$$M=m_1+m_2+\cdots+m_n.$$

每个分会由该分会的一名成员领导，这名成员称为该分会的秘书。秘书的编号与分会编号相同，即秘书 $i$ 负责第 $i$ 个分会。

所有秘书通过“导师关系”组成一棵有根树：

• 除一人外，每名秘书都有一名导师，导师也是某个分会的秘书；
• 唯一没有导师的秘书称为协会的主席；
• 若秘书 $a$ 是秘书 $b$ 的导师，则称秘书 $b$ 是秘书 $a$ 的直接下属；
• 不存在任何秘书直接或间接成为自己的导师。

因此，从任意秘书开始不断沿导师关系向上走，最终都会到达主席。

一名秘书的影响力定义为：其所在分会的成员数，加上其所有直接下属的影响力之和。等价地，秘书 $i$ 的影响力就是以 $i$ 为根的子树中所有分会的成员总数。

主席的影响力始终为 $M$。若一名秘书的影响力满足

$$\operatorname{influence}(i)\ge \frac M2,$$

则称其为高级秘书。

协会章程规定：在所有高级秘书中，影响力最小的那一名担任协会的财务主管。

有时，一名非主席秘书会更换导师。设秘书 $x$ 原本是秘书 $y$ 的直接下属，现在将其整棵子树从 $y$ 处断开，并把秘书 $x$ 改为秘书 $z$ 的直接下属。为了保证结构仍是一棵树，$z$ 不能等于 $x$，也不能位于 $x$ 的子树中。

每次更换导师后，一些秘书的影响力可能发生变化，财务主管也可能随之改变。

任务

给定协会的初始结构以及 $q$ 次更换导师操作，请输出初始状态下的财务主管，并在每次操作后再次输出当前的财务主管。

输入格式

第一行包含两个整数 $n,q$，分别表示分会数量和更换导师操作的次数。

接下来 $n$ 行描述协会的初始状态。第 $i$ 行包含两个整数 $s_i,m_i$：

• $s_i$ 表示秘书 $i$ 的导师；
• $m_i$ 表示第 $i$ 个分会的成员数；
• 若 $s_i=0$，则秘书 $i$ 是主席，没有导师。

接下来 $q$ 行描述操作。第 $j$ 行包含两个整数 $\hat x_j,\hat z_j$。

设 $t_j$ 表示完成前 $j$ 次操作后担任财务主管的秘书编号，其中 $t_0$ 表示初始状态下的答案。第 $j$ 次操作中的真实编号为

$$x_j=1+\bigl((t_{j-1}+\hat x_j)\bmod n\bigr),$$ $$z_j=1+\bigl((t_{j-1}+\hat z_j)\bmod n\bigr).$$

随后，把秘书 $x_j$ 的导师改为秘书 $z_j$。

这种编码方式保证你必须按输入顺序处理所有操作。

所有操作均保证合法：

• $z_j\ne x_j$；
• $z_j$ 不在 $x_j$ 的子树中；
• 允许 $z_j$ 原本就是 $x_j$ 的导师，此时树的结构实际上不会改变。

注意：若程序在某一步求错了 $t_j$，之后会错误解码操作，甚至可能得到非法操作并导致运行时错误，而不一定只是答案错误。

输出格式

输出 $q+1$ 行，依次为

$$t_0,t_1,\ldots,t_q,$$

其中 $t_j$ 表示完成前 $j$ 次操作后的财务主管编号。

数据范围

• $1\le n\le 1\,000\,000$；
• $1\le q\le 30\,000$；
• 对所有 $i$，$m_i\ge 1$；
• $m_1+m_2+\cdots+m_n\le 10^9$；
• 对所有 $j$，$1\le \hat x_j,\hat z_j\le n$。

子任务

子任务	分值	附加限制
1	15	$n\le 100$
2	10	$n\le 1000$
3	50	$n\le 300\,000$
4	25	无附加限制

样例

输入

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

于是秘书 $6$ 的导师改为秘书 $3$。操作后秘书 $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.$$

于是秘书 $5$ 的导师改为秘书 $3$，秘书 $3$ 成为新的财务主管，即 $t_2=3$。