![](https://dmoj.algome.me/media/martor/496dbaea-11cc-4a68-b89f-b2142c2f615f.jpg)
During the last DMOPC, rows of seats. Each row has
seats. Initially, there is one player in each seat. As the event goes on, a person's laptop battery might run dry, which causes them to pack up and go home.
games. Before each game, a single player's laptop battery runs out and they leave the party. Specifically, before the
game, the player sitting at the
row and the
column leaves the party. After this person leaves, needs to choose players to play in the upcoming game, so he chooses a square of seats such that all seats in the square are occupied by a player.
Before each game,
wants to know the side length of the greatest square of players he can invite for that game. Can you help him?Constraints
For all subtasks:
Subtask 1 [20%]
Subtask 2 [20%]
Subtask 3 [60%]
No additional constraints.
Input Specification
The first line will contain and
, the number of rows and columns respectively.
The second line will contain , the players that will leave throughout the event.
The next lines will contain integers
and
, indicating that the person at the
row and the
column leaves because his or her battery dies. It is guaranteed that the player sitting at
has not already left.
Output Specification
For each of the lines, output the side length of the largest square of players that can still invite to his game. If there are no players remaining, print
0
.
Sample Input
3 3
3
3 3
3 2
2 2
Sample Output
2
2
1
Comments