405420: GYM101955 E 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 input contains several test cases, and the first line contains a positive integer $$$T$$$ indicating the number of test cases which is up to $$$60$$$.

For each test case, the first line contains two integers $$$n$$$, indicating the number of clans and also the number of ninjas, and $$$m$$$, indicating the total number of special conflicts and inquiries from the governor, where $$$1 \le n \le 10^5$$$ and $$$1 \le m \le 10^5$$$.

The following $$$n$$$ lines describe the initial situations of all ninjas. The $$$i$$$-th line of them contains three integers $$$x, y$$$ and $$$c$$$ indicating the initial position where the $$$i$$$-th ninja stays is $$$(x, y)$$$ and the initial clan which he/she belongs to is the $$$c$$$-th one, where $$$-10^9 \le x, y \le 10^9$$$ and $$$1 \le c \le n$$$.

Then the following $$$m$$$ lines describe all special conflicts that change someone's position or his/her clan, and all inquiries from the governor in chronological order. Each of them must be in one of the following forms.

• 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