XOR과 집합과 트리와 쿼리

양의 정수를 원소로 갖는 유한집합 $S$에 대해, $f(S)$를 아래 조건을 모두 만족하는 유한집합 중 크기가 가장 작은 집합으로 정의한다. 이런 집합은 하나만 존재한다.

• $S \subseteq f(S)$이다.
• 임의의 양의 정수 $x, y$에 대해 $x, y \in f(S)$이고 $x \neq y$이면 $x \oplus y \in f(S)$이다. 여기서 $\oplus$는 비트 단위 XOR 연산이다.
• 임의의 양의 정수 $x$에 대해 $x \in f(S)$이고 $x < 2^{1000}$이면 $2x \in f(S)$이다.
• 임의의 양의 정수 $x$에 대해 $2x \in f(S)$이고 $x < 2^{1000}$이면 $x \in f(S)$이다.

정점이 $N$개인 트리가 있다. 모든 $i$ ($1 \le i \le N$)에 대해 $i$번 정점에는 양의 정수 $A_i$가 적혀 있다. 이때 $Q$개의 쿼리를 처리해야 한다.

쿼리 $u, v$에 대해, $u$번 정점에서 $v$번 정점까지의 최단 경로에 포함되는 정점들의 집합을 $P$라고 하자. 이때 집합 $f(\{A_r \mid r \in P\})$의 원소 중 최솟값을 출력해야 한다.

첫 줄에 정점의 개수 $N$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다.

둘째 줄에는 각 정점에 적힌 양의 정수 $A_1, A_2, \ldots, A_N$이 공백으로 구분되어 주어진다.

셋째 줄부터 $N - 1$개의 줄에는 트리의 간선이 연결하는 두 정점의 번호 $a$, $b$가 공백으로 구분되어 주어진다.

$N + 2$번째 줄부터 $Q$개의 줄에는 쿼리를 나타내는 두 정수 $u$, $v$가 공백으로 구분되어 주어진다.

각 쿼리의 답을 한 줄에 하나씩, 총 $Q$개의 줄에 출력한다.

• $1 \le N, Q \le 100{,}000$
• $0 < A_i < 2^{30}$ ($1 \le i \le N$)
• 모든 쿼리에서 $1 \le u, v \le N$