Art Academy IV: Alice's Blazing Fury

Points: 31 (partial)

Time limit: 6.0s

Java 8 12.0s

Processing 12.0s

Memory limit: 128M

Author:

BenZeng

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. A_L_I_C_E_ 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. A_L_I_C_E_ has not only one, not two, but an infinite stash of Alicizers, which she will be placing down at specific co-ordinates along her $N$ ~N~ row by $M$ ~M~ column Empire. The more in a line, either vertically or horizontally, there are, the more powerful and destructive they get. Since A_L_I_C_E_ 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 $Q$ ~Q~ queries to help him keep track of the battle.

Input Specification

On the first line, there will be three space-separated integers - $N$ ~N~, $M$ ~M~ $($ ~(~ $1$ ~1~ $\le$ ~\le~ $N × M$ $\le$ ~\le~ $5 × 10^5$ $)$ ~)~, and $Q$ ~Q~ $($ ~(~ $1$ ~1~ $\le$ ~\le~ $Q$ ~Q~ $\le$ ~\le~ $5 × 10^4$ $)$ ~)~, representing the size of A_L_I_C_E_'s empire, and the number of queries yeahbennou wants you to perform.

The following $Q$ ~Q~ lines will contain one of the following queries:

Format	Description
$1$ ~1~ $x$ ~x~ $y$ ~y~ $z$ ~z~	At the position $(x, y)$ ~(x, y)~, place down Alicizers in a $z$ ~z~ by $z$ ~z~ square. $($ ~(~ $1$ ~1~ $\le$ ~\le~ $x$ ~x~ $\le$ ~\le~ $N$ ~N~ $)$ ~)~, $($ ~(~ $1$ ~1~ $\le$ ~\le~ $y$ ~y~ $\le$ ~\le~ $M$ ~M~ $)$ ~)~, $($ ~(~ $1$ ~1~ $\le$ ~\le~ $z$ ~z~ $\le$ ~\le~ $min(N,\space M,\space 200)$ $)$ ~)~ For example, if $x$ ~x~, $y$ ~y~, and $z$ ~z~ were $2$ ~2~, $3$ ~3~, and $2$ ~2~ respectively, there would now be Alicizers at $(2, 3)$ ~(2, 3)~, $(3, 3)$ ~(3, 3)~, $(2, 4)$ ~(2, 4)~, and $(3, 4)$ ~(3, 4)~. 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.
$2$ ~2~ $x$ ~x~ $y$ ~y~ $z$ ~z~	Place down an Anti-Alicizer at position $(x, y)$ ~(x, y)~ of power level $z$ ~z~ $($ ~(~ $1$ ~1~ $\le$ ~\le~ $x$ ~x~ $\le$ ~\le~ $N$ ~N~ $)$ ~)~, $($ ~(~ $1$ ~1~ $\le$ ~\le~ $y$ ~y~ $\le$ ~\le~ $M$ ~M~ $)$ ~)~, $($ ~(~ $1$ ~1~ $\le$ ~\le~ $z$ ~z~ $\le$ ~\le~ $min(N,\space M,\space 200)$ $)$ ~)~. For example, if $x$ ~x~, $y$ ~y~, and $z$ ~z~ were $2$ ~2~, $3$ ~3~, and $2$ ~2~ respectively, The Alicizers at $(2, 3)$ ~(2, 3)~, $(3, 3)$ ~(3, 3)~, $(2, 4)$ ~(2, 4)~, or $(3, 4)$ ~(3, 4)~ would now be destroyed. It is guaranteed that there WILL be Alicizers fully encompassing the area being destroyed.
$3$ ~3~ $x$ ~x~ $y$ ~y~ $z$ ~z~	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 $[x, x + z)$ ~[x, x + z)~, $[y, y + z)$ ~[y, y + z)~. For example, if $x$ ~x~, $y$ ~y~, and $z$ ~z~ were $2$ ~2~, $3$ ~3~, and $2$ ~2~ respectively, the points in this range would be $(2, 3)$ ~(2, 3)~, $(3, 3)$ ~(3, 3)~, $(2, 4)$ ~(2, 4)~, and $(3, 4)$ ~(3, 4)~. $($ ~(~ $1$ ~1~ $\le$ ~\le~ $x$ ~x~ $\le$ ~\le~ $N$ ~N~ $)$ ~)~, $($ ~(~ $1$ ~1~ $\le$ ~\le~ $y$ ~y~ $\le$ ~\le~ $M$ ~M~ $)$ ~)~, $($ ~(~ $1$ ~1~ $\le$ ~\le~ $z$ ~z~ $\le$ ~\le~ $min(N,\space M,\space 200)$ $)$ ~)~.

It is guarunteed that for all queries, $x + z <= N$ ~x + z <= N~ and $y + z <= M$ ~y + z <= M~.

Output Specification

For each type $3$ ~3~ query, print the result on a newline.

Subtasks

Subtask	Points	Description
1	30	$1$ ~1~ $\le$ ~\le~ $N, M, Q$ ~N, M, Q~ $\le$ ~\le~ $10^2$ ~10^2~, and $z$ ~z~ $=$ ~=~ $1$ ~1~ for all queries.
2	70	No further constraints.

Sample Input

Sample Output

2
4

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

Explanation

After the first two queries of type $1$ ~1~, there are now Alicizers at $(1, 1)$ ~(1, 1)~, $(1, 2)$ ~(1, 2)~, $(2, 1)$ ~(2, 1)~, $(2, 2)$ ~(2, 2)~, $(2, 3)$ ~(2, 3)~, $(3, 3)$ ~(3, 3)~, $(2, 4)$ ~(2, 4)~, $(3, 4)$ ~(3, 4)~.

In the third query, only the position $(1, 1)$ ~(1, 1)~ is in the range $[x, x + z)$ ~[x, x + z)~, $[y, y + z)$ ~[y, y + z)~.

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

In the last query, the positions $(1, 1)$ ~(1, 1)~, $(1, 2)$ ~(1, 2)~, $(2, 1)$ ~(2, 1)~, $(2, 2)$ ~(2, 2)~ are in the range $[x, x + z)$ ~[x, x + z)~, $[y, y + z)$ ~[y, y + z)~.

The longest contiguous subsequence of Alicizers that spans strictly on one direction, that includes any of these points, would be the subsequence containing $(2, 1)$ ~(2, 1)~, $(2, 2)$ ~(2, 2)~, $(2, 3)$ ~(2, 3)~, and $(2, 4)$ ~(2, 4)~, which is of length $4$ ~4~.

Comments

There are no comments at the moment.