$n$ 個の頂点を持つ木が与えられる。この木は以下の性質を満たす。

1. すべての葉の深さは等しい。
2. 頂点番号は BFS 順に割り振られている。構築方法は以下の通りである。
   1. 根を頂点 1 とし、1 をキューに入れる。
   2. キューの先頭を取り出し、その子に順次未使用の番号を割り当て、番号順にキューに入れる。

各頂点は重みを持ち、初期値は 0 である。

以下の 2 種類の操作が与えられる。

• 操作 1：頂点 $x$ を根とする部分木に含まれるすべての頂点の重みに $y$ を加算する。
• 操作 2：頂点の重みを巡回シフトする。頂点 $i$ の重みを $(i \bmod n) + 1$ の位置へ移動させる。

$q$ 回の操作後の各頂点の重みを求めよ。出力が大きくなるのを避けるため、各頂点の重みの XOR 合計を出力せよ。

入力

1 行目に $n$ と $q$ が与えられる。これらは木のサイズと操作回数を表す。

続く 1 行に $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（巡回シフト）を行う。

出力

すべての頂点の重みの XOR 合計を 1 行で出力せよ。

入出力例

入力 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

注記

実際の各頂点の重みは以下の通りである。

9 11 6 6 5 13

これの XOR 合計は 10 である。

制約

すべてのデータにおいて、$n, Q \leq 100\,000$、$y \leq 10\,000$ を満たす。