플랫폼 게임

Bajtazar는 새 컴퓨터로 플랫폼 게임을 하고 있다. 보드는 위아래로 쌓인 $n$개의 플랫폼으로 이루어져 있고, 플레이어 캐릭터는 그 위를 움직인다. 각 플랫폼의 길이는 $X$이므로 캐릭터의 위치는 $(i, x)$ 쌍으로 나타낼 수 있다. 여기서 $i$는 위에서부터 센 플랫폼 번호이고, $x$는 플랫폼 왼쪽 끝에서 떨어진 거리이다 ($1 \le i \le n$, $1 \le x \le X$). 캐릭터는 어떤 플랫폼의 왼쪽 끝에서 출발해 아무 플랫폼의 오른쪽 끝에 도달해야 한다. 캐릭터는 오른쪽으로만 움직일 수 있다.

쉽게 통과하지 못하도록 일부 위치에 구멍이 있다. 캐릭터는 구멍을 뛰어넘을 수도 있고, 구멍을 이용해 아래 플랫폼으로 떨어지거나 위 플랫폼으로 뛰어오를 수도 있다. 보드의 어떤 두 구멍도 바로 위아래에 있지 않고, 바로 옆에 붙어 있지도 않다.

캐릭터가 $(i, x)$에 있을 때 가능한 이동은 다음과 같다.

• F 키: 위치 $(i, x + 1)$에 구멍이 없으면 $(i, x + 1)$로 이동한다.
• F 키: $i \neq n$이고 $(i, x + 1)$에 구멍이 있으면 $(i + 1, x + 1)$로 떨어진다.
• A 키: $(i, x + 1)$에 구멍이 있으면 $(i, x + 2)$로 뛰어넘는다.
• B 키: $i \neq 1$이고 $(i - 1, x)$에 구멍이 있으면 $(i - 1, x + 1)$로 뛰어오른다.

시작 위치가 주어졌을 때, 어떤 플랫폼의 오른쪽 끝에든 도달하는 데 필요한 A 키와 B 키의 최소 입력 횟수를 구하라.

첫 줄에는 세 정수 $n$, $X$, $z$가 주어진다 ($1 \le n \le 100000$, $1 \le X \le 10^9$, $1 \le z \le 100000$). 각각 플랫폼의 개수, 플랫폼의 길이, 질의의 개수이다.

다음 $n$개 줄에는 플랫폼이 주어진다. $i$번째 줄은 플랫폼 $i$의 구멍 개수를 나타내는 음이 아닌 정수 $k_i$로 시작하고, 이어서 $k_i$개의 증가하는 정수가 나온다. 이 정수들은 왼쪽 끝에서 각 구멍까지의 거리이다. 플랫폼의 양 끝에는 구멍이 없고, 같은 플랫폼에서 구멍끼리는 서로 인접하지 않는다. 연속한 두 플랫폼에서는 왼쪽 끝으로부터 같은 거리에 있는 구멍이 없다. 구멍의 총 개수는 2,000,000 이하이다.

다음 $z$개 줄에는 각각 정수 $p_j$ ($1 \le p_j \le n$)가 하나씩 주어진다.

$j$번째 줄에는 $(p_j, 1)$에서 출발해 두 번째 좌표가 $X$인 위치, 즉 플랫폼의 오른쪽 끝에 도달하는 데 필요한 A 키와 B 키의 최소 입력 횟수를 출력한다.

$(3, 1)$에서 출발하면 F 키를 두 번 눌러 $(3, 3)$에 도달할 수 있다. 그다음 B 키로 $(2, 4)$에 뛰어오르고, F 키를 다섯 번 누르면 그 사이에 한 번 아래로 떨어져 $(3, 9)$에 도달한다.

$(2, 1)$에서 출발하면 F 키, A 키, 그리고 F 키를 다섯 번 순서대로 누를 수 있다.

$(1, 1)$에서 출발하면 F 키만 계속 누르면 된다.