Description

access_globe has a huge parking lot with $n$ rows and $m$ spaces per row. For aesthetics, when building this parking lot, access_globe stipulated that it must be strip-shaped, i.e., $n\ge m$. Each parking space is a square area.

Recently, access_globe has been distressed about not being able to draw "Missing Poster", so he asks you to help maintain this parking lot. You need to support two types of events:

• A car parks in a certain space, or a car leaves a certain space.
• Query, within a rectangular region, the largest square region consisting only of empty spaces.

If you can help access_globe solve this efficiently, access_globe will reward you well.

Input Format

The first line contains three positive integers $n$, $m$, and $q$, denoting the size of the parking lot and the number of events.

The next $n$ lines each contain $m$ numbers, either $0$ or $1$. If the number at row $i$, column $j$ is $1$, then the space at row $i$, column $j$ is empty; otherwise, that space is non-empty.

The next $q$ lines each describe an event in one of the following two forms:

• $0$ $x$ $y$: The occupancy status of the space at row $x$, column $y$ toggles. That is, if this space was empty before this event, it becomes non-empty after the event; otherwise, it becomes empty. It is guaranteed that $1\le x\le n$, $1\le y\le m$.
• $1$ $l$ $s$ $r$ $t$: Query the side length of the largest all-empty square region within the rectangle with opposite corners $(l, s)$ and $(r, t)$. It is guaranteed that $1\le l\le r\le n$, $1\le s\le t\le m$.

Output Format

For each query, output one integer on its own line, representing the side length of the largest all-empty square for that query.

5 4 10
1 1 1 0
1 1 1 1
1 1 0 1
1 0 1 0
1 1 0 0
1 1 1 5 4
1 3 1 3 1
1 3 3 3 3
1 2 3 5 3
0 2 2
1 1 4 2 4
1 1 3 3 3
0 5 1
1 2 3 2 4
1 1 2 2 4

2
1
0
1
1
1
1
1

Hint

All subtasks are evenly weighted.

For all testdata, it is guaranteed that $n\times m\le 4\times 10^6$, $q\le 2000$.

Credit: https://www.luogu.org/discuss/show?postid=35727

Translated by ChatGPT 5