Given a sequence $A$ with $n$ positive integers, $a_1$, $a_2$, $\dots$, $a_n$, and $q$ queries. Each query specifies three subarrays $[L_1,R_1]$, $[L_2,R_2]$, and $[L_3,R_3]$. Bob wants to find the value

$${\displaystyle \text{len}(L_1,R_1)+\text{len}(L_2,R_2)+\text{len}(L_3,R_3)-3\times |a[L_1:R_1]\cap a[L_2:R_2]\cap a[L_3:R_3]|}$$

where $\text{len}(L_i,R_i)$ is the length of the subarray $[L_i,R_i]$ and $|a[L_1:R_1]\cap a[L_2:R_2]\cap a[L_3:R_3]|$ represents the number of shared common integers in all three subarrays.

For example, if the $1$st subarray is $[1,2,2,3,3]$, the $2$nd subarray is $[3,2,3,1,1]$, and the $3$rd subarray is $[1,3,2,2,3]$, the shared common integers are $(1,2,3,3)$, and thus the value Bob wants to find is $5+5+5-3\times 4=3$.

Input Specification

The first line of input contains two integers $n$ and $q$ ($1\le n,q\le {10}^5$), indicating the length of the sequence and the number of queries.

The second line of input contains $n$ integers $a_i$ ($1\le a_i\le {10}^9$).

Each of the following $q$ lines contains six integers, $L_1$, $R_1$, $L_2$, $R_2$, $L_3$, $R_3$ ($1\le L_i\le R_i\le n$).

Output Specification

Output one integer per line for each query.

Constraints

Subtask	Points	Additional constraints
$1$	$30$	$n,q\le 2000$.
$2$	$70$	No additional constraints.

Sample Input

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

Sample Output

3
0