유리병 속 무한히 터지는 기포

너에게서는 멸종된 과일 향기가 난다

투룸 신축 빌라 보증금 이천에 월세 구십, 어떻게 해야 너를 웃길 수 있을까 하는 생각, 두 시간 동안의 폭우, 일주일 동안의 아침, 유리병 속 무한히 터지는 기포

-고선경, [샤워젤과 소다수]

세로로 길쭉한 유리병 하나가 있다. 이 속에서 기포가 무한히 터지고 있다.

과학자 정우는 이 현상에 호기심을 느끼고 계속 관찰했다. 그 결과 다음 사실을 알아냈다. 먼저 유리병을 세로로 $N$등분해서, 가장 아래의 $1$번 구역부터 가장 위의 $N$번 구역까지 총 $N$개의 구역으로 나눌 수 있다. 각 구역에는 최대 $M$개의 기포가 있을 수 있다. 처음에는 어느 구역에도 기포가 없다. 1초마다 유리병 안에서 다음 두 현상이 이 순서대로 번갈아 일어난다.

• 기포 생성: 유리병 안의 구역 하나에서 기포가 생성된다. $i$번째 기포 생성 때 $y_i$번 구역에서 $k_i$개의 기포가 생성된다. 그 구역에 원래 있던 기포 수와 새로 생긴 기포 수의 합이 $M$을 넘으면 $M$개만 남고 나머지 기포는 모두 사라진다.
• 기포 이동: 모든 구역의 기포가 동시에 위 또는 아래로 움직인다. $i$번 구역에 $a_i$개의 기포가 있으면, $\left\lfloor\frac{a_i}{5}\right\rfloor$개는 바로 위 구역으로, $\left\lfloor\frac{a_i}{5}\right\rfloor$개는 바로 아래 구역으로 이동하고, $\left\lfloor\frac{a_i}{5}\right\rfloor$개는 제자리에 남으며, 나머지 기포는 사라진다. $1$번 구역의 아래나 $N$번 구역의 위로 움직이려는 기포는 사라진다. 이동 후 어느 구역의 기포 수가 $M$을 넘으면 $M$개만 남고 나머지 기포는 모두 사라진다.

그림 1. (a) 유리병을 $N$개의 구역으로 나눈 모습. (b) $1$번 구역과 $N$번 구역에서 각각 기포가 이동하는 모습.

정우는 유리병 속 기포의 움직임을 모델링하는 프로그램을 만들려 한다. $t$초가 지난 뒤, 즉 기포 생성과 기포 이동이 각각 $t$번 일어난 뒤 유리병 속에 남은 기포의 총수를 $S(t)$라 하자. 관찰 시간 $T$가 주어질 때, $S(1), S(2), \cdots, S(T)$의 값을 구하시오.

첫째 줄에 유리병을 이루는 구역의 수 $N$, 각 구역에 존재할 수 있는 기포의 최대 수 $M$, 관찰 시간 $T$가 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 100\,000$, $1 \leq T \leq 50\,000$)

둘째 줄부터 $T$개의 줄에 걸쳐, $i$번째 기포 생성에 대해 기포가 생성되는 구역의 번호 $y_i$와 그 구역에서 생성되는 기포의 수 $k_i$가 공백으로 구분되어 주어진다. ($1 \leq y_i \leq N$, $0 \leq k_i \leq M$)

$T$개의 줄에 걸쳐, $i$번째 줄에 $S(i)$의 값을 출력한다.

$\lfloor x \rfloor$는 바닥 함수로, 주어진 실수 $x$ 이하의 최대 정수를 나타낸다.