Boulder Arrangement Optimization

Vicomte de Bajteaux owns a famous collection of boulders. Recently, he decided to display the boulders in his expansive rectangular garden of dimensions \(10^9 \times 10^9\) (units), with sides parallel to the east‐west and north‐south directions.

For each boulder, the vicomte determined the coordinates where it should be placed. However, he forgot to specify the order of coordinates: for some boulders the first number is intended as the \(y\) coordinate (ordinate), while for others it is the \(x\) coordinate (abscissa). The servants, unaware of this fact, placed all boulders under the usual Cartesian assumption (i.e. the first coordinate is \(x\) and the second is \(y\)).

To protect his collection, the vicomte wants to enclose all boulders with a rectangular fence having sides parallel to those of the garden. The garden has been planned in such a way that if the boulders were arranged according to his original intended ordering, the required total fence length (i.e. perimeter) would be minimal. The servants, in order to avoid suspicion, are allowed to swap the two coordinates of some boulders. However, since the boulders are heavy, each may only be moved by swapping its coordinates, and each boulder has an associated weight that represents the effort required to swap its coordinates.

The task is to choose which boulders to swap so that:

1. The fence perimeter enclosing the boulders is minimized. If we let \(x_i\) and \(y_i\) denote the coordinates actually used for boulder \(i\), then the fence must cover the rectangle with \(x_{min} = \min_i x_i\), \(x_{max} = \max_i x_i\), \(y_{min} = \min_i y_i\), and \(y_{max} = \max_i y_i\), and the perimeter is \(2\Big[(x_{max}-x_{min})+(y_{max}-y_{min})\Big]\).
2. Among all configurations that yield the minimal perimeter, the total weight of the boulders that are actually moved (swapped) is minimized.

Hint: It can be shown that the intended arrangement is achieved by ensuring for each boulder with given coordinates \(a\) and \(b\), you choose the representation \((\min(a,b), \max(a,b))\). Therefore, if \(a \le b\) no move is required; if \(a > b\), swapping is necessary.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), the number of boulders. Each of the following \(n\) lines contains three positive integers \(a\), \(b\) and \(w\) (\(1 \le a, b \le 10^9\), \(1 \le w \le 10^9\)), where \(a\) and \(b\) are the coordinates as placed by the servants and \(w\) is the weight (cost) to move that boulder. For each boulder, you may either leave it as is (interpreting the coordinates as \((a,b)\)) or swap the coordinates (interpreting them as \((b,a)\)).

outputFormat

Output \(n\) lines. The \(i\)-th line should contain a single integer: 0 if the \(i\)-th boulder is left in its current position, or 1 if its coordinates are swapped. This configuration must yield the minimal possible fence perimeter, and among all such configurations, it should minimize the total move cost (i.e. the sum of weights of moved boulders).

sample

3
1 2 10
3 1 5
2 4 7

0
1
0