Triple Interval Intersection Removal

You are given an array a of length n. There are m queries. Each query consists of three intervals. For each query, you must remove numbers that appear in all three intervals one by one. That is, for each number x, let its frequency in the three intervals be f₁(x), f₂(x), and f₃(x) respectively. You remove exactly min{f₁(x), f₂(x), f₃(x)} copies of x from each interval. The answer to the query is the total number of elements remaining in the three intervals combined.

The formula for each query is given by:

[ \text{answer} = \Big(|I_1| + |I_2| + |I_3|\Big) - 3 \sum_{x}\min{f_1(x), f_2(x), f_3(x)}, ]

where |I_j| denotes the length of the j-th interval.

inputFormat

The first line contains two integers n and m -- the length of the sequence and the number of queries.

The second line contains n integers a[1], a[2], \dots, a[n].

Each of the following m lines contains 6 integers: l1 r1 l2 r2 l3 r3, representing three intervals [l1, r1], [l2, r2], and [l3, r3] on the array.

outputFormat

For each query, output a single line containing one integer -- the sum of the counts of the remaining numbers in the three intervals after performing the removals.

sample

7 1
1 2 2 3 3 3 3
1 7 1 7 1 7

0