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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

//import Number_theory.pair;

public class hacker49 {
	public static int r1=0;
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
	static class pair{
		private long cnt;
		private long[] fq;
		private long[] pref;
		pair(){
			fq=new long[41];
			pref=new long[41];
			cnt=(long)0;
		}	
	}
//	static long ans(long n,long k,long a,long b) {
//		if(k==1) {
//			return (long)((n-1)*a);
//		}
//		if(n==1) {
//			return 0;
//		}
//		if(n<k) {
//			return (long)(a*(n-1));
//		}
//		if(n==k) {
//			return (long)Math.min(b,(k-1)*a);
//		}
//		if(n%k==0) {
////			long f1=(long)(b+(long)ans(n/k,k,a,b));
//			long g=n-(n/k);
//			long f2=g*a;
//			if(f2<b) {
//				return (long)(f2+(long)ans(n/k,k,a,b));
//			}else {
//				return (long)(b+ans(n/k,k,a,b));
//			}
////			long f2=(long)((long)(g*a)+(long)ans(n/k,k,a,b));
////			return (long)Math.min(f1, f2);
//		}else {
//			long d=(long)(n%k);
//			n-=d;
//			return (long)((long)d*a+(long)ans(n,k,a,b));
//		}
//	}
	static class pair3{
		private int a;
		private int b;
		pair3(int a,int b){
			this.a=a;
			this.b=b;
		}
	}

	static long get(int i,int k,int[] a,int n) {
		if(i>n) {
			return 0;
		}
		if(i==n) {
			if(k%2!=0) {
				return a[n]; 
			}else {
				return 0;
			}
		}
		if(k%2!=0) {
			long a1=Long.MAX_VALUE;
			long a2=Long.MAX_VALUE;
			if(a[i]==0 && a[i+1]==0) {
				a2=get(i+2,k+1,a,n);
			}else if(a[i]==0) {
				a1=get(i+1,k+1,a,n);
			}else if(a[i+1]==0) {
				a2=get(i+2,k+1,a,n)+1;
			}else {
				a1=get(i+1,k+1,a,n)+1;
			}
			return Math.min(a1, a2);
		}else {
			long a1=Long.MAX_VALUE;
			long a2=Long.MAX_VALUE;
			
			if(a[i]==1 && a[i+1]==1) {
				a2=get(i+2,k+1,a,n);
			}else if(a[i]==1) {
				a1=get(i+1,k+1,a,n);
			}else if(a[i+1]==1) {
				a2=get(i+2,k+1,a,n);
			}else {
				a1=get(i+1,k+1,a,n);
			}
			return Math.min(a1, a2);
			
		}
		
		
	}
	
	
	
	
	
	
	
	
	static HashMap<Long,Integer> e=new HashMap<>();
	public static void main(String[] args) {
		OutputStream outputStream =System.out;
	    PrintWriter out =new PrintWriter(outputStream);
		FastReader s=new FastReader();
int n=s.nextInt();
int m=s.nextInt();
long[] b=new long[n];
for(int i=0;i<n;i++) {
	b[i]=s.nextLong();
}
long[] a=merge_sort(b,0,n-1);

long[] dp=new long[n+1];
long[] pre=new long[n+1];
for(int i=1;i<=n;i++) {
	if(i==1) {
		pre[i]=a[0];
	}else {
		pre[i]=pre[i-1]+a[i-1];
	}
}
//for(int i=0;i<n;i++) {
//	System.out.print(pre[i]+" ");
//}
for(int i=1;i<=n;i++) {
	if(i<=m) {
		dp[i]=pre[i];
	}else {
		dp[i]=dp[i-m]+pre[i];
		
	}
}
for(int i=1;i<=n;i++) {
	out.print(dp[i]+	" ");
}
out.close();       
	}
	static long max=Long.MIN_VALUE;
	static void ans1(int i,long sum,int count,int n,long[] a) {
		if(i>n) {
			max=Math.max(max, count);
			return;
			
		}
		if(sum+a[i]>=0) {
			ans1(i+1,sum+a[i],count+1,n,a);
			ans1(i+1,sum,count,n,a);
		}else {
			ans1(i+1,sum,count,n,a);
			
		}
	}
	static int nextPowerOf2(int n) 
	{ 
	    n--; 
	    n |= n >> 1; 
	    n |= n >> 2; 
	    n |= n >> 4; 
	    n |= n >> 8; 
	    n |= n >> 16; 
	    n++; 
	      
	    return n; 
	} 
//	static class node{
//		private int a;
//		private int b;
//		private int c;
//		private int d;
//		
//	}
	static ArrayList<Integer>[][] f1=new ArrayList[101][101];
	static boolean[][] vis=new boolean[101][101];
public static void dfs(int node,int c) {
	vis[c][node]=true;
	for(int i=0;i<f1[c][node].size();i++) {
		if(!vis[c][f1[c][node].get(i)]) {
			dfs(f1[c][node].get(i),c);
		}
	}
}
	
	
	public static class node{
		private int a;
		private int b;
		node(int a,int b){
			this.a=a;
			this.b=b;
		}
	}

	public static long GCD(long a,long b) {
		if(b==(long)0) {
			return a;
		}
		return GCD(b , a%b);
	}
	public static void Create(node[] arr,node[] segtree,int low,int high,int pos) {
		if(low==high) {
			segtree[pos]=arr[low];
			return;
		}
		int mid=(low+high)/2;
		Create(arr,segtree,low,mid,2*pos+1);
		Create(arr,segtree,mid+1,high,2*pos+2);
		if(segtree[2*pos+1].a+segtree[2*pos+2].a>=10) {
			int a=segtree[2*pos+1].a;
			int b=segtree[2*pos+2].a;
			int c=segtree[2*pos+1].b;
			int d=segtree[2*pos+2].b;
			segtree[pos]=new node((a+b)%10,1+c+d);
		}else {
			int a=segtree[2*pos+1].a;
			int b=segtree[2*pos+2].a;
			int c=segtree[2*pos+1].b;
			int d=segtree[2*pos+2].b;
			segtree[pos]=new node(a+b,c+d);
			
		}
	}
	public static node Query(node[] segtree,int qlow,int qhigh,int low,int high,int pos) {
		if(low>=qlow && high<=qhigh) {
			return segtree[pos];
		}
		if(qhigh<low || qlow>high) {
			return new node(0,0);
		}
		int mid=(low+high)/2;
	 node a=Query(segtree,qlow,qhigh,low,mid,2*pos+1);
	node b=Query(segtree,qlow,qhigh,mid+1,high,2*pos+2);
	int c=a.a;
	int d=b.a;
	if(c+d>=10) {
	node e=new node((c+d)%10,1+a.b+b.b);
	return e;
	}else {
		node e=new node(c+d,a.b+b.b);
		return e;
	}
	}
	
	static class pair1 implements Comparable<pair1>{
		private int a;
		private int b;
		private int c;
		private int d;
		pair1(int a,int b,int c,int d){
			this.a=a;
			this.b=b;
			this.c=c;
			this.d=d;
		}
		public int compareTo(pair1 o) {
			if(this.a<o.a) {
				return 1;
			}else if(this.a==o.a) {
				if(this.b<o.b) {
					return 1;
				}else {
					return -1;
				}
			}else {
				return -1;
			}
				
		}
	}
//	public static class pair5{
//		private int a;
//		private int b;
//		pair5(int a,int b){
//			this.a=a;
//			this.b=b;
//		}
//		public int compareTo(pair5 o) {
//			return Integer.compare(o.b, this.b);
//		}
//	}
//	public static pair5[] merge_sort(pair5[] A, int start, int end) {
//		if (end > start) {
//			int mid = (end + start) / 2;
//			pair5[] v = merge_sort(A, start, mid);
//			pair5[] o = merge_sort(A, mid + 1, end);
//			return (merge(v, o));
//		} else {
//			pair5[] y = new pair5[1];
//			y[0] = A[start];
//			return y;
//		}
//	}
//	public static pair5[] merge(pair5 a[], pair5 b[]) {
////		int count=0;
//		pair5[] temp = new pair5[a.length + b.length];
//		int m = a.length;
//		int n = b.length;
//		int i = 0;
//		int j = 0;
//		int c = 0;
//		while (i < m && j < n) {
//			if (a[i].a < b[j].a) {
//				temp[c++] = a[i++];
//			} else {
//				temp[c++] = b[j++];
//			}
//		}
//		while (i < m) {
//			temp[c++] = a[i++];
//		}
//		while (j < n) {
//			temp[c++] = b[j++];
//		}
//		return temp;
//	}
////	
	public static int upper_bound(int[] a ,int n,int x) {
		int l=-1;
		int r=n;
		while(r>l+1) {
			int mid=(l+r)/2;
			if(a[mid]<x) {
				l=mid;
			}else {
				r=mid;
			}
		}
		return r;
				
	}

//	
//	
	public static int lower_bound(int[] a ,int n,int x) {
		int l=-1;
		int r=n;
		while(r>l+1) {
			int mid=(l+r)/2;
			if(a[mid]<=x) {
				l=mid;
			}else {
				r=mid;
			}
		}
		return l;
				
	}
	public static int ty(int[] a, int x, int y)
    {
        Arrays.sort(a);
        int count=0;
        int n=a.length;
        for(int i=0;i<n;i++) {
        	int g=0;
        	if(x%a[i]==0) {
        		g=x/a[i];
        	}else {
        		g=x/a[i]+1;
        	}
        	int k1=upper_bound(a,n,g);
        	if(k1==n) {
        		count+=0;
        	}else {
        		int g1=0;
            	if(y%a[i]==0) {
            		g1=y/a[i];
            	}else {
            		g1=y/a[i]+1;
            	}
            	int k2=lower_bound(a,n,g1);
            	if(k2>=k1) {
            		count+=(k2-k1+1);
            	}
        	}
//        System.out.println(count);
        }
        return count;
        
    }
	static boolean isValid(int x,int y,int n,int m) {
		if(x>=1 && x<=n && y>=1 && y<=m) {
			return true;
		}else {
			return false;
		}
	}
	
	static long[] fac=new long[1000001];
	static void fac() {
		fac[0]=1;
		for(int i=1;i<=1000000;i++) {
			fac[i]=((fac[i-1]%mod)*(i%mod))%mod;
		}
	}
	static ArrayList<Integer>[] f=new ArrayList[2001];
	public static void init(int n) {
		
		for(int j=1;j<=n;j++) {
		for (int l=1; l<=Math.sqrt(j); l++)
        {
            if (j%l==0)
            {
                // If divisors are equal, print only one
                if (j/l == l) {
                    f[j].add(l);}
      
                else { // Otherwise print both
//                    System.out.print(i+" " + n/i + " " );
            f[j].add(l);
            f[j].add(j/l);
                }
                
            }
        }
		
		}
		
	}
	
	public static long[] merge_sort(long[] A, int start, int end) {
		if (end > start) {
			int mid = (end + start) / 2;
			long[] v = merge_sort(A, start, mid);
			long[] o = merge_sort(A, mid + 1, end);
			return (merge(v, o));
		} else {
			long[] y = new long[1];
			y[0] = A[start];
			return y;
		}
	}
	public static long[] merge(long a[], long b[]) {
//		int count=0;
		long[] temp = new long[a.length + b.length];
		int m = a.length;
		int n = b.length;
		int i = 0;
		int j = 0;
		int c = 0;
		while (i < m && j < n) {
			if (a[i] < b[j]) {
				temp[c++] = a[i++];
			
			} else {
				temp[c++] = b[j++];
			}
		}
		while (i < m) {
			temp[c++] = a[i++];
		}
		while (j < n) {
			temp[c++] = b[j++];
		}
		return temp;
	}
	
	public static long[] merge_sort1(long[] A, int start, int end) {
		if (end > start) {
			int mid = (end + start) / 2;
			long[] v = merge_sort1(A, start, mid);
			long[] o = merge_sort1(A, mid + 1, end);
			return (merge1(v, o));
		} else {
			long[] y = new long[1];
			y[0] = A[start];
			return y;
		}
	}
	public static long[] merge1(long a[], long b[]) {
//		int count=0;
		long[] temp = new long[a.length + b.length];
		int m = a.length;
		int n = b.length;
		int i = 0;
		int j = 0;
		int c = 0;
		while (i < m && j < n) {
			if (a[i] < b[j]) {
				temp[c++] = a[i++];
			
			} else {
				temp[c++] = b[j++];
			}
		}
		while (i < m) {
			temp[c++] = a[i++];
		}
		while (j < n) {
			temp[c++] = b[j++];
		}
		return temp;
	}
	
	static long mod=1000000007;
	static class pair2{
		private long a;
		private int b;
		pair2(long a,int b){
			this.a=a;
			this.b=b;
		}
	}
	




//	for(int i=2;i<=100000;i++) {
		
	
}