Mister IP has a plush penguin, so penguins from Byteland asked him for help. There are families of penguins; the -th family has 1 \le a_i \le 3 penguins in it.
They want to build cities and ask Mister IP to split them into teams for that. Of course, all penguins from the same family must be on the same team, and the teams must have as similar sizes as possible. In other words, you must partition the families into teams so that the size difference between the largest and smallest teams is minimized.
The first line contains two integers and (2 \le k \le n \le 2 \cdot 10^5) — the number of families and the number of teams.
The second line contains integers a_1, a_2, \dots, a_n (1 \le a_i \le 3) — the numbers of penguins in the -th family.
Output integers — t_1, t_2, \dots, t_n with 1 \le t_i \le k denoting the team number of the -th family such that all team sizes are as close as possible.
Example 1
Example 2
Example 3
In the first example, the sizes of teams are (2+2), (1+3), and (1+3) respectively; hence all team sizes are equal, and thus the partition is optimal.
In the second example, the sizes are (2+3)=5 and (1+2+3)=6 with a difference of . It can be shown that it's impossible to form two teams with a size difference equal to .
In the third example, team sizes are (3), (3+2)=5, (3+3)=6 with a difference of . It can be shown that it's impossible to form teams with a size difference smaller than .