Matrix#484

Matrix

3 seconds
256 megabytes
Hard

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:

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 .

Input

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.

Output

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.

Examples

Example 1

Loading
Loading

Note

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 ).

Scoring

In each block, the tests are evaluated independently.

  1. ( points): n \le 10;

  2. ( points): n \le 100;

  3. ( points): no additional restrictions.