Description

给定平面上的一组点。每个点被染成红色、蓝色或绿色中的一种。如果一个矩形在其内部或边缘上包含至少一个每种颜色的点，则称该矩形为彩色矩形。你的任务是找到一个与坐标轴平行的彩色矩形，使其周长最短。与坐标轴平行的线段被视为退化的矩形，其周长为该线段长度的两倍。

Input Format

输入包含单个测试用例，格式如下。

$$\begin{aligned} & n\\ & x_1 \ y_1 \ c_1\\ & \vdots\\ & x_n \ y_n \ c_n\\ \end{aligned}$$

第一行包含一个整数 $n$ （$3 \le n \le 10^5$），表示平面上点的数量。接下来的 $n$ 行中，每行包含三个整数 $x_i$、$y_i$ 和 $c_i$，满足 $0 \le x_i \le 10^8$，$0 \le y_i \le 10^8$，且 $0 \le c_i \le 2$。每行表示在坐标 $(x_i, y_i)$ 处有一个颜色为 $c_i$ 的点（$0$：红色，$1$：蓝色，$2$：绿色）。保证至少存在每种颜色的一个点，并且没有两个点的坐标完全相同。

Output Format

在一行中输出一个整数，表示与坐标轴平行的彩色矩形的最短周长。

4
0 2 0
1 0 0
1 3 1
2 4 2

8

4
0 0 0
0 1 1
0 2 2
1 2 0

4