There is a bidirectional unweighted connected graph with ~N~ nodes, numbered from ~1~ to ~N~, each with a value ~a_i~.

There are exactly ~N - 1~ edges. The ~i^{\text{th}}~ edge connects ~u_i~ and ~v_i~. There is at most one edge between any pair of nodes. No edge connects a node with itself.

~Q~ questions are asked in the form: "On the path from ~u_j~ to ~v_j~, including these ~u_j~ and ~v_j~ themselves, how many nodes have a value of at least ~k_j~?".

Constraints

All numbers in the input are positive integers.

~1 \leq N, Q \leq 10^5~

~1 \leq a_i, k_j \leq 10^9~

Input Specifications

All numbers on the same line of input are separated by spaces.

The first line of input contains ~2~ numbers: ~N~ and ~Q~.

The second line of input contains ~N~ numbers, the ~i^{\text{th}}~ number is ~a_i~.

The next ~N - 1~ lines each contain ~2~ numbers: ~u_i~ and ~v_i~.

The next ~Q~ lines contain ~3~ numbers: ~u_j~, ~v_j~, and ~k_j~. All ~3~ of these numbers are encrypted. To decrypt them, take the bitwise XOR with the previous answer. The first of these queries is not encrypted.

Output Specification

~Q~ lines each containing one number, the ~j^{\text{th}}~ line representing the answer to the ~j^{\text{th}}~ question.

Sample Input 1

5 2
10 20 30 40 50
1 2
1 3
2 4
2 5
3 4 20
7 6 29

Sample Output 1

3
2

Explanation for Sample 1

The first query is not encrypted.

The path from ~3~ to ~4~ is ~3 \to 1 \to 2 \to 4~. Out of these ~4~ trees, ~3~ of them have a height of at least ~20~.

The second query is encrypted. By taking the bitwise XOR of the previous answer, which is in this case ~3~, we get

• ~7 \oplus 3 = 4~
• ~6 \oplus 3 = 5~
• ~29 \oplus 3 = 30~.

This means the decrypted input is 4 5 30.

The path from ~4~ to ~5~ is ~4 \to 2 \to 5~. Out of these ~3~ trees, ~2~ of them have a height of at least ~30~.

Sample Input 1 Without Encryption

This sample does not have the XOR involved. This is just for convenience of viewing and is not representative of the test data.

5 2
10 20 30 40 50
1 2
1 3
2 4
2 5
3 4 20
4 5 30