C1539 [Ynoi]2016-A

内存限制:512 MB 时间限制:4000 ms

题目描述

您正在打galgame,然后突然发现您今天太颓了,于是想写个数据结构题练练手:

一个长为 $n$ 的序列 $a$。

有 $m$ 个询问,每次询问三个区间,把三个区间中同时出现的数一个一个删掉,问最后三个区间剩下的数的个数和,询问独立。

注意这里删掉指的是一个一个删,不是把等于这个值的数直接删完,比如三个区间是 $[1,2,2,3,3,3,3]$,$[1,2,2,3,3,3,3]$ 与 $[1,1,2,3,3]$,就一起扔掉了 $1$ 个 $1$,$1$ 个 $2$,$2$ 个 $3$。

输入格式

第一行两个数表示 $n,m$。

第二行 $n$ 个数表示 $a[i]$​。

之后 $m$ 行,每行 $6$ 个数 $l_1,r_1,l_2,r_2,l_3,r_3$ 表示这三个区间。

输出

对于每个询问,输出一个数表示答案。

样例

样例输入 1

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

样例输出 1

3 0

提示

$n , m \le 100000 , 1 \le a[i] \le 1000000000$