有 $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$ 。
| 子任务编号 | 追加限制 | 分数 |
|---|---|---|
| $1$ | $ $ | $100$ |
时间限制：$\texttt{2s}$
空间限制：$\texttt{1024MB}$