Bithuania 有 $n$ 个城市，由 $m$ 条双向道路连接。目前，每两个城市之间都存在一条路径。在每个城市中住着一个孩子。每个孩子都想给其他所有孩子寄一张圣诞明信片。不幸的是，持续的圣诞假期导致一些道路正在翻修。由于困难，对于某些道路，明信片只能单向运输，或者根本无法通过该道路运输。

Bithuania 政府收集了许多道路关闭计划。你的任务是依次找出对于每一个计划，有多少个孩子能够从其他所有孩子那里收到明信片。

输入格式

第一行包含三个整数 $n, m, q$ ($2 \le n \le 3000, 1 \le m \le 500\,000, 1 \le q \le 500\,000$)。接下来的 $m$ 行包含道路网络的描述：第 $i$ 行包含两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示城市 $u_i$ 和 $v_i$ 之间的一条道路。道路按在输入中出现的顺序编号为 $1$ 到 $m$。一对城市之间可能由多条道路连接。

然后是 $q$ 个道路关闭计划的描述（编号为 $1$ 到 $q$）。第 $i$ 个描述以包含一个整数 $r_i$ ($1 \le r_i \le 100$) 的行开始，表示翻修道路的数量。接下来是第 $i$ 个计划中关闭道路的描述。它包含 $r_i$ 行；每一行描述一条被关闭的道路，并包含三个数字 $x, p_{uv}, p_{vu}$ ($0 \le x < m, p_{uv}, p_{vu} \in \{0, 1\}, p_{uv} + p_{vu} \ge 1$)。令 $S_i$ 为关于第 $1$ 到 $(i-1)$ 个计划的答案之和。那么，第 $i$ 个翻修计划包括连接 $j := ((x + S_i) \bmod m) + 1$。如果 $p_{uv} = 1$，则将无法通过道路 $j$ 从城市 $u_j$ 前往城市 $v_j$。如果 $p_{vu} = 1$，则将无法通过道路 $j$ 从城市 $v_j$ 前往城市 $u_j$。

你可以假设对于每个计划，值 $x$ 是不同的。此外，所有计划中 $r_i$ 的总和不超过 $500\,000$。

输出格式

对于每个道路关闭计划，输出一行，包含能够从其他所有孩子那里收到明信片的孩子的数量。

样例

输入 1

4 4 3
1 2
4 3
2 3
1 3
2
3 1 1
1 0 1
3
1 1 0
0 1 0
3 1 0
1
1 1 1

输出 1

3
1
0

说明

样例解释：在第一个计划中，我们完全关闭了道路 4（连接城市 1 和 3），并部分关闭了道路 2（无法从 3 前往 4）。来自城市 1、2 和 3 的孩子可以从其他所有孩子那里收到明信片。

在第二个查询中，我们有 $S_2 = 3$。道路 1、4 和 3 被部分封锁（我们分别禁止从 1 前往 2，从 1 前往 3，以及从 2 前往 3）。只有来自城市 1 的孩子可以从其他所有孩子那里收到明信片。

在最后一个查询中，我们有 $S_3 = 4$。道路 2 被封锁。在这种情况下，没有孩子能从其他所有孩子那里收到明信片。