Bajtazar is playing a platform game on his new computer. The game board consists of $n$ platforms arranged one below another, on which the player's character can move. Each platform has a length $X$, so the character's position can be described by a pair of numbers $(i, x)$, where $i$ is the platform number (counting from the top) and $x$ is the distance from the left end of the platform ($1 \le i \le n$, $1 \le x \le X$). The character starts at the left end of a certain platform and must reach the right end of any platform. The character can only move to the right.

To make things not so simple, there are holes in some places on the platforms that hinder the player's movement. The character can jump over them or use them to fall/jump onto platforms located below/above. There are no two holes directly below each other anywhere on the board, nor directly next to each other.

Formally, if the character is at position $(i, x)$, the possible moves are as follows: Using key F, the character can move to position $(i, x + 1)$, if there is no hole there. Using key F, the character can fall to position $(i + 1, x + 1)$, if $i \neq n$ and there is a hole at position $(i, x + 1)$. Using key A, the character can jump to position $(i, x + 2)$, if there is a hole at position $(i, x + 1)$. Using key B, the character can jump to position $(i - 1, x + 1)$, if $i \neq 1$ and there is a hole at position $(i - 1, x)$.

Knowing the player's starting position, calculate the minimum number of jumps (i.e., presses of keys A and B) required to reach the right end of any platform.

Input

The first line of input contains three integers $n$, $X$, and $z$ ($1 \le n \le 100\,000$, $1 \le X \le 10^9$, $1 \le z \le 100\,000$), representing the number of platforms, the length of the platforms, and the number of queries.

The next $n$ lines describe the platforms; the $i$-th line starts with a non-negative integer $k_i$ representing the number of holes on the $i$-th platform, followed by an increasing sequence of $k_i$ integers representing the distances of these holes from the left end of the platform. On no platform are there holes at the left or right ends, holes are not adjacent to each other, and on consecutively following platforms, there are no holes having the same distance from the left end of their platform. The total number of holes is no more than $2\,000\,000$.

The next $z$ lines contain the queries; the $j$-th line contains an integer $p_j$ ($1 \le p_j \le n$).

Output

Your program should output $z$ lines; the $j$-th line should contain an integer, which is the answer to the question: what is the minimum number of presses of keys A and B needed to get from position $(p_j, 1)$ to a position whose second coordinate is $X$.

Examples

Input 1

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

Output 1

1
1
0

Note

Explanation of the example: The player, starting from position $(3, 1)$, can press the F key twice to get to position $(3, 3)$, then use the B key to jump to position $(2, 4)$, and after using the F key five times, falling lower in the process, they will end up at position $(3, 9)$. Starting from position $(2, 1)$, one can press the F key, then A, and then F five times. Starting from position $(1, 1)$, it is enough to press only the F key.

Subtasks