K. Pèppito.
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Holla th're
— Pèppito, Pèppito

Pèppito is a bird stuck on a tree because he can't fly, he travels only on the tree by walking on branches.

Pèppito's tree is a tree of $$$n$$$ vertices, the $$$i_{th}$$$ node has an integer $$$a_i$$$, he gets bored sometimes, so he came up with this problem:

Given four integers $$$u$$$ $$$v$$$ $$$l$$$ $$$r$$$: let's define $$$f(x)$$$ as the number of occurrences of $$$x$$$ on the simple path between nodes $$$u$$$ and $$$v$$$, calculate $$$\sum_{x = l}^r f(x)^2$$$.

Pèppito thought that it might be too easy to solve it, so you have to answer $$$q$$$ of these problems.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1 \leq n, q \leq 10^5)$$$.

The second line contains $$$n$$$ integers $$$a_i$$$ $$$(1 \leq a_i \leq 10^5)$$$.

The next $$$q$$$ lines each contains 4 integers $$$u$$$ $$$v$$$ $$$l$$$ $$$r$$$, $$$(1 \leq u, v \leq n)$$$ $$$(1 \leq l \leq r \leq 10^5)$$$.

Output

For each of the $$$q$$$ problems, print on integer the answer to that problem.

Examples
Input
5 3
9 4 7 7 8
1 2
2 3
1 4
4 5
4 4 6 6
4 2 6 8
3 5 2 7
Output
0
1
5
Input
5 4
8 2 6 7 10
1 2
1 3
2 4
4 5
2 4 1 7
1 5 4 10
4 5 6 10
3 5 1 8
Output
2
3
2
4
Input
8 2
3 7 6 5 4 5 7 3
1 2
1 3
1 4
2 5
2 6
5 7
6 8
2 2 1 9
8 7 7 8
Output
1
4