Colorful Rectangle

Time limit10sMemory limit512 MB

Summary

Given colored points in the plane, find the minimum perimeter of an axis-parallel rectangle that contains at least one point of each of the three colors.

Level: Hard8 of 10
Topics: Segment tree, Sorting, Two pointers
Solved: No attempts yet

Problem

Points are given on a plane. Each point is colored red, blue, or green. An axis-parallel rectangle is called colorful if it contains at least one point of every color inside or on its edges. Find the colorful axis-parallel rectangle with the shortest perimeter. An axis-parallel line segment counts as a degenerate rectangle, and its perimeter is twice its length.

Input

The first line contains an integer $n$ ( $3 \le n \le 10^5$ ). Each of the next $n$ lines contains three integers $x_i$ , $y_i$ , and $c_i$ , meaning a point of color $c_i$ is at $(x_i, y_i)$ ( $0 \le x_i \le 10^8$ , $0 \le y_i \le 10^8$ , $0 \le c_i \le 2$ ). Color 0 is red, 1 is blue, and 2 is green. There is at least one point of every color, and no two points share the same coordinates.

Output

Print a single integer, the shortest perimeter of a colorful axis-parallel rectangle.

Examples2

Example 1
Input
```
4
0 2 0
1 0 0
1 3 1
2 4 2
```
Expected output
```
8
```
Example 2
Input
```
4
0 0 0
0 1 1
0 2 2
1 2 0
```
Expected output
```
4
```