题目描述

给定 n 个集合 A1⋯n​，满足 Ai​ 里的元素都严格小于 i。

可以通过这些集合构造另外 n 个集合 B1⋯n​，其中 Bi​={i}∪(∩k∈Ai​​Bk​)，即所有 k∈Ai​ 的 Bk​ 的交再并上 {i}。

给出 q 组询问，每次询问需要回答若干个 B 集合的 并集 的大小。

输入格式

第一行一个正整数。 之后行描述集合。第一个数表示集合中元素的个数，之后给出集合中的元素。 之后一行一个正整数。 之后行每行描述一个询问。格式与之前相同。

输出格式

对于每个询问，在单独的一行内输出答案。

7
0
1 1
1 1
1 2
2 2 3
0
2 2 6
3
2 2 3
2 3 5
2 4 5

3
3
4

提示

对于100% 的数据，1 <= n, m <= 50000，1 <= 10^9，-10^9 <= a, b, x, y <= 10^9。

Source

Violet 0