Infinitely Bursting Bubbles in a Glass Bottle

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

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

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

A tall, thin glass bottle stands upright. Inside it, bubbles burst endlessly.

Scientist Jeongwoo became curious about this phenomenon and kept observing it. He found the following facts. First, divide the bottle vertically into $N$ equal parts, forming $N$ zones from zone $1$ at the bottom to zone $N$ at the top. Each zone can hold at most $M$ bubbles. At the start, no zone has any bubbles. Every second, the following two phenomena occur in turn, in this order.

• Bubble creation: Bubbles are created in one zone of the bottle. At the $i$-th creation, $k_i$ bubbles are created in zone $y_i$. If the sum of the bubbles already in that zone and the newly created bubbles exceeds $M$, only $M$ bubbles remain and the rest disappear.
• Bubble movement: Bubbles in all zones move up or down at the same time. If zone $i$ has $a_i$ bubbles, then $\left\lfloor\frac{a_i}{5}\right\rfloor$ bubbles move to the zone directly above, $\left\lfloor\frac{a_i}{5}\right\rfloor$ bubbles move to the zone directly below, $\left\lfloor\frac{a_i}{5}\right\rfloor$ bubbles stay in place, and the remaining bubbles disappear. A bubble that tries to move below zone $1$ or above zone $N$ disappears. After movement, if any zone has more than $M$ bubbles, only $M$ remain and the rest disappear.

Figure 1. (a) The bottle divided into $N$ zones. (b) Bubble movement at zone $1$ and zone $N$.

Jeongwoo wants to write a program that models how bubbles move in the bottle. Let $S(t)$ be the total number of bubbles left in the bottle after $t$ seconds, that is, after $t$ rounds of bubble creation and bubble movement. Given the observation time $T$, find the values of $S(1), S(2), \cdots, S(T)$.

The first line contains three integers $N$, $M$, and $T$, separated by spaces: the number of zones, the maximum number of bubbles each zone can hold, and the observation time. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 100\,000$, $1 \leq T \leq 50\,000$)

From the second line onward, the next $T$ lines each contain, for the $i$-th creation, the zone number $y_i$ where bubbles are created and the number of bubbles $k_i$ created there, separated by a space. ($1 \leq y_i \leq N$, $0 \leq k_i \leq M$)

Print $T$ lines. On line $i$, print $S(i)$.

$\lfloor x \rfloor$ is the floor function, which gives the largest integer less than or equal to the real number $x$.