给出一棵 $n$ 个点的树，满足以下性质：

1. 每个叶子的深度都相同
2. 树的编号按照 BFS 序标号，构造方法具体如下：
   1. 设根节点为标号1，将1加入队列
   2. 每次取出队列头，将其儿子依次设为下一个未使用的标号，并按标号顺序加入队列

每个点都有一个权值，初始为0

给出两种操作：

• 操作 1：对点 $x$ 所在子树内的每个点加 $y$
• 操作 2：进行点权的轮换，将点 $i$ 的权值移动到$(i\bmod n)+1$处

求 $q$ 次操作后每个点的权值，为避免输出过大，请输出每个点权值的异或和

输入格式

第一行两个数 $n$ 与 $q$，表示树的大小以及操作次数

接下来一行 $n-1$ 个数，第 $i$ 个数$fa[i+1]$表示点$i+1$的父亲节点（根据 BFS 的性质，当 $i \leq j$ 时有 $fa[i] \leq fa[j]$）

之后 $q$ 行，分别表示每次操作，若为 1 x y 则表示操作 1，对子树 $x$ 的点加 $y$；若为 2 则表示操作 2，进行轮换操作

输出格式

一行一个数，表示所有点权的异或和

样例输入

6 10
1 1 2 3 3
1 3 1
1 2 2
2
1 4 3
1 5 4
2
2
1 1 5
2
1 6 6

样例输出

10

样例解释

实际答案为

9 11 6 6 5 13

异或和为10

数据范围

对于$100%$的数据：$n,Q \leq 100\,000$，$y \leq 10\,000$