32718번 - 우선순위 큐와 시뮬레이션

$N$개의 원소가 들어 있는 우선순위 큐가 있다. 해당 큐의 top은 큐에 존재하는 원소의 최댓값으로 정의한다.

우선순위 큐를 이용해 시뮬레이션하려고 할 때, $i$번째 쿼리는 아래의 순서로 이루어진다.

• 우선순위 큐의 모든 원소에 대해 $A_i$를 더한다.
• 모든 원소에 대해 정수 $K$로 나눈 나머지를 취한다.
• top을 출력한다.

$T$개의 쿼리에 대한 결과를 구해보자.

첫째 줄에 우선순위 큐에 들어 있는 원소의 개수 $N$, 쿼리에서 사용하는 정수 $K$, 쿼리의 개수 $T$가 공백으로 구분되어 주어진다. $(1\leq N, T\leq 200,000;$ $2\leq K\leq 10^{9})$

둘째 줄에 우선순위 큐에 들어 있는 원소 $Q_i$가 공백으로 구분되어 주어진다. $\left(1\leq Q_i\leq 10^{9}\right)$

셋째 줄에 $i$번째 쿼리에 더하는 수 $A_i$가 공백으로 구분되어 주어진다. $\left(1\leq A_i\leq 10^{9}\right)$

$T$개의 쿼리를 수행한 결과를 순서대로 공백으로 구분하여 출력한다.