예방접종 작업

모든 백신을 전 세계 인구에게 전달하는 일은 여러 면에서 복잡한 문제다. Ñambi는 배송을 최적화하는 일을 이끌고 있다. 접근 장벽을 최대한 낮추려고 그녀는 환자의 집에서 백신을 직접 전달하고 접종하는 로봇을 설계하고 있다.

현재 설계에서 로봇은 서쪽에서 동쪽으로 뻗은 하나의 도로에서 작업한다. 로봇이 받는 명령은 'move $x$ meters' 하나뿐이다. $x$가 양수면 로봇은 동쪽으로 $x$미터 이동하고, 음수면 서쪽으로 $-x$미터 이동한다.

하루를 시작할 때 로봇에는 그날 수행해야 할 모든 예방접종 정보가 입력된다. 각 접종에는 백신을 가져올 위치인 수거 위치와, 백신을 받을 환자가 있는 배송 위치가 있다. 각 백신은 환자 한 명을 위해 맞춤 제작된다. 배송 위치가 수거 위치와 같은 경우는 없다. 로봇은 백신을 배송하기 전에 반드시 수거해야 한다.

로봇은 백신의 수거 위치를 처음 지날 때 그 백신을 자동으로 수거해 싣는다. 이미 수거한 백신의 배송 위치를 지나면 곧바로 배송한다. 백신 배송이 끝날 때마다 접종이 한 건 완료된다. 수거는 이전 명령 중에 이루어질 수도 있고, 같은 명령 안에서 배송 전에 이루어질 수도 있다. Ñambi는 명령마다 접종이 몇 건 완료되는지 기록하려 한다.

아래 그림은 가능한 시나리오 하나(예시 #1)를 보여 준다. 얼굴 모양은 로봇의 시작 위치이고, 긴 검은 선은 도로다. 선 위의 표시는 수거 위치, 아래 표시는 배송 위치다. 선 아래의 화살표는 위에서 아래 순서로 이루어지는 이동을 나타내며, 각 이동에서 완료된 배송 수가 표시되어 있다.

각 이동에서 일어나는 일은 다음과 같다.

• 이동 1. 로봇은 백신 5와 1을 수거하고 백신 1을 배송한다. 이동이 끝나는 순간 백신 3을 수거한다. 로봇은 백신 3의 배송 위치를 수거 전에 지나므로 이 백신은 배송할 수 없다.
• 이동 2. 로봇은 백신 1과 4의 배송 위치를 지난다. 백신 1은 이미 배송되었고 백신 4는 아직 수거되지 않았으므로 완료된 접종은 없다.
• 이동 3. 로봇은 백신 3을 배송한다.
• 이동 4. 로봇은 백신 2를 수거하고, 백신 5를 배송하고, 백신 4를 수거한다.

백신 2와 4는 수거했지만 배송하지 못했다. 백신 2의 배송 위치는 한 번도 도달하지 않았고, 백신 4는 수거 후 배송 위치를 지나지 않았다.

접종 목록과 이동 명령 목록이 주어지면 로봇은 명령을 순서대로 실행한다. 각 명령 뒤에 완료되는 접종 수를 구하라.

첫 줄에는 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 네 줄로 이루어진다.

테스트 케이스의 첫 줄에는 접종 수 $V$와 이동 명령 수 $M$이 정수 두 개로 주어진다.

둘째 줄에는 $V$개의 정수 $P_1, P_2, \dots, P_V$가 주어진다. $i$번째 백신은 로봇의 시작 위치에서 정확히 $P_i$미터 동쪽에서 수거해야 한다. 여러 백신이 같은 수거 위치를 가질 수 있다.

셋째 줄에는 $V$개의 정수 $D_1, D_2, \dots, D_V$가 주어진다. $i$번째 백신은 로봇의 시작 위치에서 정확히 $D_i$미터 동쪽에서 배송해야 한다. 여러 백신이 같은 배송 위치를 가질 수 있다.

넷째 줄에는 $M$개의 정수 $X_1, X_2, \dots, X_M$이 주어진다. $X_j$의 절댓값은 $j$번째 이동 명령에서 로봇이 움직이는 거리(미터)다. $X_j$가 양수면 동쪽으로, 음수면 서쪽으로 움직인다. 접종은 입력 번호 순서와 다른 순서로 일어날 수 있지만, 이동 명령은 주어진 순서대로 실행된다.

각 테스트 케이스마다 Case #x: y1 y2 ... yM 형식으로 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y_j$는 $j$번째 이동 명령 동안 완료된 접종 수다.

• $1 \le T \le 100$.
• 모든 $i$에 대해 $1 \le P_i \le 10^9$.
• 모든 $i$에 대해 $1 \le D_i \le 10^9$.
• 모든 $i$에 대해 $P_i \neq D_i$.
• 모든 $j$에 대해 $-10^9 \le X_j \le 10^9$.
• 모든 $j$에 대해 $X_j \ne 0$.

예시 #1은 문제 설명에서 풀이와 그림으로 설명한 케이스다.

예시 #2와 #3에서는 수거 위치를 먼저 지나야만 같은 이동 안에서 수거와 배송을 모두 할 수 있다는 점에 주의하라. 또 이동이 끝나는 바로 그 순간에 수거와 배송이 일어날 수도 있다.

예시 #4에서 로봇은 서쪽으로 987654321미터를 다섯 번, 동쪽으로 987654321미터를 네 번, 그다음 동쪽으로 987654323미터를 이동한다. 유일한 수거와 배송은 모두 마지막 이동에서 일어난다. 명령 값이 매우 크므로 로봇은 시작 위치에서 동쪽이나 서쪽으로 매우 멀리 떨어질 수 있다.