There are $n$ cakes, where the $i$-th cake has a weight of $a_i$.

You want to divide these $n$ cakes into three parts such that the sum of weights in each part is equal.

However, you find that the cakes cannot be cut, so you must settle for minimizing the range, which is the difference between the maximum sum of weights and the minimum sum of weights among the three parts.

Input

The first line contains a positive integer $n$.

The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$.

Output

Output $n$ integers, each of which must be one of $\{1, 2, 3\}$, representing which part each cake is assigned to.

If there are multiple solutions that minimize the range, you may output any one of them.

Examples

Input 1

5
2 3 1 4 2

Output 1

3 2 2 1 3

Note 1

The sums of the weights of the three parts are:

• $4$
• $3 + 1 = 4$
• $2 + 2 = 4$

Therefore, the range of this scheme is $0$.

Input 2

6
3 2 5 3 4 2

Output 2

2 3 1 2 3 1

Note 2

The sums of the weights of the three parts are:

• $5 + 2 = 7$
• $3 + 3 = 6$
• $2 + 4 = 6$

Therefore, the range of this scheme is $1$.

Input 3

See the provided files.

Constraints

For all data, it is guaranteed that $3 \le n \le 25$ and $1 \le a_i \le 10^7$.