{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThe 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.\u003c/p\u003e\u003cp\u003eThese 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.\u003c/p\u003e\u003cp\u003eThat 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.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe 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$$$.\u003c/p\u003e\u003cp\u003eFor 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$$$.\u003c/p\u003e\u003cp\u003eThe 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$$$.\u003c/p\u003e\u003cp\u003eThen the following $$$m$$$ lines describe all special conflicts that change someone\u0027s 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.\u003c/p\u003e\u003cul\u003e \u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e1 k x y\u003c/span\u003e, 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. \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e2 k c\u003c/span\u003e, the $$$k$$$-th ninja changes his/her mind and decides to work for the $$$c$$$-th clan. \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e3 l r\u003c/span\u003e, the governor asks his vulture for ninjas labelled from $$$l$$$ to $$$r$$$ (inclusive) the largest distance between two of them belonging to different clans. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eAll $$$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$$$.\u003c/p\u003e\u003cp\u003eWe 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.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, output a line containing \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eCase #x:\u003c/span\u003e\" (without quotes) at first, where \u003cspan class\u003d\"tex-font-style-tt\"\u003ex\u003c/span\u003e is the test case number starting from $$$1$$$.\u003c/p\u003e\u003cp\u003eThen 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.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n2 8\n0 0 1\n1 1 2\n3 1 2\n1 1 1 1\n3 1 2\n1 1 1 1\n2 1 2\n3 1 2\n2 1 1\n3 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1:\n2\n0\n0\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003e\u0027\u003cspan class\u003d\"tex-font-style-sf\"\u003eThe Kouga Ninja Scrolls\u003c/span\u003e\u0027 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$$$.\u003c/p\u003e\u003cp\u003e– from Wikipedia, the free encyclopedia\u003c/p\u003e"}}]}