우선순위 큐와 시뮬레이션

면접 대비

시간 제한1초메모리 제한1024 MB

요약

우선순위 큐의 모든 원소에 A_i를 더한 뒤 각 원소를 K로 나눈 나머지로 바꾸고, 매 질의마다 최댓값을 출력하는 문제입니다.

문제

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

우선순위 큐를 이용해 시뮬레이션한다. $i$ 번째 쿼리는 다음 순서로 진행한다.

$T$ 개의 쿼리를 수행한 결과를 구한다.

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

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

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

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