{"raw_statement":[{"iden":"background","content":"**题目译自 [XXVIII Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi28-1/dashboard/) [Gra platformowa](https://sio2.mimuw.edu.pl/c/oi28-1/p/gra/)。**"},{"iden":"statement","content":"Bajtazar 正在他的新电脑上玩游戏。\n\n在这个游戏里，有 $n$ 层平台，自上而下分别编号为 $1$ 至 $n$，玩家需要在这些平台之间移动。每层平台的长度为 $X$，因此可以用数对 $(i,x)$ 描述玩家当前的位置，其中 $i$ 表示玩家在第几层平台，$x$ 表示玩家在当前平台的位置（最左端为 $1$，最右端为 $X$）。\n\n玩家从某个平台的最左端开始，游戏的目标是到达任意一个平台的最右端，且玩家只能向右移动。为了增大难度，在平台的一些地方会有洞，这种情况下，玩家可以选择跳跃操作，直接跳过这个洞，也可以通过该洞前往上面或下面的平台，保证不存在两个在水平方向上或竖直方向上相邻的洞。\n\n更具体地说，假如玩家当前的位置为 $(i,x)$，玩家可以执行如下几种操作：\n\n- $\\texttt{F}$ 操作：当 $(i,x+1)$ 没有洞时，玩家将会移动到 $(i,x+1)$；否则，玩家将会移动到 $(i+1,x+1)$。\n- $\\texttt{A}$ 操作：当 $(i,x+1)$ 有洞时，玩家将会移动到 $(i,x+2)$。\n- $\\texttt{B}$ 操作：当 $(i-1,x)$ 有洞时，玩家将会移动到 $(i-1,x+1)$。\n\n现在 Bajtazar 希望执行最少的跳跃操作（即 $\\texttt{A}$ 操作和 $\\texttt{B}$ 操作）完成游戏。你能帮他完成这个任务吗？"},{"iden":"input","content":"输入第一行三个整数 $n,X,z$，表示一共有 $n$ 层平台，每层平台的长度为 $X$，询问的次数为 $z$。\n\n接下来 $n$ 行，第 $i$ 行描述第 $i$ 层平台的信息。每行开头一个整数 $k_i$，表示该层平台有 $k_i$ 个洞。接下来 $k_i$ 个递增的整数，给出该层每个洞的位置。数据保证任何一个平台的最左端和最右端不存在洞，且不存在两个在水平方向上或竖直方向上相邻的洞。\n\n接下来 $z$ 行，每行包含一个整数 $p_j$，表示在第 $j$ 组询问中，玩家需要从第 $p_j$ 层平台的最左端出发。"},{"iden":"output","content":"对于第 $j$ 组询问，请在第 $j$ 行输出一个整数，表示从 $(p_j,1)$ 出发，抵达任意一个平台的最右端需要执行的 $\\texttt{A}$ 操作和 $\\texttt{B}$ 操作的最小次数。"},{"iden":"note","content":"【样例解释1】：\n\n![pp5jnwd.png](https://s1.ax1x.com/2023/04/05/pp5jnwd.png)\n\n上图给出了样例 $1$ 的第一个询问对应的最优方案：玩家先执行两次 $\\texttt{F}$ 操作到达 $(3,3)$，再执行一次 $\\texttt{B}$ 操作到达 $(2,4)$，再执行五次 $\\texttt{F}$ 操作到达 $(3,9)$。\n\n对于第二个询问，最优方案是执行一次 $\\texttt{F}$ 操作，再执行一次 $\\texttt{A}$ 操作，最后执行五次 $\\texttt{F}$ 操作。\n\n对于第三个询问，最优方案是连续执行八次 $\\texttt{F}$ 操作。\n\n【数据范围】：\n\n所有测试点均满足：$1 \\leq n \\leq 10^5$，$1 \\leq X \\leq 10^9$，$1 \\leq z \\leq 10^5$，$\\sum k\\le 2\\times 10^6$。\n\n| 子任务编号 | 约束 | 分值 |\n| :-: | :-: | :-: |\n|$0$|样例|$0$|\n| $1$| $z \\leq 5$，$n\\times X \\leq 10^6$ | $30$ |\n| $2$| $z \\leq 5$| $50$ |\n|$3$| 无附加约束|$20$|"}],"translated_statement":null,"sample_group":[["3 9 3\n1 6\n2 3 8\n2 5 7\n3\n2\n1","1\n1\n0"],["5 20 5\n1 16\n3 7 15 18\n3 6 9 14\n3 3 8 11\n2 2 5\n1\n2\n3\n4\n5","0\n0\n0\n1\n2"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}