MangoSmash

JONTRONA RUET CodeSmash 2020
Limits 1.5s, 512 MB

Your friend has come to visit the RUET campus. As the Mango season goes on \cdots, he/she said “Mama Aam Khawa!”. As Manik Bhai leased those Mango Trees, he will not give you guys Mangoes for free rather he gave you a problem as he knew you are a great problem solver. You and your friend want one mango for each but with Distinction. The Distinction means bitwise XORXOR of the sweetness of mangoes must be positive (greater than zero). There will be multiple queries.

Given a Mango Tree rooted at node 11. Each node represents a Mango with sweetness SiS_i. Manik bhai will only let you choose mangoes from a subtree. So, in each query, Manik bhai will give you a node UU and you just need to find - in the subtree rooted at UU, how many ways you can take two mangoes such that they have Distinction.

A subtree of a tree is a tree that consists of a node in the tree and all of this node's descendants. The tree can also be considered as a subtree of itself.

Input

The first line of the input will have NN(1N5×105)(1 \leq N \leq 5 \times 10^5) and QQ (1Q5×105)(1 \leq Q \leq 5 \times 10^5), number of Mangoes in the Tree and number of queries respectively.

Then the next line contains N numbers in form SiS_i(1Si2311)(1 \leq S_i \leq {2^{31} -1}), the sweetness of the ithi^{th}mango.

Next N1N - 1 lines, each containing a(1aN)a(1\leq a\leq N) and b(1bN)b(1\leq b\leq N) as there is a branch between node aa and bb. It’s guaranteed that they will form a Tree.

The next line contains QQ numbers, indicating UU, the root of the Subtree for each query.

Output

For each query, print the answer of the Query. As the answer can be too large print modulo 10000000071000000007.

Sample

InputOutput
5 5
1 2 2 3 2
1 2
2 4
1 3
2 5
1 2 3 4 5
7
2
0
0
0

Submit

Login to submit.

Statistics

67% Solution Ratio
mahabub.tweetEarliest, 4M ago
steinumFastest, 0.7s
steinumLightest, 86 MB
steinumShortest, 1556B
Toph uses cookies. By continuing you agree to our Cookie Policy.