給出一棵 $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$。