「POI 2020/2021 R1」Gra platformowa

题目描述

Bajtazar 正在他的新电脑上玩游戏。

在这个游戏里，有 $n$ 层平台，自上而下分别编号为 $1$ 至 $n$，玩家需要在这些平台之间移动。每层平台的长度为 $X$，因此可以用数对 $(i,x)$ 描述玩家当前的位置，其中 $i$ 表示玩家在第几层平台，$x$ 表示玩家在当前平台的位置（最左端为 $1$，最右端为 $X$）。

玩家从某个平台的最左端开始，游戏的目标是到达任意一个平台的最右端，且玩家只能向右移动。为了增大难度，在平台的一些地方会有洞，这种情况下，玩家可以选择跳跃操作，直接跳过这个洞，也可以通过该洞前往上面或下面的平台，保证不存在两个在水平方向上或竖直方向上相邻的洞。

更具体地说，假如玩家当前的位置为 $(i,x)$，玩家可以执行如下几种操作：

• $\texttt{F}$ 操作：当 $(i,x+1)$ 没有洞时，玩家将会移动到 $(i,x+1)$；否则，玩家将会移动到 $(i+1,x+1)$。
• $\texttt{A}$ 操作：当 $(i,x+1)$ 有洞时，玩家将会移动到 $(i,x+2)$。
• $\texttt{B}$ 操作：当 $(i-1,x)$ 有洞时，玩家将会移动到 $(i-1,x+1)$。

现在 Bajtazar 希望执行最少的跳跃操作（即 $\texttt{A}$ 操作和 $\texttt{B}$ 操作）完成游戏。你能帮他完成这个任务吗？

输入格式

输入第一行三个整数 $n, X, z$，表示一共有 $n$ 层平台，每层平台的长度为 $X$，询问的次数为 $z$。

接下来 $n$ 行，第 $i$ 行描述第 $i$ 层平台的信息。每行开头一个整数 $k_i$，表示该层平台有 $k_i$ 个洞。接下来 $k_i$ 个递增的整数，给出该层每个洞的位置。数据保证任何一个平台的最左端和最右端不存在洞，且不存在两个在水平方向上或竖直方向上相邻的洞。

接下来 $z$ 行，每行包含一个整数 $p_j$，表示在第 $j$ 组询问中，玩家需要从第 $p_j$ 层平台的最左端出发。

输出格式

对于第 $j$ 组询问，请在第 $j$ 行输出一个整数，表示从 $(p_j,1)$ 出发，抵达任意一个平台的最右端需要执行的 $\texttt{A}$ 操作和 $\texttt{B}$ 操作的最小次数。

样例 1

输入

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

输出

1
1
0

解释：上图给出了样例 1 的第一个询问对应的最优方案：玩家先执行两次 $\texttt{F}$ 操作到达 $(3,3)$，再执行一次 $\texttt{B}$ 操作到达 $(2,4)$，再执行五次 $\texttt{F}$ 操作到达 $(3,9)$。

对于第二个询问，最优方案是执行一次 $\texttt{F}$ 操作，再执行一次 $\texttt{A}$ 操作，最后执行五次 $\texttt{F}$ 操作。

对于第三个询问，最优方案是连续执行八次 $\texttt{F}$ 操作。

样例 2

输入

5 20 5
1 16
3 7 15 18
3 6 9 14
3 3 8 11
2 2 5
1
2
3
4
5

输出

0
0
0
1
2

样例 3

见附加文件下 gra2.in 和 gra2.out。

该样例中 $n=50$，且所有孔位于一条对角线上。

样例 4

见附加文件下 gra3.in 和 gra3.out。

该样例中 $n=50$，且所有孔形成了国际象棋棋盘的图案。

数据范围与提示

所有测试点均满足：

• $1 \leq n \leq 10^5$
• $1 \leq X \leq 10^9$
• $1 \leq z \leq 10^5$
• $\sum k \leq 2 \times 10^6$

子任务

子任务编号	约束	分值
1	$z \leq 5$，$n \times X \leq 10^6$	30
2	$z \leq 5$	50
3	无附加约束	20