Bajtyna and Bitek must divide $n$ items between themselves. For each item, we know its value for Bajtyna and its value for Bitek; these two values may be the same, but they do not have to be. We want to assign each item to exactly one person in such a way that neither person envies the other, which we define as follows.

Bitek envies Bajtyna if the total value of all of Bitek's items is strictly less than the total value of all of Bajtyna's items excluding one arbitrarily chosen item (in particular, the one with the lowest value), where both total values are calculated by adding the values for Bitek. For example, consider four items whose values for Bitek are $4, 3, 4, 8$ respectively. Assigning the first two items to Bitek causes Bitek to envy Bajtyna, because $4 + 3 < 8$. Assigning the last item to Bitek ensures Bitek does not envy Bajtyna, because $8 \geq 4 + 4$.

We define when Bajtyna envies Bitek in an analogous way, where in this case we calculate the total values by adding the values for Bajtyna.

Divide all items between Bajtyna and Bitek so that no person envies the other.

Input

The first line of input contains a single integer $n$ ($1 \leq n \leq 500\,000$) denoting the number of items. The second line of input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$) denoting the values of the items for Bajtyna. The third line of input contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \leq b_i \leq 10^9$) denoting the values of the items for Bitek.

Output

In the first line of output, print $n$ integers separated by single spaces that describe a division of items satisfying the condition in the problem statement. Of these numbers, the $i$-th should be equal to $0$ if the $i$-th item goes to Bajtyna, and $1$ otherwise. You may assume that a division satisfying the condition always exists.

Examples

Input 1

4
10 5 9 6
4 6 8 4

Output 1

1 0 0 1

Note

Explanation for the example: The second and third items go to Bajtyna, and the rest go to Bitek. Bajtyna does not envy Bitek, because $5 + 9 \geq 10$ and $5 + 9 \geq 6$. Bitek does not envy Bajtyna, because $4 + 4 \geq 6$ and $4 + 4 \geq 8$.

Sample Tests

Test 0 is the example above. Additionally: - Test 1: $n = 6, a_i = 7 - i, b_i = i$; sample answer: $0, 0, 0, 1, 1, 1$; - Test 2: $n = 12, a_i = 1, b_i = 2$; sample answer: $1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0$; - Test 3: $n = 500\,000, a_i = b_i = 10^9$; sample answer: $0, 1, 0, 1, 0, 1, \dots$.

Subtasks