You are given a tree containing $N$
nodes. The nodes are numbered from $1$
to $N$
. The root node of that tree is $R$
. Every node in that tree is associated with a value. Let, $X_u$
be the value associated with node $u$
.
You have to answer $Q$
queries. In each query, you will be given a pair of integers $(u, k)$
and you have to calculate the Bitwise AND of all the values of $k$
-th child in the subtree of node $u$
. If there is no $k$
-th child in subtree then the answer will be $-1$
.
First line of the Input will have a single integer $T$
($1 \leq T \leq 5$
) denoting the number of test cases.
The first line of every test case contains three integers $N$
($1 \leq N \leq 10^5$
), $Q$
($1 \leq Q \leq 10^5$
), $R$
($1 \leq R \leq N$
) representing the number of nodes in the tree, number of queries, and the root node of the tree respectively.
Next line will contain $N$
space-separated integers representing the values of $X_u$
($0 \leq X_u \leq 10^9$
).
Next $N-1$
lines will contain a pair of integers $(u, v)$
which denotes there is an edge between node $u$
and node $v$
. Here, ($1 \leq u, v \leq N$
).
Next $Q$
line will have a pair of integers $(u, k)$
representing each query. Here, ($1 \leq u \leq N$
) and ($0 \leq k \leq 10^5$
).
Subtask 1 (5 Points)
$1 \leq T \leq 5$
, $1 \leq N \leq 10^4$
, $1 \leq Q \leq 10^4$
, $0 \leq X_u \leq 10^9$
, $0 \leq k \leq10^5$
Subtask 2 (5 Points)
$1 \leq T \leq 5$
, $1 \leq N \leq 10^5$
, $1 \leq Q \leq 10^5$
, $0 \leq X_u \leq 10^9$
, $0 \leq k \leq 1$
Subtask 3 (90 Points)
Original constraints
For each query, you have to print the answer of that query in a new line.
Input | Output |
---|---|
1 8 6 1 3 23 5 6 15 11 14 10 1 2 2 4 4 8 3 5 3 6 3 7 3 2 2 2 3 1 4 2 1 2 1 3 1 1 | 10 10 -1 4 10 23 |
Here, 0-th child of node |