题目描述

有一个由 $N$ 个房间和 $N-1$ 条过道组成的迷宫。房间从 $1$ 到 $N$ 编号，并且每个房间都是圆形的。过道满足以下条件：

• 每条过道连接两个不同的房间；
• 每对房间被恰好一条由过道组成的路径连通。

走出这个迷宫中的一个难题就是所有灯都熄灭了，所以你看不到你在哪儿。为了帮助确定方向，每个房间都有一个激光笔，初始指向某条过道。考虑如下策略：

• 顺时针旋转屋子里的激光笔，直到它指向下一条过道为止。
• 按激光笔所指方向通过那条过道。
• 不断重复如上两步。

为了研究这个策略，你有 $Q$ 个问题。对于每个问题，你被给定了一个整数 $K$，并且你从房间 $1$ 出发。你需要确定在通过了恰好 $K$ 条过道后你所处的房间是哪个。在每次询问后所有的激光笔都会转回最初的方向。

输入格式

第一行包含两个整数 $N$ 和 $Q$。

接下来 $N$ 行描述这个迷宫的构造，第 $i$ 行描述的是房间 $i$。每行第一个数 $k$ 表示与房间 $i$ 相连的过道数。接下来 $k$ 个整数 $c_1,c_2,\ldots,c_k$，按顺时针顺序给出通过这些过道可以到达的房间编号。最初，激光笔指向的过道是通向 $c_1$ 的那条。

最后 $Q$ 行描述询问。每行包含一个整数 $K$。

输出格式

按顺序输出 $Q$ 行，表示对询问的回答。

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

2
1
2
4
2
3

数据范围与提示

对于全部数据，$2\le N\le 8\times 10^5,1\le Q\le 8\times 10^5,1\le K\le 10^{15}$。

对于 $16\%$ 的分数，第 $i$ 条过道连接房间 $i$ 和 $i+1$。

对于另外 $16\%$ 的分数，$N,Q\le 2000$。

对于另外 $48\%$ 的分数，$Q=1$。