第 3 题 鲜明特征 (distinctivefeatures)

时间限制 3 s · 空间限制 512 MB · 162 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 distinctivefeatures.in，输出文件 distinctivefeatures.out。

时间限制：3 秒 内存限制：512 MB

题目描述

你正在为智能手机商店的导购开发一套辅助系统。

商店中的所有智能手机排成一排，按摆放顺序用 1 到 $n$ 的整数编号。

每部智能手机都具有若干鲜明特征，例如坚固耐用或者大容量电池。共有 $m$ 种不同的鲜明特征，它们用 1 到 $m$ 的整数编号。

导购最需要回答的问题是：这部手机与旁边的手机相比有何不同？我们把这个问题形式化如下：

给定编号从 $l_i$ 到 $r_i$（含两端）的一段智能手机，以及该段内某部手机 $p_i$ 的编号（$l_i \le p_i \le r_i$），求出有多少种鲜明特征是手机 $p_i$ 具有、而在区间 $[l_i, r_i]$ 内其他任何一部手机都不具有的。

为了减轻导购的工作负担，你被委派开发一套能够高效回答这类询问的系统。

输入格式

第一行包含三个整数 $n$、$m$ 和 $g$（$1 \le n, m \le 500\,000$，$0 \le g \le 9$）——商店中智能手机的数量、不同鲜明特征的数量，以及该测试点所属的组号。

接下来的 $n$ 行按如下格式描述各手机的鲜明特征：

行首是一个整数 $k_i$（$0 \le k_i \le m$）——第 $i$ 部手机的鲜明特征数量。随后在同一行中有 $k_i$ 个整数 $1 \le a_{i,1} < \cdots < a_{i,k_i} \le m$——第 $i$ 部手机的鲜明特征，按递增顺序给出。

接下来一行包含一个整数 $q$（$1 \le q \le 500\,000$）——询问数量。

接下来的 $q$ 行描述询问。第 $i$ 行包含三个整数 $l_i$、$r_i$ 和 $p_i$（$1 \le l_i \le p_i \le r_i \le n$）——第 $i$ 个询问的参数。

记 $s$ 为所有手机的鲜明特征总数（$s = \sum_{i=1}^{n} k_i$）。保证 $n, m \le s \le 500\,000$。

输出格式

输出 $q$ 个整数——每个询问的鲜明特征数量。

样例

样例 1

输入：

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

输出：

0
3
1
1
1

样例解释

考虑该样例。

第一个询问中，第二部手机没有任何鲜明特征，因此答案为 0。

第二个询问中，该区间只包含一个元素，因此第四部手机的所有鲜明特征都符合条件。

第三个询问中，第三部手机的鲜明特征为 $[1, 4]$，第四部为 $[2, 3, 4]$，第五部为 $[1, 2]$。在第四部手机的全部鲜明特征中，只有特征 3 是它独有的，因此答案为 1。

约束与子任务

本题的测试点分为九组。只有当该组的所有测试点以及某些前置组的所有测试点都通过时，该组的分数才会被计入。注意：对某些组而言，通过样例并不是必需的。离线评测意味着你的程序在该组上的评测结果只有在比赛结束后才能获知。