题目描述

You are given a set of points on a plane. Each point is colored either red, blue, or green. A rectangle is called colorful if it contains one or more points of every color inside or on its edges. Your task is to find an axis-parallel colorful rectangle with the shortest perimeter. An axis-parallel line segment is considered as a degenerated rectangle and its perimeter is twice the length of the line segment.

输入格式

The input consists of a single test case of the following format.

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

The first line contains an integer $n$ ($3 \le n \le 10^5$) representing the number of points on the plane. Each of the following $n$ lines contains three integers $x_i$, $y_i$, and $c_i$ satisfying $0 \le x_i \le 10^8$, $0 \le y_i \le 10^8$, and $0 \le c_i \le 2$. Each line represents that there is a point of color $c_i$ (0: red, 1: blue, 2: green) at coordinates $(x_i, y_i)$. It is guaranteed that there is at least one point of every color and no two points have the same coordinates.

输出格式

Output a single integer in a line which is the shortest perimeter of an axis-parallel colorful rectangle.

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