Uolevi is working as a teacher's assistant on a software project course. His job is to divide the course's students into groups in which they will work. The course will have $n$ students numbered $1,2,\dots,n$ and Uolevi has assessed that student $i$ has $s_i$ smarts. When Uolevi was little, his mother told him that a group is as stupid as it's stupidest member. He took that advice to heart and is now going to divide the $n$ students to $k$ nonempty groups so that the total amount of smarts will be maximized according to this rule.

Formally, if group $S$ of size $x$ contains students $1, 2,\dots,x$, then each of the group's $x$ members will contribute $min_{i=1}^{x}{s_i}$ to the total sum of smarts. That is, group $S$ will contribute $x \times min_{i=1}^{x}{s_i}$ smarts in total.

Input

The first line contains two integers $n$ and $k$. The second line contains $n$ numbers $s_1,\,s_2,\dots,\,s_n$.

Output

Print $n$ numbers on a single. The $i$-th number indicates the group student $i$ belongs to. If there are multiple ways to group the students optimally, print any.

Constraints

• $1 \leq k \leq n \leq 500$
• $1 \leq s_i \leq 10^9$
• $1 \leq g_i \leq k$

Example 1

Input:

5 3
6 8 9 7 9

Output:

1 2 3 1 3

Example 2

Input:

10 5
10 8 10 1 2 4 10 2 3 1

Output:

5 4 5 1 2 3 5 2 2 1