T2 花海

(iberis/2s/1024MB)

题目背景

一片花海。

有你喜欢的花吗？

题目描述

有一片花海，Displace 从中选出了 $n$ 朵。

花有很多种属性，其中容易观察的有 $m$ 种属性。第 $i$ 朵花有 $k_i$ 种属性，用一个序列 $\{a_{i, 1}, a_{i, 2}, \cdots, a_{i, k_{i}}\}$ 描述这朵花具有的属性，保证 $1\leq a_{i, 1}

每朵花都应当是独一无二的。Displace 会给你 $q$ 次询问，每次询问给出三个参数 $l, r, p$，询问第 $p$ 朵花有多少种属性满足这个属性在这个区间内出现且仅出现了一次。保证 $l\leq p\leq r$。

本题采用子任务捆绑测试。

输入格式

第一行一个整数 $taskid$ ，表示子任务编号。 $taskid=0$ 表示样例。

接下来一行两个整数 $n,m$，分别表示花的数量和属性的数量。

接下来 $n$ 行，每行先给出一个整数 $k_i$，表示第 $i$ 朵花的属性数量；接下来给出 $k_i$ 个整数，描述这朵花具有的属性。

接下来一行一个整数 $q$，表示询问的数量。

接下来 $q$ 行，每行 $3$ 个整数 $l, r, p$，表示询问的参数，含义同题目描述。

输出格式

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

样例

样例输入 1

0
6 4
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

样例输出 1

0
3
1
1
1

其余样例见下发文件。

• ex_iberis2 与子任务 $1$ 的限制一致，

• ex_iberis3 与子任务 $3$ 的限制一致，

• ex_iberis4 与子任务 $4$ 的限制一致，

• ex_iberis5 与子任务 $5$ 的限制一致。

时空限制与数据范围

2s, 1024MB

对于所有的数据：

• $n,m,q\leq 5\times 10^{5}$,

• $0\leq k_i\leq m, \sum {k_i}\leq 10^{6}$,

• $1\leq a_{i, 1}

• $1\leq l\leq p\leq r\leq n$

特殊性质 A: $1\leq k_i\leq 2$。