Logo Universal Online Judge

UOJ

时间限制:4 s 空间限制:512 MB
Statistics

Sample

Description

《十步万度》是一款逻辑型解谜游戏,玩法很简单,点击指针就可以让指针顺时针旋 转 $90$ 度,同时指针指向的方向的相邻指针也会顺时针旋转一次。当你小心翼翼地调整 完所有指针,并走下最后一步,就能看到多个指针互相影响,最后引发蝴蝶效应并达到 $10000$ 度的旋转。

你觉得局限于每个指针只能带动至多四个相邻指针太无趣了,于是创造了一关有 $n$ 个指针的游戏,并规定第 $i$ 个指针有 $k_i\ge 1$ 个指针与其相邻,于是每次激活指针 $i$ 就会 使其顺时针转向下一个与其相邻的指针。

为了简化规则,你又规定,如果把相邻关系看作无向边,把指针看作结点,则其构成 一棵 $n$ 个结点,$n−1$ 条边的树。也就是说,相邻是双向的关系,且满足 $\sum n _{i=1}^n k_i = 2(n−1)$,不存在由相邻关系构成的环。

具体地,游戏流程如下:

  1. 初始激活 $1$ 号指针。
  2. 将当前激活的指针 $i$ 顺时针转向下一个与其相邻的指针 $j$。
  3. 取消指针 $i$ 的激活状态,激活指针 $j$。
  4. 回到步骤 $2$。

显然这个游戏不会终止,每个时刻也只会有一个指针处于激活状态,于是你想知道 第 $x$ 次执行步骤 $3$ 后,被激活的指针编号。你觉得这个问题太简单了,于是提了 $q$ 个这 样的问题。请注意,每个问题是独立的,也就是每次执行步骤 $1$ 前都会把所有指针恢复 初始状态。

Input

第一行两个整数 $n, q$。

接下来 $n$ 行,第 $i$ 行给出与指针 $i$ 相邻的指针信息。首先一个整数 $k_i$ 表示指针 $i$ 相 邻的指针数量,接下来 $k_i$ 个整数 $v_{i,1}, v_{i,2},\cdots , v_{i,k_i}$ 依次以顺时针顺序表示与指针 $i$ 相邻 的指针编号。初始指针 $i$ 指向指针 $v_{i,1}$。

接下来 $q$ 行,每行一个正整数 $x$ 表示询问参数。

Output

共 $q$ 行,每行一个整数表示对应询问的答案。

Range

$n, q\le 8\times 10^5, 1\le x\le 10^{15}, \sum k_i = 2(n - 1), k_i\ge 1$