Tsumugi brought n delicious sweets to the Light Music Club. They are numbered from 1 to n, where the i-th sweet has a sugar concentration described by an integer a_i.

Yui loves sweets, but she can eat at most m sweets each day for health reasons.

Days are 1-indexed (numbered 1, 2, 3, …). Eating the sweet i at the d-th day will cause a sugar penalty of (d ⋅ a_i), as sweets become more sugary with time. A sweet can be eaten at most once.

The total sugar penalty will be the sum of the individual penalties of each sweet eaten.

Suppose that Yui chooses exactly k sweets, and eats them in any order she wants. What is the minimum total sugar penalty she can get?

Since Yui is an undecided girl, she wants you to answer this question for every value of k between 1 and n.

Input

The first line contains two integers n and m (1 ≤ m ≤ n ≤ 200\ 000).

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 200\ 000).

Output

You have to output n integers x_1, x_2, …, x_n on a single line, separed by spaces, where x_k is the minimum total sugar penalty Yui can get if she eats exactly k sweets.

Examples

Input


9 2
6 19 3 4 4 2 6 7 8


Output


2 5 11 18 30 43 62 83 121


Input


1 1
7


Output


7

Note

Let's analyze the answer for k = 5 in the first example. Here is one of the possible ways to eat 5 sweets that minimize total sugar penalty:

  * Day 1: sweets 1 and 4 
  * Day 2: sweets 5 and 3 
  * Day 3 : sweet 6 



Total penalty is 1 ⋅ a_1 + 1 ⋅ a_4 + 2 ⋅ a_5 + 2 ⋅ a_3 + 3 ⋅ a_6 = 6 + 4 + 8 + 6 + 6 = 30. We can prove that it's the minimum total sugar penalty Yui can achieve if she eats 5 sweets, hence x_5 = 30.


import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;


public class wef {
public static class FastReader {
	BufferedReader br;
	StringTokenizer st;
	//it reads the data about the specified point and divide the data about it ,it is quite fast
	//than using direct 

	public FastReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	String next() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (Exception r) {
				r.printStackTrace();
			}
		}
		return st.nextToken();
	}

	int nextInt() {
		return Integer.parseInt(next());//converts string to integer
	}

	double nextDouble() {
		return Double.parseDouble(next());
	}

	long nextLong() {
		return Long.parseLong(next());
	}

	String nextLine() {
		String str = "";
		try {
			str = br.readLine();
		} catch (Exception r) {
			r.printStackTrace();
		}
		return str;
	}
}
static ArrayList<String>list1=new ArrayList<String>();
static void combine(String instr, StringBuffer outstr, int index,int k)
{
	if(outstr.length()==k)
	{
		list1.add(outstr.toString());return;
	}
	if(outstr.toString().length()==0)
	outstr.append(instr.charAt(index));
    for (int i = 0; i < instr.length(); i++)
    {
        outstr.append(instr.charAt(i));
       
        combine(instr, outstr, i + 1,k);
        outstr.deleteCharAt(outstr.length() - 1);
    }
   index++;
} 
static ArrayList<ArrayList<Integer>>l=new ArrayList<>();
static void comb(int n,int k,int ind,ArrayList<Integer>list)
{
	if(k==0)
	{
		l.add(new ArrayList<>(list));

		return;
	}
	
	
	for(int i=ind;i<=n;i++)
	{
		list.add(i);
		comb(n,k-1,ind+1,list);
		
		list.remove(list.size()-1);
		
	}
	
	
	
	
	

}
static long sum(long n)
{
	long sum=0;
	while(n!=0)
	{
		sum+=n%10;
		n/=10;
	}
	return sum;
}


static boolean check(HashMap<Integer,Integer>map)
{
	for(int h:map.values())
		if(h>1)
			return false;
	return true;
}

static class Pair implements Comparable<Pair>{
    int x;int y;
    Pair(int x,int y){
        this.x=x;
        this.y=y;
      //  this.i=i;
    }
	@Override
	public int compareTo(Pair o) {
		// TODO Auto-generated method stub
		return x-o.x;
		
	}
}
static long ncr(long n, int k) 
{ long m=(long)1e9+7;
    long C[] = new long[k + 1]; 
     
    // nC0 is 1 
    C[0] = 1;   
   
    for (int i = 1; i <= n; i++) 
    { 
        // Compute next row of pascal  
        // triangle using the previous row 
        for (int j = Math.min(i, k); j > 0; j--) 
            C[j] = (C[j]%m + C[j-1]%m)%m; 
    } 
    return C[k]%m; 
} 
static boolean isPrime(int n) 
{ 
    // Corner cases 
    if (n <= 1) 
        return false; 
    if (n <= 3) 
        return true; 
  
    // This is checked so  
    // that we can skip 
    // middle five numbers 
    // in below loop 
    if (n % 2 == 0 ||  
        n % 3 == 0) 
        return false; 
  
    for (int i = 5; 
             i * i <= n; i = i + 6) 
        if (n % i == 0 || 
            n % (i + 2) == 0) 
            return false; 
  
    return true; 
} 
static long pow(long a, long n, long mod) {
	//		a %= mod;
	long ret = 1;
	int x = 63 - Long.numberOfLeadingZeros(n);
	for (; x >= 0; x--) {
		ret = ret * ret % mod;
		if (n << 63 - x < 0)
			ret = ret * a % mod;
	}
	return ret;
}



static int maxsum=0;
static long dp[]=new long[100000];
static long recur(int a[],int ind,int tempsum)
 {
	 if(ind>=a.length)
	 {//System.out.println(tempsum);
		 if(maxsum==0)
			 maxsum=tempsum;
		 else
		 maxsum=Math.max(maxsum, tempsum);
		 return maxsum;
	 }
	 if(dp[ind]!=-1)
		 return dp[ind];
	 
	// System.out.println(tempsum);
	 int ct=0;
	 for(int i=ind;i<ind+(a.length-ind)/2;i++)
	 {ct++;
//	 if(ind+ct<a.length)
	 {	 tempsum+=a[i];
		 
		dp[i]= recur(a,ind+(2*ct),tempsum);}
		 
	 }
	 
	 return dp[ind];
 }
 static int gcd(int a,int b)
 {
	 if(b==0)
		 return a;
	 return gcd(b,a%b);
 }
 static int lcm(int a,int b)
 {
	 return (a*b)/gcd(a,b);
 }
 
  static int power(int n,int pow)
  {
	  if(pow==1)
		  return n;
	  else if(pow%2==0)
	  {
		  return power(n*n,pow/2);
	  }
	  else
		  return n*power(n*n,pow/2);
  }
 
 
 static HashSet<Long> factorize(long n) {
	    HashSet<Long> facts=new HashSet<Long>();
	    for (long i = 2; i * i <= n; ++i) {
	        while (n % i == 0) {
	            facts.add(i);
	            n /= i;
	        }
	    }
	 
	    if (n != 1) {
	        facts.add(n);
	    }
	    return facts;
	}
 static int count;static boolean vis[];
 static void dfs(ArrayList a[],boolean vis[],int v)
 {
	 if(vis[v]==true)
		 return;
	 
	 vis[v]=true;
	 count++;
	 for(Object h:a[v])
	 {
		 if(vis[(int) h]==false)
		 {
			 dfs(a,vis,(int)h);
		 }
	 }
	 
 }
 static int find(int parent[],int a)
 {
	 if(parent[a]!=a)
		 parent[a]= find(parent,parent[a]);
	 return parent[a];
 }
 
public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));

	public static void main(String[] args) {
		// TODO Auto-generated method stub
	FastReader in=new FastReader();
	TreeMap<Long,Integer>map=new TreeMap<Long,Integer>();
	ArrayList<Long>list=new ArrayList<Long>();
//	HashSet<Integer>set=new HashSet<Integer>();
	HashSet<Integer>set=new HashSet<Integer>();
	Deque<Integer>qu=new LinkedList<Integer>();
	
		
	
	int n=in.nextInt();
	int m=in.nextInt();
	
	long a[]=new long[n];
	long sum[]=new long[n];
	
	for(int i=0;i<n;i++)
		a[i]=in.nextLong();
	Arrays.sort(a);
	sum[0]=a[0];
	for(int i=1;i<n;i++)
		sum[i]=a[i]+sum[i-1];
	long pre[]=new long[n];
	
	
	for(int i=0;i<m;i++)
		pre[i]=a[i];
	for(int i=m;i<n;i++)
		pre[i]=a[i]+pre[i-m];
	
	
	
	for(int i=0;i<n;i++)
	{
		if(i-m>=0)
		{
			list.add(a[i]+pre[i-m]+list.get(list.size()-1));
		}
		else
		{
			list.add(sum[i]);
		}
		
	}
	for(long h:list)
		out.print(h+" ");
	out.flush();
	
	
	
	
	
	
	
	
	
	
	
	
	
	}
	
 }
