Background

Luogu’s testdata is for community exchange only and is not official testdata. Official judging link: https://www.cspro.org/.

Problem Description

Ten Drops of Water is a very classic mini game.

:::align{center} :::

Player C is playing a one-dimensional version of the Ten Drops of Water game. We describe the basic rules of the game with an example.

The game is played on a $1 \times c$ grid. Cells are indexed by integers $x\ (1 \le x \le c)$, increasing from left to right. Among the $c$ cells, $m$ cells contain $1 \sim 4$ drops of water, and the other cells contain no water. In our example, $c = m = 5$, and in index order, the numbers of drops in each cell are $2, 4, 4, 4, 2$.

The player can perform several operations. In each operation, the player chooses a cell that contains water and increases the number of drops in that cell by $1$. At any time, if the number of drops in a cell is greater than or equal to $5$, the drops in this cell will burst to both sides. At this moment, the cell is cleared (its water becomes $0$). Then, for both the left and right directions, do the following at the same time: find the nearest cell in that direction that currently contains water; if such a cell exists, increase its number of drops by $1$. If at some moment multiple cells have at least $5$ drops, the leftmost one bursts first.

In our example, if the player performs an operation on the third cell, its number of drops becomes $5$, so the third cell bursts. It is cleared, and the nearest cell with water on its left (the second cell) and on its right (the fourth cell) each gains $1$ drop. Now the numbers of drops become $2, 5, 0, 5, 2$.

At this time, both the second and fourth cells have at least $5$ drops. According to the rule, the second cell bursts first. After that, the numbers of drops become $3, 0, 0, 6, 2$. Finally, the fourth cell bursts, and the numbers of drops become $4, 0, 0, 0, 3$.

Player C has started a game and performed $n$ operations. After each operation, Player C will wait until all cells with at least $5$ drops have finished bursting before performing the next operation.

Player C wants to know how good he is, so he wants to know how many cells still contain water after each operation.

It is guaranteed that these $n$ operations are all valid, i.e., in each operation, the chosen cell contains water at that time.

Input Format

Read from standard input.

The first line contains three integers $c, m, n$, representing the grid width, the number of cells that contain water, and the number of operations.

The next $m$ lines each contain two integers $x, w$, meaning that cell $x$ contains $w$ drops of water.

The next $n$ lines each contain one integer $p$, meaning that Player C performs an operation on cell $p$.

Output Format

Write to standard output.

Output $n$ lines, each containing one integer: the number of cells that contain water after this operation.

5 5 2
1 2
2 4
3 4
4 4
5 2
3
1

2
1

Hint

Subtasks

For all testdata,

• $1 \le c \le 10^9$，$1 \le m \le \min(c, 3 \times 10^5)$，$1 \le n \le 4m$；
• $1 \le x, p \le c$，$1 \le w \le 4$；
• All input $x$ are pairwise distinct；
• For each input $p$, it is guaranteed that cell $p$ contains water at the time of the corresponding operation.

Special Property: At any moment in the game (including during the chain reaction of bursting), there is at most one cell whose number of drops is greater than or equal to $5$.

Translated by ChatGPT 5