#214984. [ICPC 2020 Yokohama R] Colorful Rectangle

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.

The first line contains an integer () representing the number of points on the plane. Each of the following lines contains three integers , , and satisfying , , and . Each line represents that there is a point of color (0: red, 1: blue, 2: green) at coordinates . 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.

样例输入 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