밀링 머신

팹랩은 레이저 커터나 3D 프린터 같은 컴퓨터 제어 장비로 거의 모든 것을 직접 만들어 보는 작은 개방형 공방이다. 어느 팹랩에 CNC 밀링 머신이 새로 들어왔다. 밀링 머신은 여러 공구로 공작물 표면에서 재료를 깎아내고, 컴퓨터 프로그램이 그 동작을 지시한다.

모양이 다른 공작물을 같은 밀링 프로그램에 차례로 넣으면 결과가 어떻게 되는지 알아보자. 문제를 단순하게 하려고 공작물은 구멍이 없는 2차원 도형으로 본다. 공작물의 너비는 $X$개의 열이고, 각 열마다 표면 높이가 하나씩 정해져 있다.

밀링 프로그램은 여러 단계로 이루어진다. 각 단계는 열마다 커터 헤드를 어느 깊이까지 내릴지 지정한다. 어떤 단계의 $i$번째 값이 $s_i$이면 그 단계에서 $i$번째 열의 커터 헤드는 높이 $Y - s_i$에 놓이고, 그 열에서 높이가 $Y - s_i$를 넘는 부분이 깎여 나간다. 깎는 깊이는 공작물의 현재 표면이 아니라 밀링 영역의 높이 $Y$를 기준으로 잰다.

모든 단계를 순서대로 적용한 뒤 각 공작물에 남는 표면 높이를 구하라.

첫째 줄에 공작물의 개수 $W$와 밀링 프로그램의 단계 수 $S$가 주어진다 ($1 \le W, S \le 10^4$).

둘째 줄에 공작물의 너비 $X$와 공작물이 가질 수 있는 최대 높이 $Y$가 주어진다 ($1 \le X, Y \le 100$).

다음 $W$개 줄에는 공작물이 한 줄에 하나씩 주어진다. 각 줄에는 음이 아닌 정수 $X$개가 있고, $i$번째 값은 $i$번째 열의 표면 높이다. 각 높이는 0 이상 $Y$ 이하이다.

다음 $S$개 줄에는 밀링 프로그램의 단계가 순서대로 한 줄에 하나씩 주어진다. 각 줄에는 음이 아닌 정수 $s_i$가 $X$개 있고 ($0 \le s_i \le Y$), 이 값은 그 열에서 깎아낼 양을 밀링 영역의 높이 $Y$를 기준으로 나타낸다.

공작물마다 한 줄씩, 남은 표면 높이 $X$개를 입력과 같은 순서로 공백 하나로 구분해 출력한다.

그림: 첫 번째 예제의 두 번째 공작물. 처음 상태에 이어 각 열을 깎아 나가는 과정을 보여준다. 밀링 프로그램의 값이 커터 헤드의 세로 위치를 정한다.