题目描述

你正在开发一个系统，用来辅助智能手机商店中的顾问。

商店中所有智能手机排成一行，按摆放顺序从 $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 500000$，$0\le g\le 9$），分别表示手机数量、不同独特特征的数量，以及当前测试点所属分组编号。

接下来 $n$ 行描述每台手机的独特特征。每行格式如下：

先给出一个整数 $k_i$（$0\le k_i\le m$），表示第 $i$ 台手机具有的独特特征数量；随后在同一行给出 $k_i$ 个整数

表示第 $i$ 台手机具有的特征编号，按递增顺序给出。

下一行包含一个整数 $q$（$1\le q\le 500000$），表示询问数量。

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

设

为所有手机特征数量之和。保证 $n,m\le s\le 500000$。

输出格式

输出 $q$ 个整数，分别表示每个询问的答案。每个答案占一行。

样例

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

样例解释

在第一个询问中，第 $2$ 台手机没有任何独特特征，因此答案为 $0$。

在第二个询问中，区间只包含一个元素，因此第 $4$ 台手机的全部独特特征都满足要求。

在第三个询问中，第 $3$ 台手机的特征为 $[1,4]$，第 $4$ 台手机的特征为 $[2,3,4]$，第 $5$ 台手机的特征为 $[1,2]$。在第 $4$ 台手机的特征中，只有特征 $3$ 在该区间内是唯一的，因此答案为 $1$。