Access Globe Parking Lot Maintenance

access_globe has a huge parking lot with \(n\) rows and \(m\) parking spots per row (with the condition \(n\ge m\)). Each parking spot is a square. Initially, all parking spots are empty.

You need to support two types of events:

• U x y s: Update the parking lot at row \(x\), column \(y\) to state \(s\) (where \(s=1\) means a car parks there, and \(s=0\) means a car leaves, making the spot empty).
• Q x1 y1 x2 y2: Query the rectangular region with the top-left corner (\(x1,y1\)) and bottom-right corner (\(x2,y2\)). For this region, determine the side length of the largest square that contains only empty parking spots. The square can be located anywhere within the queried rectangle.

If you can efficiently solve this problem, access_globe will reward you handsomely!

inputFormat

The first line contains three integers \(n, m, q\) (with \(n\ge m\)), representing the number of rows, columns, and events, respectively.

The next \(q\) lines each describe an event in one of the following formats:

• U x y s: Update the cell at row \(x\) and column \(y\) to state \(s\) (\(s=1\) for a parked car and \(s=0\) for an empty spot).
• Q x1 y1 x2 y2: Query the rectangular region with top-left \((x1,y1)\) and bottom-right \((x2,y2)\) for the largest square consisting solely of empty spots.

Initially, all parking spots are empty.

outputFormat

For each query event, output a single integer on a new line — the side length of the largest square containing only empty parking spots within the specified rectangle.

sample

3 3 4
Q 1 1 3 3
U 2 2 1
Q 1 1 3 3
U 2 2 0

3
1