Background

作为富商的你接受国王的订单，要为国王在他的领土内采购物品。

Description

王国的领土被分为 $n$ 个区域。每个区域都有一定种类的物产，物产的种类用数值表示。这些区域中有 $m$ 对区域两两之间接壤。为了方便王国的治理，在接壤处设有关卡。每个关卡都具有一个等级 $w$ 。要通过关卡的人需要手持一份通行证。通行证同样也有一个通行等级 , 记为 $k$ 。只有当 $k \geqslant w$ 时持有者才能通过该关卡从接壤区域的一边到达另一边。通行证使用次数没有上限。因为你是一个很富很富的富商 , 只要到达一地你就可以采购当地拥有的任意种类的物品，并且不计较路中所携带物品的数量和运输路程。现在作为你要从某个特定的区域出发 , 为国王收集不少于 $t$ 种不同的物产。你需要向国王申请通行证。当然为了显示自己的能力 , 你需要在保证完成任务的情况下向国王申请等级尽量低的通行证。

Format

Input

第 $1$ 行两个整数 $n$ , $m$。

第 $2$ 到 $n+1$ 行共 $n$ 行 , 第 $i$ 行第一个数 $num_{i}$ 表示第 $i-1$ 个区域拥有的物产的种数。接下来 $num_{i}$ 个互不相同的正整数 , 记为 $a_1, a_2, \cdots, a_{num_i}$ , 其中 $a_j$ 代表第 $i+1$ 个区域内有第 $a_j$ 种物产。

第 $n+2$ 到 $n+m+1$ 行共 $m$ 行每行三个正整数 $u$ , $v$ , $w$ , 代表第 $u$ 个区域与第 $v$ 个区域接壤并设有 $w$ 等级的关卡。

第 $n+m+2$ 行两个正整数 $q , k$ , 接下来共有 $q$ 组询问。

第 $n+m+3$ 行到第 $n+m+q+2$ 行共 $q$ 行, 每行两个正整数 $ps$ , $pt$ , 代表你要从 $s = (ps \oplus lastans) \bmod n + 1$ 号区域出发 , 为国王收集不少于 $t = (pt \oplus lastans) \bmod k + 1$ 种物产。

$\oplus$ 代表异或运算。

$lastans$ 代表上一组询问的答案 , 特别地 , 对于第一组询问和上一组询问无法完成任务的情况 $lastans = 0$ 。

Output

总共 $q$ 行。

第 $i$ 行为一个正整数 $ans_i$ , 代表第 $i$ 组询问的答案。 特别地 , 如果给定任意等级的通行证均不可完成任务 , $ans_i = -1$。

Sample 1

9 10
2 2 5
1 3
2 4 5
2 2 3
2 4 5
2 1 3
1 4
2 1 2
4 1 2 3 5
2 4 1
1 2 2
1 3 1
1 5 4
3 5 5
5 7 5
5 8 3
5 6 2
6 8 1
7 9 1
4 5
2 3
5 4
1 2
1 6

2
0
2
4

Limitation

对于 $30\%$ 的数据有 : $n, q \leqslant 500, m \leqslant 2 \times 10^3, \sum num_i \leqslant 10^4$

对于 $100\%$ 的数据有 :

$u, v \leqslant n,q \leqslant 10^5, m, \sum num_i \leqslant 10^6 , a_i \leqslant 10^5$

$0 \leqslant t \leqslant \max\{a_i\}$

$1 \leqslant w \leqslant 10^7$

保证图连通。

Hint

注意，你只需要收集齐物品即可，国王会派人来取的。

请开O2。