B. Points
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.
Input

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$$$
Output

For each Type 3 query, you should print its answer in a single line.

Examples
Input
5
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 2
Output
2
4
8
4
Input
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 4
Output
20
40
20
40
40