농부 존의 소들은 단것을 무척 좋아하며, 그중에서도 사탕 지팡이를 특히 좋아한다! 농부 존에게는 각각 초기 키가 정해진 소 \(N\)마리가 있고, 높이가 서로 다를 수 있는 사탕 지팡이 \(M\)개를 소들에게 먹이려고 한다. (\(1\le N,M\le 2\cdot 10^5\))

농부 존은 입력으로 주어진 순서대로 사탕 지팡이를 하나씩 소들에게 먹일 계획이다. 사탕 지팡이 하나를 먹일 때는 처음에 사탕 지팡이의 아래쪽 끝이 땅에 닿도록 매단다. 그러면 소들이 입력으로 주어진 순서대로 한 마리씩 줄을 서서 사탕 지팡이로 다가가며, 각 소는 자신의 키가 닿는 높이까지 먹는다. 더 높은 곳에는 닿을 수 없기 때문이다.

사탕 지팡이는 처음 매단 위치에 그대로 고정되어 있으며, 소들이 아래쪽 부분을 먹은 뒤에도 땅 쪽으로 내려오지 않는다. 사탕 지팡이의 남은 부분 중 가장 낮은 곳이 어떤 소의 키보다 높다면, 그 소는 자신의 차례에 아무것도 먹지 못할 수도 있다.

모든 소가 한 번씩 먹고 나면 각 소의 키는 자신이 먹은 사탕 지팡이의 길이만큼 자란다. 이후 농부 존은 다음 사탕 지팡이를 매달고 같은 과정을 반복한다. 다음 사탕 지팡이에서도 첫 번째 소부터 다시 먹기 시작한다.

입력

첫째 줄에 \(N\)과 \(M\)이 주어진다.

둘째 줄에 \(N\)마리 소의 초기 키가 주어진다. 각 키는 \([1,10^9]\) 범위에 있다.

셋째 줄에 \(M\)개 사탕 지팡이의 높이가 주어진다. 각 높이는 \([1,10^9]\) 범위에 있다.

출력

각 소의 최종 키를 입력으로 주어진 순서대로 한 줄에 하나씩 출력한다.

이 문제에서 다루는 정수의 크기가 클 수 있으므로 64비트 정수 자료형을 사용해야 할 수 있다. 예를 들어 C/C++에서는 long long을 사용할 수 있다.

예제 입력

3 2
3 2 5
6 1

예제 출력

7
2
7

첫 번째 사탕 지팡이의 높이는 \(6\)이다.

1. 첫 번째 소는 첫 번째 사탕 지팡이를 높이 \(3\)까지 먹는다. 그러면 남은 부분은 높이 \([3,6]\)에 놓인다.
2. 두 번째 소는 첫 번째 사탕 지팡이의 남은 부분을 먹을 만큼 키가 크지 않다.
3. 세 번째 소는 첫 번째 사탕 지팡이를 추가로 길이 \(2\)만큼 먹는다. 높이 \([5,6]\)에 놓인 나머지 부분은 먹히지 않는다.

이후 각 소가 자신이 먹은 길이만큼 자라므로 소들의 키는 \([3+3,2+0,5+2]=[6,2,7]\)이 된다.

두 번째 사탕 지팡이의 높이는 \(1\)이며, 첫 번째 소가 전부 먹는다.

서브태스크

출처

USACO 2023 December Contest, Bronze, Problem 1. Candy Cane Feast