The Kouga Ninja Scrolls

The story centres around $n$ rival ninja clans labelled from $1$ to $n$, and $n$ ninjas also labelled from $1$ to $n$.
For each ninja, the family decides his/her initial belief and affiliation of a clan.
But some conflicts occur in the story, such as two young souls, facing the rivalry between their ninjas but falling in love, can change their mind and some ninjas may desert to other opposite clans.

These ninjas are living in a pretty quiet town with straightforward footpaths, but they live like a group of wild animals eyeing up ninjas of other clans, continually escaping and looking forward to killing.
The governor of this region knows that the end of the war between them depends on those ninjas belonging to different clans who have the farthest distance.

That is what a noble vulture as the honest servant of the governor should do.
Now you need to act as a vulture, and report in real time to the governor the largest distance between two ninjas that belong to different clans and whose labels are in a specified consecutive range.
As a practical matter, the distance between two points in the plane is defined as the Manhattan distance, which is equal to the sum of the absolute differences of their Cartesian coordinates.

The story centres around $n$ rival ninja clans labelled from $1$ to $n$, and $n$ ninjas also labelled from $1$ to $n$.
For each ninja, the family decides his/her initial belief and affiliation of a clan.
But some conflicts occur in the story, such as two young souls, facing the rivalry between their ninjas but falling in love, can change their mind and some ninjas may desert to other opposite clans.

These ninjas are living in a pretty quiet town with straightforward footpaths, but they live like a group of wild animals eyeing up ninjas of other clans, continually escaping and looking forward to killing.
The governor of this region knows that the end of the war between them depends on those ninjas belonging to different clans who have the farthest distance.

That is what a noble vulture as the honest servant of the governor should do.
Now you need to act as a vulture, and report in real time to the governor the largest distance between two ninjas that belong to different clans and whose labels are in a specified consecutive range.
As a practical matter, the distance between two points in the plane is defined as the Manhattan distance, which is equal to the sum of the absolute differences of their Cartesian coordinates.

$1$ $k$ $x$ $y$, the $k$-th ninja changes his/her position along the direction $(x, y)$; that is to say, he/she moves to the new position $(x_0 + x, y_0 + y)$ where $(x_0, y_0)$ is his/her original position.
$2$ $k$ $c$, the $k$-th ninja changes his/her mind and decides to work for the $c$-th clan.
$3$ $l$ $r$, the governor asks his vulture for ninjas labelled from $l$ to $r$ (inclusive) the largest distance between two of them belonging to different clans.


All $k, x, y, l, r$ and $c$ mentioned in these $m$ lines satisfy $1 \le k, c \le n$, $-10^9 \le x, y \le 10^9$ and $1 \le l \le r \le n$.

We guarantee that the sum of $n$ in all test cases is no larger than $5 \times 10^5$, and the sum of $m$ in all test cases is no larger than $5 \times 10^5$ as well.

For each test case, output a line containing "Case #x:" (without quotes) at first, where $x$ is the test case number starting from $1$.

Then for each inquire, output an integer in a line indicating the answer. If all of the related ninjas belong to the same clan, output $0$ instead.

1
2 8
0 0 1
1 1 2
3 1 2
1 1 1 1
3 1 2
1 1 1 1
2 1 2
3 1 2
2 1 1
3 1 2

Case #1:
2
0
0
2

The Kouga Ninja Scrolls is a historical fantasy novel about ninja written in 1958-1959 by the Japanese author Futaro Yamada.
This is the first volume of the Ninja Scrolls series written by Yamada in 1958-2001.
The book has been translated into English by Geoff Sant and was published by Del Rey in December 2006.

--from Wikipedia, the free encyclopedia

The 43rd ACM International Collegiate Programming Contest Asia Shenyang Regional Contest