Given a sequence $a$ of length $n$.

There are $m$ queries. Each query provides three intervals. For each query, remove the numbers that appear in all three intervals one by one. Calculate the total number of remaining elements across the three intervals. Queries are independent.

Note that "removing one by one" means we do not remove all occurrences of a value at once. For example, if the three intervals are $[1, 2, 2, 3, 3, 3, 3]$, $[1, 2, 2, 3, 3, 3, 3]$, and $[1, 1, 2, 3, 3]$, we remove one $1$, one $2$, and two $3$s from each interval.

Input

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers representing $a_i$.

The following $m$ lines each contain $6$ integers $l_1, r_1, l_2, r_2, l_3, r_3$ representing the three intervals.

Output

For each query, output a single integer representing the answer.

Examples

Input 1

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

Output 1

3
0

Subtasks

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477

$1 \leq n, m \leq 10^5$, $1 \leq a_i \leq 10^9$, $1 \leq l_1, r_1, l_2, r_2, l_3, r_3 \leq n$, $l_1 \leq r_1$, $l_2 \leq r_2$, $l_3 \leq r_3$.