The "Photo" installation can be abstracted as a tree containing $n$ nodes, where each node represents an image node, and the filter color of node $i$ ($1 \le i \le n$) is $c_i$. There are $n-1$ light beams connecting the nodes, numbered sequentially from $1$ to $n-1$.

In the process of exploring the patterns, you recorded data from $m$ dynamic effect tests. For each test, you specify an index range $[l, r]$ for the light beams. Assume that only the light beams with indices falling within this range are activated (other light beams with indices outside this range are disconnected), causing the entire original network to split into several independent connected components.

To analyze the changes more deeply, you need to calculate for each test: the sum of the number of types of visible filters (i.e., filter colors that appear an odd number of times) contained in each connected component.

输入格式

The first line contains two positive integers $n, m$ ($1 \le n \le 3 \times 10^5, 1 \le m \le 10^6$), representing the number of image nodes and the number of tests, respectively.

The second line contains $n$ positive integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), representing the filter color of each image node.

The next $n-1$ lines, the $i$-th line ($1 \le i \le n-1$) contains two positive integers $u_i, v_i$ ($1 \le u_i, v_i \le n$), representing the two nodes connected by the light beam with index $i$.

The next $m$ lines, each contains two positive integers $l, r$ ($1 \le l \le r \le n-1$), representing the light beam index range for a test.

输出格式

Output $m$ lines, each containing a non-negative integer, representing the sum of the number of types of visible filters contained in all independent connected components for each test.

Examples

Input 1

12 13
2 4 1 2 3 4 2 4 3 3 3 6
3 5
9 1
5 11
4 9
1 12
2 1
10 8
11 10
8 4
6 11
7 6
1 3
2 2
6 6
9 11
6 11
1 4
8 10
1 11
5 10
4 7
1 10
6 8
11 11

Output 1

10
12
12
12
6
8
10
4
8
12
4
10
12