给出一棵 $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，进行轮换操作。

输出格式

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

样例

输入 1

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

输出 1

10

说明 1

实际答案为

9 11 6 6 5 13

异或和为 10。

数据范围

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