Envy-Free Item Distribution

Bajtyna and Bitek have n items. For the i^th item, Bajtyna assigns it a value \(a_i\) and Bitek assigns it a value \(b_i\) (the two values may be equal or different). They must distribute all items between them so that neither one becomes jealous of the other. The jealousy is defined as follows:

• Bitek will be jealous if \[ S_B < S_A - \min_{j \in A} a_j, \] where \(A\) is the set of items assigned to Bajtyna, \(S_A = \sum_{j \in A} a_j\) and \(S_B\) is the total Bitek value of his items.
• Similarly, Bajtyna will be jealous if \[ S_A < S_B - \min_{j \in B} b_j, \] where \(B\) is the set of items assigned to Bitek and \(S_B = \sum_{j \in B} b_j\).

An allocation is considered envy‐free up to one item (EF1) if neither player is jealous according to the above definition. It is known that an EF1 allocation always exists for two players with additive valuations. One well‐known procedure is the sequential picking (or round‐robin) method: the players take turns picking the remaining item that gives them the maximum value (according to their own valuation). In this problem, Bajtyna picks first.

Your task is to output an allocation of all items (each item must be given to either Bajtyna or Bitek) that is envy‐free up to one item by applying the sequential picking procedure.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)) — the number of items. Each of the following \(n\) lines contains two integers \(a_i\) and \(b_i\) (\(1 \le a_i, b_i \le 10^9\)), representing the value of the i^th item for Bajtyna and Bitek respectively.

outputFormat

Output a single line containing \(n\) numbers. The \(i^th</em> number should be 1 if the i^th item is allocated to Bajtyna, or 2 if it is allocated to Bitek. It is guaranteed that the allocation produced by the following sequential picking process is envy‐free up to one item:

1. Bajtyna picks first. When it is a player's turn, they choose the remaining item with the maximum value according to their own valuation.
2. They alternate turns until all items are allocated.

sample

2
5 3
4 6

1 2