## Art Academy IV: Alice's Blazing Fury

View as PDF

Points: 30 (partial)
Time limit: 2.5s
Java 5.0s
Python 20.0s
Memory limit: 128M
Python 256M

Author:
Problem type

You notice a disturbance in the area. Something on this particular day is strangely, off?

Is it because hewmatt10 has been sabotaged?

Is it because both astrocat879 and skyflaren are nowhere to be found?

Simply put, it's much more frightening than that.

Today marks the end of an era. [REDACTED] has finally had enough of scandals like hewmatt10 being able to freely roam around her majestic Empire. To ensure that her task is as quick as possible, she will be activating her Empire's secret stash of illegal weaponry, which has been crafted with only one purpose in mind - destruction.

Since this is her Empire after all, the weapons have been specifically named after her - The Alicizer. [REDACTED] has not only one, not two, but an infinite stash of Alicizers, which she will be placing down at specific coordinates along her row by column Empire. The more in a line, either vertically or horizontally, there are, the more powerful and destructive they get. Since [REDACTED] is a cruel person by nature, she will be placing down Alicizers in large square-shaped chunks at a time.

Such a ruthless task will definitely face resistance, as hewmatt10 and his army will be tryharding epically to defend his basement art academy. hewmatt10's basement workers have engineered a special line of defense that they will be using to protect themselves, called the Anti-Alicizer. Just like how Alicizers will be placed in large square-shaped chunks at a time, an Anti-Alicizer will be able to remove square-shaped chunks of Alicizers.

As a spectator of this war, yeahbennou would rather not get completely obliterated in battle, and instead like to record down some statistics as the war goes on. Since he is lazy, yeahbennou wants you to create a program which will answer queries to help him keep track of the battle.

#### Input Specification

On the first line, there will be three space-separated integers - , , and , representing the size of [REDACTED]'s empire, and the number of queries yeahbennou wants you to perform.

The following lines will contain one of the following queries:

Format Description
At the position , place down Alicizers in a by square. , , For example, if , , and were , , and respectively, there would now be Alicizers at , , , and . It is guaranteed that these newly placed Alicizers will not be "overlapping" any previously placed ones. It is also guaranteed that no Alicizers in the square will land outside of the empire.
Place down an Anti-Alicizer at position of power level , , . For example, if , , and were , , and respectively, The Alicizers at , , , or would now be destroyed. It is guaranteed that there WILL be Alicizers fully encompassing the area being destroyed.
Query the length of the longest contiguous subsequence of Alicizers that goes strictly in one direction (Horizontal or Vertical), that includes at least one of the points in the range , . For example, if , , and were , , and respectively, the points in this range would be , , , and . , , .

It is guaranteed that for all queries, and .

#### Output Specification

For each type query, print the result on a new line.

#### Constraints

, and for all queries.

#### Sample Input

5 5 4
1 1 1 2
1 2 3 2
3 1 1 1
3 1 1 2

#### Sample Output

2
4

Note: Passing the sample is not required for passing the subtasks.

#### Explanation

After the first two queries of type , there are now Alicizers at , , , , , , , .

In the third query, only the position is in the range , .

The longest contiguous subsequence of Alicizers that spans strictly on one direction, that includes , would either be the subsequence containing and , or the subsequence containing and . Both of these are of length .

In the last query, the positions , , , are in the range , .

The longest contiguous subsequence of Alicizers that spans strictly on one direction, that includes any of these points, would be the subsequence containing , , , and , which is of length .