有 $n$ 个饼，第 $i$ 个饼的权值为 $a_i$ 。

你想用胎教时候就学过的除法把这 $n$ 个饼平均分成三份，使得每一份的权值之和都相等。

但是你发现饼不能切开，所以只能退而求其次，最小化极差，也就是最大的权值之和减去最小的权值之和。

输入格式

第一行一个正整数 $n$ 。

第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$ 。

输出格式

输出 $n$ 个整数，每个整数只能是 $\{1,2,3\}$ 中的一个，表示这个饼要分到第几份。

如果有多个最小化极差的方案，可以输出任意一个。

样例一

input

5
2 3 1 4 2

output

3 2 2 1 3

explanation

三份饼的权值和分别为：

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

因此该方案的极差为 $0$。

样例二

input

6
3 2 5 3 4 2

output

2 3 1 2 3 1

explanation

三份饼的权值和分别为：

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

因此该方案的极差为 $1$。

样例三

见下发文件。

数据范围与提示

对于所有数据，保证 $3\le n\le 25$，$1\le a_i\le 10^7$ 。

时间限制：$\texttt{2s}$

空间限制：$\texttt{1024MB}$