Alice có \(n\) gói kẹo, gói thứ \(i\) có \(a_{i}\) cái kẹo. Alice muốn chia các gói kẹo thành \(k\) phần có số kẹo bằng nhau.
Yêu cầu: Cho \(a_{1}, a_{2}, \ldots, a_{n}\) và số nguyên dương \(k\), hãy giúp Alice đưa ra một phương án chia kẹo.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, k\) \((k \leq n)\).
• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) \((a_{i} \leq 10^{9})\).

Output

• In ra \(n\) số nguyên, trong đó, số thứ \(i\) \((1 \leq i \leq n)\) bằng \(p_{i}\) cho biết gói thứ \(i\) được xếp vào phần \(p_{i}\) \((1 \leq p_{i} \leq k)\). Nếu không tồn tại phương án chia kẹo ghi số \(−1\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \leq 10\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 20\).
• Subtask \(3\) (\(20\%\) số điểm): \(k = 3, n \leq 100, a_{i} \leq 100\).
• Subtask \(4\) (\(10\%\) số điểm): \(k = 3, n \leq 10^{6}, a_{i} = i\)
• Subtask \(5\) (\(20\%\) số điểm): \(k \leq 10, n \leq 10^{6}, a_{i} = i\)

Example

5 3
1 2 3 4 5

1 2 2 1 3