Public Judge

pjudge

Time Limit: 2 s Memory Limit: 1024 MB Hackable ✓
统计

有 $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}$