You are given sequence A₁, A₂, ... A_n and integer k. For each integer i (0 ≤ i < k) find such nonempty subsequence of A so that sum of numbers in this subsequence is maximal possible and remainder of integer division of this sum by k is equal to i.

Input

In first line numbers n and k (1 ≤ n ≤ 10⁶, 1 ≤ k ≤ 200).

In second line: n numbers representing sequence A (1 ≤ A_i ≤ 10⁹). 

Output

Print k numbers in one line. i'th number represent sum of numbers in subsequence for number i - 1. If there is no such subsequence print -1.

Example

Input:
6 5
2 8 10 44 15 32
Output:
65 111 77 103 109