{"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\u003eYou have been given the coordinates of $$$N$$$ points in three-dimensional space—namely, $$$P_1, P_2, \\dots, P_N$$$. Initially, these points are distributed into $$$N$$$ singleton sets, one for each point. You have been asked to execute $$$Q$$$ operations involving these sets.\u003c/p\u003e\u003cp\u003eOperations may be of three distinct types: \u003c/p\u003e\u003cul\u003e \u003cli\u003e Type 1: given two points $$$P_i$$$ and $$$P_j$$$, previously belonging to different sets, join the sets to which they belong. \u003c/li\u003e\u003cli\u003e Type 2: undo the most recent union operation (Type 1) that has not already been undone. It is guaranteed that there exists at least one such operation. \u003c/li\u003e\u003cli\u003e Type 3: given two points $$$P_i$$$ and $$$P_j$$$, belonging to different sets, print the maximum Manhattan distance from a point in the same set as $$$P_i$$$ to a point in the same set as $$$P_j$$$. \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains a single integer $$$N$$$, indicating the number of points which follow. Each of the next $$$N$$$ lines contain three integers $$$x_i$$$, $$$y_i$$$ and $$$z_i$$$, representing the coordinates of the $$$i$$$th point.\u003c/p\u003e\u003cp\u003eThe next line contains an integer $$$Q$$$, indicating the number of queries that should be answered. Each of the next $$$Q$$$ lines represents a query, and has one of the following three formats: \u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$1$$$ $$$i$$$ $$$j$$$: represents a Type 1 query over the points $$$P_i$$$ and $$$P_j$$$. \u003c/li\u003e\u003cli\u003e $$$2$$$: represents a Type 2 query. \u003c/li\u003e\u003cli\u003e $$$3$$$ $$$i$$$ $$$j$$$: represents a Type 3 query over the points $$$P_i$$$ and $$$P_j$$$. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eLimites:\u003c/span\u003e \u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$1 \\leq N \\leq 2 \\times 10^5$$$ \u003c/li\u003e\u003cli\u003e $$$1 \\leq Q \\leq 3 \\times 10^5$$$ \u003c/li\u003e\u003cli\u003e $$$-10^8 \\leq x_i, y_i, z_i \\leq 10^8$$$ \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each Type 3 query, you should print its answer in a single line.\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\u003e5\n1 5 0\n2 4 0\n3 3 0\n4 2 0\n5 1 0\n7\n3 1 2\n1 1 4\n3 1 2\n1 2 5\n3 1 2\n2\n3 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n4\n8\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\u003e4\n-10 -10 0\n-10 10 0\n10 -10 0\n10 10 0\n6\n3 2 4\n1 1 2\n3 2 4\n3 4 3\n3 1 3\n3 1 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e20\n40\n20\n40\n40\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}