예방 접종 작전

모든 백신을 전 세계 인구에게 제공하는 것은 여러 측면에서 복잡한 문제이다. Ñambi는 배송을 최적화하는 일을 이끌고 있다. 접근 장벽을 가능한 한 낮추기 위해, 자동화된 로봇이 환자의 집으로 직접 백신을 배송하고 접종하도록 하려고 한다.

현재 설계에서 Ñambi가 만드는 로봇은 서쪽에서 동쪽으로 뻗은 하나의 거리에서 작동한다. 따라서 로봇은 '$x$미터 이동'이라는 하나의 명령을 받는다. $x$이 양수이면 로봇은 동쪽으로 $x$미터 이동한다. $x$이 음수이면 로봇은 서쪽으로 $-x$미터 이동한다.

하루가 시작될 때 로봇에는 그날 실시해야 하는 모든 예방 접종에 관한 정보가 입력된다. 각 정보는 수거할 백신의 현재 위치와 백신을 전달받아야 하는 환자의 위치로 구성된다. 각 백신은 한 환자를 위해 맞춤 제작된다. 물론 백신의 배송 위치는 절대로 그 백신의 수거 위치와 같지 않다. 로봇은 백신을 환자에게 배송하기 전에 수거해야 한다.

로봇은 백신의 수거 위치를 처음 통과할 때 백신을 자동으로 수거하여 화물칸에 싣도록 프로그래밍되어 있다. 또한 백신을 이미 수거했다면 수령인의 위치를 통과하는 즉시 백신을 배송하도록 프로그래밍되어 있다. Ñambi는 각 이동 명령 후 몇 건의 예방 접종이 이루어지는지 추적하려고 한다. 백신이 배송되면 예방 접종이 이루어진다. 백신은 이전 명령 중 어느 하나에서 수거되었을 수도 있고, 같은 명령 중 배송 전에 수거되었을 수도 있음에 유의하라.

다음 그림은 가능한 한 가지 상황(아래의 예제 케이스 #1)을 보여 준다. 웃는 얼굴은 로봇의 초기 위치를 나타내고, 긴 검은 선은 거리이다. 선 위의 표시는 수거 위치이고 선 아래의 표시는 배송 위치이다. 마지막으로 아래의 화살표는 로봇이 수행하는 이동을 위에서 아래의 순서로 나타내며, 각 이동 중 완료되는 배송 건수가 표시되어 있다.

각 이동 중에는 다음과 같은 일이 순서대로 일어난다.

• 이동 1. 로봇은 백신 $5$와 $1$를 수거한 다음 백신 $1$를 배송하고, 이동이 끝나는 순간 백신 $3$를 수거한다. 로봇이 백신 $3$의 배송 위치를 통과하지만, 이는 백신 $3$를 수거하기 전에 일어나므로 배송할 수 없음에 유의하라.

• 이동 2. 로봇은 백신 $1$와 $4$의 배송 위치를 통과한다. 하지만 백신 $1$는 이미 배송되었고 백신 $4$는 수거되지 않았으므로, 완료되는 예방 접종은 없다.

• 이동 3. 로봇은 백신 $3$를 배송한다.

• 이동 4. 로봇은 백신 $2$를 수거하고, 백신 $5$를 배송하고, 백신 $4$를 수거한다.

백신 $2$와 $4$는 수거되었지만 배송되지 않았음에 유의하라. 백신 $2$의 배송 위치에는 한 번도 도달하지 않았고, 백신 $4$의 배송 위치에는 그 백신을 수거한 뒤에 도달하지 않았기 때문이다.

실시해야 할 예방 접종의 목록과 로봇이 순서대로 실행할 이동 명령의 목록이 주어질 때, 각 명령 후 완료된 예방 접종 수를 계산하라.

제한

메모리 제한: 2 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $1 \le \mathbf{P_i} \le 10^9$. 모든 $i$에 대해 $1 \le \mathbf{D_i} \le 10^9$. 모든 $i$에 대해 $\mathbf{P_i} \neq \mathbf{D_i}$. 모든 $j$에 대해 $-10^9 \le \mathbf{X_j} \le 10^9$. 모든 $j$에 대해 $\mathbf{X_j} \ne 0$.

테스트 세트 1 (Visible Verdict)

시간 제한: 20초. $1 \le \mathbf{V} \le 100$. $1 \le \mathbf{M} \le 100$.

테스트 세트 2 (Hidden Verdict)

시간 제한: 40초. $1 \le \mathbf{V} \le 10^5$. $1 \le \mathbf{M} \le 10^5$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 $4$개의 줄로 구성된다. 테스트 케이스의 첫 번째 줄에는 예방 접종 수와 이동 명령 수를 나타내는 $2$개의 정수 $\mathbf{V}$와 $\mathbf{M}$이 주어진다.

테스트 케이스의 두 번째 줄에는 $\mathbf{V}$개의 정수 $\mathbf{P_1}, \mathbf{P_2}, \dots, \mathbf{P_V}$가 주어지며, 이는 $i$번째 백신을 로봇의 초기 위치에서 정확히 동쪽으로 $\mathbf{P_i}$미터 떨어진 곳에서 수거해야 함을 나타낸다. 여러 백신의 수거 위치가 같을 수 있음에 유의하라.

세 번째 줄에는 $\mathbf{V}$개의 정수 $\mathbf{D_1}, \mathbf{D_2}, \dots, \mathbf{D_V}$가 주어지며, 이는 $i$번째 백신을 로봇의 초기 위치에서 정확히 동쪽으로 $\mathbf{D_i}$미터 떨어진 곳에 배송해야 함을 나타낸다. 여러 백신의 배송 위치가 같을 수 있음에 유의하라.

테스트 케이스의 마지막 줄에는 $\mathbf{M}$개의 정수 $\mathbf{X_1}, \mathbf{X_2}, \dots, \mathbf{X_M}$가 주어진다. $\mathbf{X_j}$의 절댓값은 $j$번째 이동 명령에서 로봇이 이동해야 하는 미터 수이다. $\mathbf{X_j}$이 양수이면 $j$번째 이동은 동쪽을 향해야 하고, 음수이면 서쪽을 향해야 한다. 예방 접종은 입력의 번호와 다른 순서로 일어날 수 있지만, 이동 명령은 주어진 순서대로 실행됨에 유의하라.

각 테스트 케이스마다 Case #$x$: $y_1 ~ y_2 ~ \dots ~ y_{\mathbf{M}}$를 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y_j$은 주어진 $j$번째 이동 명령을 수행하는 동안 완료된 예방 접종 수이다.

예제 케이스 #1은 문제 설명에서 설명하고 그림으로 나타낸 케이스이다.

예제 케이스 #2과 예제 케이스 #3에서는 수거 장소를 먼저 방문할 때에만 같은 이동 중에 백신을 수거하고 배송할 수 있음에 유의하라. 또한 이동이 끝나는 정확한 순간에도 수거와 배송이 가능함에 유의하라.

예제 케이스 #4에서 로봇은 서쪽으로 $987654321$미터씩 다섯 번 이동하고, 그다음 동쪽으로 $987654321$미터씩 네 번 이동한 뒤, 동쪽으로 $987654323$미터 이동한다. 유일한 수거와 배송은 모두 마지막 이동에서 이루어진다. 명령의 이동 거리가 매우 극단적일 수 있으므로, 로봇이 어느 시점에는 초기 위치에서 서쪽이나 동쪽으로 매우 멀리 떨어질 수 있음에 유의하라.