初始时有一个数组 $a$，满足 $a[i] = i$。该数组执行了 $m$ 次操作。在每次操作中，会选择两个随机下标 $i$ 和 $j$，并交换元素 $a[i]$ 和 $a[j]$。

你需要回答 $q$ 个询问。每个询问给出一个数组 $b_1, b_2, \dots, b_k$。你需要找到 $b$ 成为 $a$ 的连续子数组的第一次时刻。

交换操作中的下标保证是独立地从均匀分布中选择的。

输入格式

第一行包含三个整数 $n, m$ 和 $q$ ($1 \le n, m, q \le 10^5$)。

接下来的 $m$ 行，每行包含两个整数 $i$ 和 $j$ ($1 \le i < j \le n$)，描述交换操作。

接下来的 $q$ 行包含询问描述。每个描述以整数 $k$ ($1 \le k \le n$) 开头，随后是 $k$ 个整数 $b_1, b_2, \dots, b_k$ ($1 \le b_i \le n$)。保证所有 $k$ 的总和不超过 $10^5$。

输出格式

对于每个由数组 $b$ 描述的询问，你需要输出在 $b$ 成为 $a$ 的连续子数组之前所执行的操作次数。如果初始数组 $a$ 就包含 $b$，则输出 0。保证 $b$ 在某个时刻一定是 $a$ 的子数组。

样例

输入 1

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

输出 1

1
3
0
2
3