有一个迷宫，由 $N$ 个房间和 $N-1$ 条走廊连接而成。房间编号为 $1$ 到 $N$，每个房间呈圆形。走廊满足以下限制：

• 每条走廊连接两个不同的房间。
• 任意两个房间之间有且仅有一条由走廊组成的路径。

在迷宫中导航的一个困难是灯全灭了，所以你看不见自己所在的位置。为了辅助导航，每个房间都包含一个激光指示器，初始时指向某条走廊。考虑以下策略：

• 将房间的激光指示器顺时针旋转，直到它指向另一条走廊。
• 沿着房间的激光指示器指向的走廊移动。
• 无限重复上述两个步骤。

你创建了 $Q$ 个查询来研究这一策略。对于每个查询，给定一个整数 $K$，你从房间 $1$ 出发。确定在经过恰好 $K$ 条走廊后的最终房间。每个查询后，所有激光指示器都会重置为它们的初始方向。

输入格式

第一行包含整数 $N$ 和 $Q$ ($2 \le N \le 800\,000, 1 \le Q \le 800\,000$)。

接下来的 $N$ 行描述了迷宫的布局，其中第 $i$ 行描述房间 $i$。具体来说，它包含一个整数 $k$，表示连接到房间 $i$ 的走廊数量，随后是 $k$ 个整数 $c_1, c_2, \dots, c_k$，按顺时针顺序表示这些走廊通向的房间。最后，房间 $i$ 的激光指示器初始指向通向房间 $c_1$ 的走廊。

最后的 $Q$ 行描述查询，每行包含一个整数 $K$ ($1 \le K \le 10^{15}$)。

对于 $25$ 分中的 $4$ 分，第 $i$ 条走廊连接房间 $i$ 和房间 $i+1$。

对于另外 $25$ 分中的 $4$ 分，$N \le 2000$ 且 $Q \le 2000$。

对于另外 $25$ 分中的 $12$ 分，$Q = 1$。

输出格式

输出 $Q$ 行，按顺序回答每个查询。

样例

输入 1

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

输出 1

2
1
2
4
2
3

说明 1

这是迷宫的初始状态：

该策略访问房间的顺序为：

$1, 2, 1, 2, 4, 2, 3, \dots$