Description

You are playing a galgame, and suddenly realize you have been slacking off too much today, so you want to write a data structure problem to practice:

There is a sequence $a$ of length $n$.

There are $m$ queries. Each query gives three intervals. For numbers that appear in all three intervals, delete them one by one. Ask for the sum of the counts of remaining numbers in the three intervals at the end. Queries are independent.

Note that “delete” means deleting one by one, not deleting all elements equal to that 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]$, then we throw away $1$ occurrence of $1$, $1$ occurrence of $2$, and $2$ occurrences of $3$ together.

Input Format

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

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

Then follow $m$ lines. Each line contains $6$ integers $l_1,r_1,l_2,r_2,l_3,r_3$ describing the three intervals.

Output Format

For each query, output one integer denoting the answer.

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

3
0

Hint

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$。

Translated by ChatGPT 5