给出一棵 $n$ 个点的树，满足以下性质：
- 每个叶子的深度都相同
- 树的编号按照 BFS 序标号，构造方法具体如下：
- 设根节点为标号1，将1加入队列
- 每次取出队列头，将其儿子依次设为下一个未使用的标号，并按标号顺序加入队列
每个点都有一个权值，初始为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$
| 子任务编号 | $n,Q \leq$ | 特殊性质 | 分值 |
|---|---|---|---|
| 1 | $1\,000$ | $ $ | 21 |
| 2 | $100\,000$ | 只有操作1 | 8 |
| 3 | $fa[i+1]=i$ | 8 | |
| 4 | 给出的是一棵完全二叉树，$n=2^k-1$ | 13 | |
| 5 | 叶子个数 $\leq 20$ | 13 | |
| 6 | $50\,000$ | $ $ | 21 |
| 7 | $100\,000$ | 16 |