Altaireon lives in a galaxy having N planets interconnected with N−1 pathways. Each planet has its population known to Altaireon.
His friend Apptica, tries to test his knowledge by devising an interesting situation. On the galactic network, he needs to find the following given three distinct planets A,B and C.
1. Find XOR of the populations of all the planets which lie on the way fromA to B (inclusive) and call it xor.
2. Find the planet's population which is closest to B and lies on the way from A to C (inclusive), and call it pop.
3. Tell Apptica the value of (xor * pop) % 10^9 + 7
Apptica asks Altaireon this problem Q times. Help him find the the value.
Input:
First line contains N and Q, number of planets in the galaxy and number of times Apptica asks Altaireon the question.
Next line contains N space separated integers, denoting population of N planets.
Next N-1 lines contain 2 integers u, v denoting there is a direct way from planet u to planet v.
Next Q lines contain, 3 integers A, B and C, each.
Output:
Print the value of (xor * pop) % 10^9 + 7 for each query on the next line.
Constraints:
1≤N,Q≤105
1≤population≤107
1≤u,v,A,B,C≤N