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

输入格式

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

$n$ $x_1 \ y_1 \ c_1$ $\vdots$ $x_n \ y_n \ c_n$

第一行包含一个整数 $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：绿色）。保证每种颜色的点至少有一个，且没有两个点坐标相同。

输出格式

输出一行，包含一个整数，表示最短的轴平行多彩矩形的周长。

样例

样例输入 1

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

样例输出 1

8

样例输入 2

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

样例输出 2

4