Jontrona of Liakot

Zeronfinity Mirror of NSTU ICE Fest R...
Limits 3s, 512 MB

Liakot, the king of Cox's Bazar, is currently in a dire situation. His own younger sister Ayesha is conspiring with a surfer named Sohel to dethrone Liakot.

It all started from when they were mere children. Ayesha and Sohel would team up to bully poor little Liakot. Often, they would give Liakot a programming problem and laugh at his failure.

In the problem, Sohel would make a tree of NN nodes where the ii-th node contains a number AiA_i. The root of the tree is the node number 1. Then Ayesha would give Liakot QQ queries to answer.

In each query, Ayesha would choose two nodes of the tree UU and VV (VV will always be in the subtree of UU). Ayesha takes the subtree rooted at UU and then from that subtree, she removes the subtree rooted at VV.

Ayesha takes all the numbers from the tree segment she made this way and does a XOR operation with ZZ on all of these numbers (XOR is exclusive-or operation). She chooses another number KK in that query, and Liakot has to answer the KK-th smallest number among Ayesha's XOR'ed numbers.

Can you help Liakot by finding the KK-th smallest number after XOR-ing ZZ to all the numbers which are in the subtree rooted at UU but not in the subtree rooted at VV?


Input starts with two space-separated integers NN and QQ, representing respectively the number of nodes in the tree and the number of queries.

In the next line, NN space-separated integers are given, the ii-th integer representing the number AiA_i of the node ii.

In the following N1N-1 lines, two integers XX and YY are given representing an edge between nodes XX and YY in the tree. It is guaranteed that the given tree will be a valid one.

Finally, in each of the last QQ lines of input, four space-separated integers UU, VV, ZZ and KK will be given representing the queries.


1N1051 \leq N \leq 10^5
1Q1061 \leq Q \leq 10^6
1Ai,Z,K1091 \leq A_i, Z, K \leq 10^9
1X,YN1 \leq X, Y \leq N
1U,VN1 \leq U, V \leq N

It is guaranteed that the tree will always be a valid one. In each query, VV will always be within the subtree rooted at UU.


For each query, print the answer in a single line. If the answer does not exist for a query, print “-1” (w/o quotes) instead in the corresponding line.


8 6
3 7 10 10 5 8 8 1
4 2
7 3
4 5
8 6
4 7
1 4
1 8
4 2 2 3
7 3 2 2
3 3 2 9
8 6 8 1
1 7 3 4
1 5 3 4

In the first query, Ayesha takes the subtree rooted at node 4 and removes the subtree rooted at node 2 from it. So, the remaining segment has the nodes 3, 4, 5 and 7 in it.

The numbers in these nodes are 10, 10, 5 and 8 respectively. In the first query, ZZ = 2. After XOR-ing ZZ with these numbers (10, 10, 5 and 8), they become 8, 8, 7 and 10 respectively. The 3rd smallest number among them is 8, thus the answer.

Dataset is big, use fast I/O.


Login to submit.



100% Solution Ratio
tmwilliamlin168Earliest, Jan '20
Deshi_TouristFastest, 1.1s
mumith_fahim99Lightest, 49 MB
Kuddus.6068Shortest, 1233B
Toph uses cookies. By continuing you agree to our Cookie Policy.