405778: GYM102078 B Points
Description
You 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.
Operations may be of three distinct types:
- Type 1: given two points $$$P_i$$$ and $$$P_j$$$, previously belonging to different sets, join the sets to which they belong.
- 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.
- 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$$$.
The 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.
The 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:
- $$$1$$$ $$$i$$$ $$$j$$$: represents a Type 1 query over the points $$$P_i$$$ and $$$P_j$$$.
- $$$2$$$: represents a Type 2 query.
- $$$3$$$ $$$i$$$ $$$j$$$: represents a Type 3 query over the points $$$P_i$$$ and $$$P_j$$$.
Limites:
- $$$1 \leq N \leq 2 \times 10^5$$$
- $$$1 \leq Q \leq 3 \times 10^5$$$
- $$$-10^8 \leq x_i, y_i, z_i \leq 10^8$$$
For each Type 3 query, you should print its answer in a single line.
ExamplesInput5 1 5 0 2 4 0 3 3 0 4 2 0 5 1 0 7 3 1 2 1 1 4 3 1 2 1 2 5 3 1 2 2 3 1 2Output
2 4 8 4Input
4 -10 -10 0 -10 10 0 10 -10 0 10 10 0 6 3 2 4 1 1 2 3 2 4 3 4 3 3 1 3 3 1 4Output
20 40 20 40 40