비트 연산 게임

$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$이 주어진다.

둘째 줄부터 $N$번째 줄까지 $1$번부터 $N-1$번 정점에 적힌 연산이 주어진다.

이어서 $N-1$개의 줄에 간선으로 연결된 두 정점 번호 $u_i$와 $v_i$가 주어진다.

마지막으로 $M$개의 줄에 각 게임의 $X_i$와 $Y_i$가 주어진다.

각 게임의 최종 $T$ 값을 $M$개의 줄에 출력하라.

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