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