You have a square binary matrix of size n \times n. Initially, all its elements are equal to zero.
You are given updates. Each update has the following form:
x y — set a_{x,y} := 1. If this cell was already , it stays .
The coordinates and are -based.
After the initial all-zero matrix (before processing any updates), and after each of the updates, you have to find the side length of the largest square submatrix consisting only of .
The first line contains two integers and (1 \le n \le 500, 1 \le q \le 250 000) — the size of the matrix and the number of updates.
Each of the next lines contains two integers and (1 \le x, y \le n) and describes the update x y — set a_{x,y} := 1.
Print q+1 lines.
On the first line, print the side length of the largest all-ones square submatrix in the initial matrix (which is all zeros).
Then, after each update, print the side length of the largest all-ones square submatrix in the current matrix.
Example 1
In the example, the matrix after each query is:
After 1 1:
1 | 0 | 0 |
0 | 0 | 0 |
0 | 0 | 0 |
After 1 2:
1 | 1 | 0 |
0 | 0 | 0 |
0 | 0 | 0 |
The largest all-ones square has side length .
After 2 2:
1 | 1 | 0 |
0 | 1 | 0 |
0 | 0 | 0 |
Now the largest all-ones square has side length (top-left corner at ).
In each block, the tests are evaluated independently.
( points): n \le 10;
( points): n \le 100;
( points): no additional restrictions.