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 NN nodes. The nodes are numbered from 11 to NN. The root node of that tree is RR. Every node in that tree is associated with a value. Let, XuX_u be the value associated with node uu.

You have to answer QQ queries. In each query, you will be given a pair of integers (u,k)(u, k) and you have to calculate the Bitwise AND of all the values of kk-th child in the subtree of node uu. If there is no kk-th child in subtree then the answer will be 1-1.

Input

First line of the Input will have a single integer TT (1T51 \leq T \leq 5) denoting the number of test cases.

The first line of every test case contains three integers NN (1N1051 \leq N \leq 10^5), QQ (1Q1051 \leq Q \leq 10^5), RR (1RN1 \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 NN space-separated integers representing the values of XuX_u (0Xu1090 \leq X_u \leq 10^9).

Next N1N-1 lines will contain a pair of integers (u,v)(u, v) which denotes there is an edge between node uu and node vv. Here, (1u,vN1 \leq u, v \leq N).

Next QQ line will have a pair of integers (u,k)(u, k) representing each query. Here, (1uN1 \leq u \leq N) and (0k1050 \leq k \leq 10^5).

Subtask 1 (5 Points)

1T51 \leq T \leq 5, 1N1041 \leq N \leq 10^4, 1Q1041 \leq Q \leq 10^4, 0Xu1090 \leq X_u \leq 10^9, 0k1050 \leq k \leq10^5

Subtask 2 (5 Points)

1T51 \leq T \leq 5, 1N1051 \leq N \leq 10^5, 1Q1051 \leq Q \leq 10^5, 0Xu1090 \leq X_u \leq 10^9, 0k10 \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 22 is 2{2}. 1st children of node 22 are 3,4{3, 4}. 2nd children of node 22 are 5,6,7,8{5, 6, 7, 8}. And there is no 3rd child of node 22.


Discussion

Statistics


62% Solution Ratio

DibyaJyotiEarliest, Jul '20

developer.spyderFastest, 0.3s

Shahwat_Has9Lightest, 31 MB

developer.spyderShortest, 1668B

Submit

Login to submit

Editorial

Subtask 1: 1 ≤ N, Q ≤ 104 For this subtask, we only need the simple idea of DFS. At first from the r...

Toph uses cookies. By continuing you agree to our Cookie Policy.