← 返回题目列表

Codeforces · 369/E

E. 瓦莱拉和查询

中文机器翻译题面 查看原题

瓦莱拉喜欢片段。他最近提出了一个有趣的问题。

Ox 坐标轴有 n 段,第 i 段从位置 li 开始,到位置 ri 结束(我们将其标记为 [li, ri])。你的任务是处理 m 个查询,每个查询由数字 cnti 和位于 Ox 轴上的点的一组 cnti 坐标组成。查询的答案是段数,其中每个段至少包含查询中的一个点。如果 l ≤ q ≤ r,则线段 [l, r] 包含点 q。

Valera 发现这个问题的解决太困难了。所以他请求你帮助他。帮助瓦莱拉。

输入

第一行包含两个整数n, m (1 ≤ n, m ≤ 3·105)——坐标轴上的线段数和查询数。

接下来的 n 行包含段的描述。第 i 行包含两个正整数 li, ri (1 ≤ li ≤ ri ≤ 106) — 第 i 段的边界。

接下来的 m 行包含查询的描述,每行一个。每行从整数 cnti (1 ≤ cnti ≤ 3·105) 开始 — 第 i 个查询中的点数。然后该行包含 cnti 个不同的正整数 p1, p2, ..., pcnti (1 ≤ p1 < p2 < ... < pcnti ≤ 106) — 第 i 个查询中的点的坐标。

保证所有查询中的点数总和不超过3·105。

输出

打印 m 个非负整数,其中第 i 个数字是对第 i 个查询的响应。

示例

输入 #1

3 3
1 3
4 5
6 7
3 1 4 7
2 4 5
1 8

输出 #1

3
1
0