사탕 막대 잔치

Farmer John의 소들은 사탕 막대를 특히 좋아합니다. FJ에게는 총 $N$마리의 소가 있고, 각 소의 초기 키는 정해져 있습니다. FJ는 키가 제각각인 사탕 막대 $M$개를 이 소들에게 먹이려고 합니다. ($1\le N,M\le 2\cdot 10^5$)

FJ는 입력으로 주어진 순서대로 사탕 막대를 하나씩 먹입니다. 막대를 먹이려면 아랫부분이 땅에 막 닿도록 막대를 매답니다. 그다음 소들이 입력 순서대로 한 줄로 서서 막대 앞으로 나아갑니다. 각 소는 자기 키만큼 막대의 아래쪽을 먹습니다. 그 이상은 닿지 않습니다. 막대는 처음 매단 위치에 그대로 떠 있으며, 소들이 아래쪽을 먹어도 내려오지 않습니다. 막대의 아랫부분이 이미 소의 키보다 높으면, 그 소는 자기 차례에 아무것도 먹지 못합니다.

모든 소의 차례가 끝나면 각 소는 먹은 만큼 자랍니다. 그다음 FJ가 다음 사탕 막대를 매달고, 소들은 같은 과정을 반복합니다. 이번에도 1번 소가 가장 먼저 먹습니다.

첫 줄에 $N$과 $M$이 주어집니다. 다음 줄에는 $N$마리 소의 초기 키가 주어집니다. 각 키는 $[1,10^9]$ 범위의 정수입니다. 다음 줄에는 $M$개 사탕 막대의 키가 주어집니다. 각 키는 $[1,10^9]$ 범위의 정수입니다.

$N$마리 소의 최종 키를 한 줄에 하나씩 출력합니다.

값이 매우 커질 수 있으므로 64비트 정수형(C/C++의 "long long" 등)을 사용해야 합니다.

첫 번째 사탕 막대의 키는 6입니다.

1. 1번 소가 높이 3까지 막대를 먹습니다. 남은 부분은 높이 $[3,6]$을 차지합니다.
2. 2번 소는 키가 작아서 남은 부분을 전혀 먹지 못합니다.
3. 3번 소가 두 칸을 더 먹습니다. 높이 $[5,6]$ 부분은 먹히지 않고 남습니다.

그다음 각 소는 먹은 만큼 자라서 키가 $[3+3, 2+0, 5+2]=[6, 2, 7]$이 됩니다. 두 번째 사탕 막대의 키는 1이고, 1번 소가 전부 먹습니다.