#becncw. 徽章（badge）

时间限制：3 s       空间限制：512 MiB       标签： 根号分治 扫描线 

算法难度等级：0       思维难度等级：0       实现难度等级：0

Kaguya 是一个还没能辟谷的女孩子。

有一天，Kaguya 来到了食堂。食堂的队伍好长好长，居然长达 $n$ 个同学。Kaguya 学过一点信息学，所以她将队伍中的同学依次编号为 $1,2,\cdots,n$。其中，有 $n$ 个区间 $[l_i,r_i]$ 引起了她的兴趣。

Kaguya 拿出了 $m$ 个微章，并将第 $i$（$1\leq i\leq m$）个徽章送给了第 $x_i$ 个人。

Kaguya 不喜欢奇数。她希望知道，$[l_1,r_1],\ [l_2,r_2],\ \cdots,\ [l_n,r_n]$ 中，有多少区间 $[l,r]$ 满足：第 $1$ 个人到第 $r$ 个人得到的徽章数目总和是奇数。

由于 Kaguya 非常可爱，所以你需要回答她 $q$ 次同样形式的询问。

输入格式

输入的第一行包含两个整数 $n,q$，分别表示 Kaguya 感兴趣的区间数目和询问数目。接下来 $n$ 行，第 $1$ 行包含两个整数 $l_i,r_i$，表示 Kaguya 感兴趣的第 $i$ 个区间的左右端点。

接下来依次输入每个询问，对于每个询问：

输入的第一行包含一个整数 $m$，表示 Kaguya 拿出的微章数目。

输入的第二行包含 $m$ 个整数 $x_{1\ldots m}$ 表示 Kaguya 将第 $i$（$1\leq i\leq m$）个徽章送给了第 $x$ 个人。

输出格式

对于每次询问，输出一行一个整数表示对应的答案。

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

3
3

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

5
5

样例 3

见选手目录下的 badge/badge3.in 和 badge/badge3.ans。

样例 4

见选手目录下的 badge/badge4.in 和 badge/badge4.ans。

样例 5

见选手目录下的 badge/badge5.in 和 badge/badge5.ans。

数据范围

对于所有测试数据保证 $1\leq n\leq 5\times 10^5$，$0\leq q\leq n$，$1\leq l_i\leq r_i\leq n$，$1\leq m,\sum m\leq n$，$1\leq x_i\leq n$。

每个测试点的具体限制见下表：