Pak Dengklek 刚刚开发了一个社交媒体网站。网站共有 $N$ 名用户，编号为 $0$ 到 $N - 1$。一天有 $S$ 个小时。所有用户都有固定的每日使用时间表。对于每个满足 $0 \le i \le N - 1$ 的 $i$，用户 $i$ 每天会在线 $T[i]$ 次：

• 从第 $A[i][0]$ 小时的开始到第 $B[i][0]$ 小时的结束，
• 从第 $A[i][1]$ 小时的开始到第 $B[i][1]$ 小时的结束，
• ...
• 从第 $A[i][T[i] - 1]$ 小时的开始到第 $B[i][T[i] - 1]$ 小时的结束。

在任何时候，网站上的所有用户都喜欢与所有其他在线用户分享新闻。不幸的是，其中一名用户在第一天开始时携带了一个恶作剧（hoax）并会传播它。因此，所有在第一天结束时与携带恶作剧的用户见过面的用户也会获得该恶作剧。如果两个用户至少有一个小时同时在线，则称这两个用户见过面。

这个恶作剧也会在第二天传播。因此，所有在第一天结束时与携带恶作剧的用户见过面的用户，在第二天结束时也会获得该恶作剧。这种情况在接下来的日子里持续发生。

共有 $Q$ 个场景，每个场景可以用一个整数 $P$ 表示。对于每个场景，第一天开始时携带恶作剧的用户是用户 $P$。不同的场景可能会导致不同的恶作剧传播情况。因此，对于每个场景，Pak Dengklek 想知道在第 $N$ 天结束时携带恶作剧的用户数量，其中 $N$ 是用户总数。

实现细节

你需要实现以下过程：

void init(int N, int S, int[] T, int[][] A, int[][] B)

• $N$: 数组 $T, A, B$ 的元素个数。
• $S$: 一天中的小时数。
• $T$: 一个长度为 $N$ 的数组，描述每个用户每天在线的次数。
• $A, B$: 长度为 $N$ 的数组。$A[i]$ 和 $B[i]$ 是长度为 $T[i]$ 的数组，描述用户 $i$ 每天在线的时间段。
• 该过程在调用 count_users 之前恰好被调用一次。

int count_users(int P)

• $P$: 第一天开始时携带恶作剧的用户编号。
• 该过程应返回在第 $N$ 天结束时携带恶作剧的用户数量，其中 $N$ 是用户总数。
• 该过程被调用恰好 $Q$ 次。

样例

考虑以下调用序列：

init(5, 10, [2, 1, 1, 1, 1],
 [[2, 7], [1], [1], [9], [5]], [[4, 9], [3], [1], [10], [6]])

count_users(0)

这意味着用户 $0$ 在第一天开始时携带恶作剧。用户 $0$ 与用户 $1$ 见过面（在第 $2$ 小时到第 $3$ 小时），并与用户 $3$ 见过面（在第 $9$ 小时）。因此，在第一天结束时，这两个用户将获得恶作剧。用户 $1$ 也与用户 $2$ 见过面（在第 $1$ 小时）。因此，在第二天结束时，用户 $2$ 也将获得恶作剧。第三、四、五天将不会有恶作剧传播，因此在第五天结束时有 $4$ 名用户携带恶作剧。因此，该过程应返回 $4$。

count_users(4)

这意味着用户 $4$ 在第一天开始时携带恶作剧。用户 $4$ 没有与其他用户见面，因此其他用户不会获得恶作剧。因此，该过程应返回 $1$。

数据范围

• $1 \le N \le 200\,000$
• $1 \le S \le 10^9$
• $1 \le Q \le 100\,000$
• $1 \le T[i] \le S$ (对于每个 $0 \le i \le N - 1$)
• $T$ 中所有元素的总和不超过 $200\,000$。
• $1 \le A[i][j] \le B[i][j] \le S$ (对于每个 $0 \le i \le N - 1$ 和 $0 \le j \le T[i] - 1$)
• $B[i][j - 1] < A[i][j]$ (对于每个 $0 \le i \le N - 1$ 和 $1 \le j \le T[i] - 1$)
• $0 \le P \le N - 1$
• 所有场景中的 $P$ 值各不相同。

子任务

1. (15 分) $N, S, Q \le 50$，且 $T$ 中所有元素的总和不超过 $50$。
2. (17 分) $N, Q \le 50$，且 $T$ 中所有元素的总和不超过 $50$。
3. (21 分) $N, Q \le 300$，且 $T$ 中所有元素的总和不超过 $300$。
4. (26 分) $N, Q \le 2000$，且 $T$ 中所有元素的总和不超过 $2000$。
5. (21 分) 无附加限制。

样例评测程序

样例评测程序按以下格式读取输入：

• 第 $1$ 行：$N \ S \ Q$
• 第 $2 + i$ 行 ($0 \le i \le N - 1$)：$T[i] \ A[i][0] \ B[i][0] \ \dots \ A[i][T[i] - 1] \ B[i][T[i] - 1]$
• 第 $2 + N + k$ 行 ($0 \le k \le Q - 1$)：场景 $k$ 的 $P$

样例评测程序按以下格式打印你的答案：

• 第 $1 + k$ 行 ($0 \le k \le Q - 1$)：场景 $k$ 的 count_users 返回值