P14867 [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. $$ \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.