24673번 - Aidana and Pita 스페셜 저지다국어

문제

Aidana loves pita. Yesterday she brought home $n$ pitas. Each pita has a tastiness value, which is an integer. Today three friends of Aidana will come to dinner. She will distribute all $n$ pitas among them; each pita will go to exactly one friend. The happiness of a friend is the sum of tastiness values of all pitas he or she received. Aidana wants to be fair. So help her find a distribution of pitas that minimizes the difference between her friends' maximum and minimum happiness.

입력

The first line contains one integer $n,ドル the number of pitas $(3 \le n \le 25)$.

The second line contains $n$ integers, $a_1, a_2, \ldots, a_n,ドル which are tastiness values for pitas (1ドル \le a_i \le 10^7$).

출력

Print $n$ integers: for each pita, print the friend's index to which this pita should go (friends' indices are 1, 2, and 3).

If there are several possible answers which minimize the difference between maximum and minimum happiness, print any one of them.

제한

힌트