该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Statement

You are given a tree with $N$ vertices numbered $1$ to $N$. The $i$-th edge connects vertex $u_i$ and vertex $v_i$. Also, integer $x_i$ is written on vertex $i$.

Process $Q$ queries. In each query, you are given integers $s,t,a,b$; find the number of integers $y$ satisfying the following condition.

• Let $f$ be the number of vertices with integer $y$ written on them among the vertices on the path connecting vertex $s$ and vertex $t$. Then, $a \leq f \leq b$ holds.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq u_i \lt v_i \leq N$
• The given graph is a tree.
• $1 \leq x_i \leq N$
• $1 \leq s \lt t \leq N$
• $1 \leq a \leq b \leq N$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

• $N$ $Q$
• $x_1$ $x_2$ $\ldots$ $x_N$
• $u_1$ $v_1$
• $u_2$ $v_2$
• $\vdots$
• $u_{N-1}$ $v_{N-1}$
• $\mathrm{query}_1$
• $\mathrm{query}_2$
• $\vdots$
• $\mathrm{query}_Q$

Each query $\mathrm{query}_q$ is given in the following format:

• $s$ $t$ $a$ $b$

Output

Output $Q$ lines. The $q$-th line should contain the answer to the $q$-th query.

5 4
1 2 3 1 2
1 2
2 3
3 4
4 5
1 5 1 2
1 4 2 3
3 5 1 1
2 4 2 5

3
1
3
0

Consider the first query. The vertices on the path connecting vertex $1$ and vertex $5$ are, in order, vertex $1$, vertex $2$, vertex $3$, vertex $4$, and vertex $5$. The integers written on these vertices are, in order, $1, 2, 3, 1, 2$. Thus, there are three integers $y$ satisfying the condition: $1,2,3$.

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

1
2
0
1
0
2
1
0

• Source: AtCoder ABC 477 G