Aidana 喜欢皮塔饼。昨天她带回家 $n$ 个皮塔饼。每个皮塔饼都有一个整数美味值。今天 Aidana 的三个朋友要来吃晚餐。她将把所有 $n$ 个皮塔饼分给他们；每个皮塔饼必须恰好分给一个朋友。一个朋友的“幸福度”是他/她所收到的所有皮塔饼的美味值之和。Aidana 想做到公平。请帮她找到一种皮塔饼的分配方案，使得三个朋友中最大幸福度与最小幸福度之间的差值最小。

输入格式

第一行包含一个整数 $n$，表示皮塔饼的数量 ($3 \le n \le 25$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示皮塔饼的美味值 ($1 \le a_i \le 10^7$)。

输出格式

输出 $n$ 个整数：对于每个皮塔饼，输出它应该分给的朋友编号（朋友编号为 1、2 和 3）。 如果有多种方案能使最大幸福度与最小幸福度之间的差值最小，输出其中任意一种即可。

样例

输入 1

5
2 3 1 4 2

输出 1

3 2 2 1 3

输入 2

6
3 2 5 3 4 2

输出 2

2 3 1 2 3 1