Team Selection

Split N players into two equal teams so the difference between the captains' total scores is minimized, choosing the lexicographically smallest assignment.

Hard9Divide and conquerDynamic programmingSortingBrute forceNo attempts yetTime limit2sMemory limit128 MB

Description

Examples5

Problem

Two captains want to split the players into two teams of the same size. There are N players. Captain 1 and captain 2 each assigned their own score to every player. A team's score is the sum of the scores that its captain assigned to the players on that team.

Every player must belong to exactly one of the two teams, and the teams must have the same number of players. Find which team each player should join so that the absolute difference between the two team scores is as small as possible.

Input

The first line contains the number of players N. N is an even integer between 2 and 36, inclusive.

The second line contains, in order from player 1 to player N, the scores assigned by captain 1. The third line contains, in the same order, the scores assigned by captain 2.

Every score is an integer between 1 and 10^15, inclusive.

Output

Print one line containing the team number for each player from player 1 to player N, separated by spaces. Captain 1's team is team 1, and captain 2's team is team 2.

If multiple assignments minimize the score difference, print the lexicographically smallest output sequence.