KNMD - Subsequences with modulo

no tags 

You are given sequence A1, A2, ... An 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 ≤ 106, 1 ≤ k ≤ 200).

In second line: n numbers representing sequence A (1 ≤ Ai ≤ 109)

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

hide comments
Pawe³ Ma¶luch: 2021-07-28 00:55:46

Any hint how to achieve a good complexity?

Alex Anderson: 2015-11-08 08:47:24

k should be larger.

Rishav Goyal: 2015-08-25 08:08:56

if these is no sequence for i, then print -1 for just i. and consider other i's independent from this event.


Added by:Bartek
Date:2015-08-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY