Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Simple And

By fire_tornado · Limits 2s, 512 MB

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$.

Input

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 Constraints

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

Output

For each query, you have to print the answer of that query in a new line.

Sample

InputOutput
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 $2$ is ${2}$. 1st children of node $2$ are ${3, 4}$. 2nd children of node $2$ are ${5, 6, 7, 8}$. And there is no 3rd child of node $2$.

    Discussion

    Statistics


    60% Solution Ratio

    DibyaJyotiEarliest, 3w ago

    Shahwat_Has9Fastest, 0.4s

    Shahwat_Has9Lightest, 31 MB

    DibyaJyotiShortest, 1772B

    Submit

    Login to submit