## TLE '16 Contest 3 P5 - LAN Party

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Java 8 1.8s
Python 1.8s
Memory limit: 256M

Authors:
Problem types
From left to right: d, ZQFMGB12, jlsajfj, EnochPoon and nathanl3

During the last DMOPC, d did great and scored place! (Only to be beaten by Thornhill of course.) ZQFMGB12 is so happy for d that he decided to throw a LAN party with the entire school. The party is organized into 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.

ZQFMGB12 will host 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, ZQFMGB12 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, ZQFMGB12 wants to know the side length of the greatest square of players he can invite for that game. Can you help him?

#### 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 ZQFMGB12 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