Cow Land は牛のための特別な遊園地です。歩き回り、おいしい草を食べ、さまざまな牛用アトラクションを楽しめます（牛用ジェットコースターは特に人気です）。

異なるアトラクションが $N$ 個あります（$2 \leq N \leq 10^5$）。一部の対は道で結ばれ、道は全部で $N-1$ 本です。どの二つの間にも、これらの道からなる経路が一意に存在します。各アトラクション $i$ の楽しさは整数 $e_i$ で、朝に魅力的なものも午後遅くに魅力的なものもあるため、一日の間に変化し得ます。

$i$ から $j$ へ行く牛は、$i$ から $j$ の経路上のすべてを体験します。不思議なことに経路全体の楽しさは、端点 $i$ と $j$ を含む経路上の楽しさすべてのビット単位 XOR です。

次の Cow Land 訪問で牛たちが通る予定の経路の楽しさを求めてください。

入力

入力の最初の行は $N$ とクエリ数 $Q$（$1 \leq Q \leq 10^5$）です。次の行は $e_1 \ldots e_N$（$0 \leq e_i \leq 10^9$）です。続く $N-1$ 行は二つの整数 ID $a$、$b$（ともに $1 \ldots N$ の範囲）で道を表します。最後の $Q$ 行は $e_i$ の更新または経路の楽しさのクエリです。「1 $i$ $v$」は $e_i$ を $v$ に更新し、「2 $i$ $j$」は $i$ と $j$ を結ぶ経路の楽しさを問い合わせます。

得点の最大 50% に相当するテストデータでは、アトラクションの値は変化しません。

出力

「2 $i$ $j$」形式の各クエリについて、$i$ から $j$ の経路の楽しさを一行に出力してください。

入出力例

入力 1

5 5
1 2 4 8 16
1 2
1 3
3 4
3 5
2 1 5
1 1 16
2 3 5
2 1 5
2 1 3

出力 1

21
20
4
20

問題作成者：Charles Bailey