Bit Operation Game

$N$ 頂点の根付き木が与えられる。 頂点には $0$ から $N-1$ の番号がついており、$0$番目の頂点が根を表す。 根には T = 0 が、それ以外の頂点には

• T=T&X
• T=T&Y
• T=T|X
• T=T|Y
• T=T^X
• T=T^Y

のいずれかの操作が書かれている。 ここでの演算子 &, |, ^ はそれぞれビット演算子 and, or, xor, を意味する。

A君とB君はこの木を使って以下のゲームを $M$ 回行った。 二人は根からスタートし、子頂点を選び進むという操作を、A君から始め葉に到達するまで交互に行う。 通ったノードに書かれている操作を、通った順に適用した時の、最終的な $T$ の値がスコアになる。 B君はできるだけスコアを小さくしたいと考えており、またA君は大きくしたいと考えている。 M回のゲームの $X$, $Y$ の値が与えられるので、二人が最適な選択をした時の各ゲームのスコアを出力せよ。

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

$N$ $M$

$o\_1$

$o\_2$

$...$

$o\_{N-1}$

$u\_1$ $v\_1$

$u\_2$ $v\_2$

$...$

$u\_{N-1}$ $v\_{N-1}$

$X\_1$ $Y\_1$

$X\_2$ $Y\_2$

$...$

$X\_M$ $Y\_M$

$1$ 行目には木の頂点数 $N$ と、行われるゲーム数を表す整数 $M$ が入力される。

$2$ 行目から $N$ 行目にかけて、$1$ ～ $N-1$ 番目の頂点に書かれている操作が入力される。

さらに続けて $N-1$ 行に、各辺により繋がれる $2$ 頂点の番号が入力される。

最後に $M$ 回のゲームにおける $X$, $Y$ の値が $M$ 行に渡り入力される。

各ゲームでの最終的な $T$ の値をそれぞれ $M$ 行に出力せよ。

• $1 \leq N \leq 100000$
• $1 \leq M \leq 100000$
• $0 \leq X, Y < 2^{16}$