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

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

各頂点には重みが設定されており、初期値はすべて 0 である。

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

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

$q$ 回の操作後の各頂点の重みを求めよ。出力が大きくなることを避けるため、すべての頂点の重みの排他的論理和（XOR）を出力せよ。

制約

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

入力形式

入力は以下の形式で標準入力から与えられる。

$n$ $q$ $fa[2]$ $fa[3]$ $\dots$ $fa[n]$ 操作 1 $\vdots$ 操作 $q$

$fa[i+1]$ は頂点 $i+1$ の親を表す（BFS の性質により、$i \leq j$ ならば $fa[i] \leq fa[j]$ が成り立つ）。 各操作は以下のいずれかの形式である。

1 x y：操作 1 を行う。 2：操作 2 を行う。

出力形式

すべての頂点の重みの排他的論理和を 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

これらの排他的論理和は 10 となる。