Background

This problem is translated from XXVIII Olimpiada Informatyczna – Stage I Gra platformowa。

Problem Description

Bajtazar is playing a game on his new computer.

In this game, there are $n$ platform levels, numbered from $1$ to $n$ from top to bottom. The player needs to move between these platforms. Each platform has length $X$, so the player’s current position can be described by a pair $(i,x)$, where $i$ is the platform level and $x$ is the position on that platform ($1$ is the left end, and $X$ is the right end).

The player starts at the left end of some platform. The goal is to reach the right end of any platform, and the player can only move to the right. To make the game harder, there are holes at some positions on the platforms. In that case, the player may choose a jump operation to directly jump over the hole, or go through the hole to the platform above or below. It is guaranteed that there are no two holes adjacent horizontally or vertically.

More specifically, suppose the player is currently at $(i,x)$. The player can perform the following operations:

• $\texttt{F}$ operation: If there is no hole at $(i,x+1)$, the player moves to $(i,x+1)$; otherwise, the player moves to $(i+1,x+1)$.
• $\texttt{A}$ operation: If there is a hole at $(i,x+1)$, the player moves to $(i,x+2)$.
• $\texttt{B}$ operation: If there is a hole at $(i-1,x)$, the player moves to $(i-1,x+1)$.

Now Bajtazar wants to finish the game using as few jump operations as possible (i.e., $\texttt{A}$ and $\texttt{B}$ operations). Can you help him accomplish this task?

Input Format

The first line contains three integers $n,X,z$, meaning there are $n$ platform levels, each platform has length $X$, and there are $z$ queries.

The next $n$ lines describe the platforms. Line $i$ starts with an integer $k_i$, meaning the $i$-th platform has $k_i$ holes. Then follow $k_i$ increasing integers giving the positions of the holes on that platform. The input guarantees that there are no holes at the left end or the right end of any platform, and there are no two holes adjacent horizontally or vertically.

The next $z$ lines each contain an integer $p_j$, meaning that in the $j$-th query, the player starts from the left end of platform level $p_j$.

Output Format

For the $j$-th query, output one integer on the $j$-th line: the minimum number of $\texttt{A}$ and $\texttt{B}$ operations needed to start from $(p_j,1)$ and reach the right end of any platform.

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

1
1
0

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

Hint

[Sample Explanation 1]:

The figure above shows an optimal plan for the first query of Sample $1$: the player first performs $\texttt{F}$ twice to reach $(3,3)$, then performs $\texttt{B}$ once to reach $(2,4)$, then performs $\texttt{F}$ five times to reach $(3,9)$.

For the second query, the optimal plan is to perform $\texttt{F}$ once, then $\texttt{A}$ once, and finally $\texttt{F}$ five times.

For the third query, the optimal plan is to perform $\texttt{F}$ eight times in a row.

[Constraints]:

All testdata satisfy: $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$.

Translated by ChatGPT 5