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.util.*;
import java.math.*;
import java.io.*; 
 public class A{

static FastReader scan=new FastReader();
 public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
  static LinkedList<Integer>edges[];
  static boolean stdin = true;
    static String filein = "input";
    static String fileout = "output";
static int dx[] = { -1, 0, 1, 0 };
static int dy[] = { 0, 1, 0, -1 };
int dx_8[]={1,1,1,0,0,-1,-1,-1};
int dy_8[]={-1,0,1,-1,1,-1,0,1};
static char sts[]={'U','R','D','L'};
static boolean prime[];
static long LCM(long a,long b){
    return (Math.abs(a*b))/gcd(a,b);
   }
    public static int upperBound(long[] array, int length, long value) {
        int low = 0;
        int high = length;
        while (low < high) {
            final int mid = low+(high-low) / 2;
            if ( array[mid]>value) {
                high = mid ;
            } else {
                low = mid+1;
            }
        }
        return low;
    }
   static long gcd(long a, long b) {
    if(a!=0&&b!=0)
        while((a%=b)!=0&&(b%=a)!=0);
    return a^b;
}
static int countSetBits(int n) 
    { 
        int count = 0; 
        while (n > 0) { 
            if((n&1)!=1)
                count++;
            //count += n & 1; 
            n >>= 1; 
        } 
        return count; 
    } 
 static void sieve(long n) 
    { 
        
        prime = new boolean[(int)n+1]; 
        for(int i=0;i<n;i++) 
            prime[i] = true; 
          
        for(int p = 2; p*p <=n; p++) 
        { 
           
            if(prime[p] == true) 
            { 
                
                for(int i = p*p; i <= n; i += p) 
                    prime[i] = false; 
            } 
        } 
    }  
  
 
 
           static boolean isprime(long x)
           {
            for(long i=2;i*i<=x;i++)
                if(x%i==0)
                    return false;
                return true;
           }
           static int perm=0,FOR=0;
           
     

static boolean flag=false;
static int len=100000000;

static ArrayList<Pair>inters=new ArrayList<Pair>();





static StringBuilder sb;
static void swap(int i,int j,StringBuilder st)
{
    char tmp=st.charAt(i);
    st.setCharAt(i,st.charAt(j));
    st.setCharAt(j,tmp);
}


 private static int next(int[] arr, int target)  
    {  
        int start = 0, end = arr.length - 1;  
    
        int ans = -1;  
        while (start <= end) {  
            int mid = (start + end) / 2;  
    
            // Move to right side if target is  
            // greater.  
            if(arr[mid]==target)
                return mid;
            if (arr[mid] <target) {  
                start = mid + 1;  
            }  
    
            // Move left side.  
            else {  
                ans = mid;  
                end = mid - 1;  
            }  
        }  
        return ans;  
    }  
//static boolean vis[][];
    static long solve(int h,long n,int cur)
    {
        if(h==0)
            return 0;
        long half=1L<<(h-1);
        if(n<=half)
        {
            if((cur^1)==0)
                return 1+solve(h-1,n,0);
            else 
                return 2*half+solve(h-1,n,0);
        }
        else 
        {
              if((cur^1)==0)
             return 2*half+solve(h-1,n-half,1);
            else 
                return 1+solve(h-1,n-half,1);
        }
    }

  
public static class comp1 implements Comparator<String>{  
public int compare(String o1,String o2){
return o1.length()-o2.length(); 
}
  }
  public static class comp2 implements Comparator<String>{  
public int compare(String o1,String o2){
return o1.compareTo(o2); 
}
  }
  static StringBuilder a,b;

    static boolean isPowerOfTwo(int n)
{
    if(n==0)
    return false;
 
return (int)(Math.ceil((Math.log(n) / Math.log(2)))) == 
       (int)(Math.floor(((Math.log(n) / Math.log(2)))));
}
static ArrayList<Integer>v;
static ArrayList<Integer>pows;
static void block(long x) 
{ 
   v = new ArrayList<Integer>(); 
      
    pows=new ArrayList<Integer>();
   
    while (x > 0)  
    { 
        v.add((int)x % 2); 
        x = x / 2; 
    } 
  
    // Displaying the output when 
    // the bit is '1' in binary 
    // equivalent of number. 
    for (int i = 0; i < v.size(); i++)  
    { 
        if (v.get(i)==1)  
        { 
      pows.add(i); 
        } 
    } 

} 


   static long mod=(long)(1e9)+7;
    static int countWaysUtil(int x, int n, int num) 
    { 
        // Base cases 
        int val = (int) (x - Math.pow(num, n)); 
        if (val == 0) 
            return 1; 
        if (val < 0) 
            return 0; 
       
        // Consider two possibilities, num is 
        // included and num is not included. 
        return countWaysUtil(val, n, num + 1) + 
               countWaysUtil(x, n, num + 1); 
    }
       static int countWays(int x, int n) 
    { 
        return countWaysUtil(x, n, 1); 
    } 
   
        
        static ArrayList<Integer>arr;
        static int n,k;
        static int dp[][];
        static int rec(int l,int r,int i,int j)
        {
            if(i>j)
            {
                if(r-l>k)
                    return (int)1e7+5;

                return 0;
            }
             if(r-l<=k)
                return 0;
            int x=(int)1e7+5;
            if(dp[l][r]!=-1)
                return dp[l][r];
            if(arr.get(i)-l<=k)
            {
                return x=Math.min(rec(arr.get(i),r,i+1,j)+1,rec(l,r,i+1,j));
            }
            else if(r-arr.get(j)<=k)
            {
                x=Math.min(rec(l,arr.get(j),i,j-1)+1,rec(l,r,i,j-1));
            }

            return dp[l][r]=x;
        }
        static long l,r;
       static long createPalindrome(long input, long b, long isOdd) {
    long n = input;
    long palin = input;
  
    // checks if number of digits is odd or even
    // if odd then neglect the last digit of input in
    // finding reverse as in case of odd number of
    // digits middle element occur once
    if (isOdd == 1)
        n /= b;
  
    // Creates palindrome by just appending reverse
    // of number to itself
    while (n > 0) {
        palin = palin * b + (n % b);
        n /= b;
    }
    return palin;
}
  
// Function to print decimal 
// palindromic number
static ArrayList<Long>pals=new ArrayList<Long>();
static void generatePalindromes(long n) {
    long number;
  
    // Run two times for odd and even 
    // length palindromes
    for (long j = 0; j < 2; j++) {
  
    // Creates palindrome numbers with first 
    // half as i. Value of j decided whether
    // we need an odd length of even length
    // palindrome.
        long i = 1;
        while ((number = createPalindrome(i, 10, j % 2)) <= n) {
            if(number>=l)
                pals.add(number);
            i++;
    }
    }
}
static boolean isPalindrome(String str)
    {
 
        // Pointers pointing to the beginning
        // and the end of the string
        int i = 0, j = str.length() - 1;
 
        // While there are characters to compare
        while (i < j) {
 
            // If there is a mismatch
            if (str.charAt(i) != str.charAt(j))
                return false;
 
            // Increment first pointer and
            // decrement the other
            i++;
            j--;
        }
 
        // Given string is a palindrome
        return true;
    }

public static void main(String[] args)  throws Exception 
{
//SUCK IT UP AND DO IT ALRIGHT
//scan=new FastReader("div7.in");
//out = new PrintWriter("div7.out");
   //System.out.println(countSetBits(2015));
    //int elem[]={1,2,3,4,5};
//System.out.println("avjsmlfpb".compareTo("avjsmbpfl"));
int tt=1;
/*for(int i=0;i<=100;i++)
    if(prime[i])
        arr.add(i);
    System.out.println(arr.size());*/
   // check(new StringBuilder("05:11"));
   // System.out.println(26010000000000L%150);
// tt=scan.nextInt();
  //  System.out.println(2^6^4);
    //StringBuilder o=new StringBuilder("GBGBGG");
    //o.insert(2,"L");


outer:while(tt-->0)
{
    int n=scan.nextInt(),m=scan.nextInt();
    long arr[]=new long[n];
    for(int i=0;i<n;i++)
        arr[i]=scan.nextLong();
    Arrays.sort(arr);
    long res=0;
    long cur=0;
    long pre[]=new long[n];
    //pre[0]=arr[0];
    long yes=0;
    for(int i=0;i<n;i++)
    {
        //res=cur;
        res+=arr[i];
        pre[i]+=res;
         if(i-m>=0){
    //res+=arr[i];
         pre[i]+=pre[i-m];
     }
        out.print(pre[i]+" ");
    }


}
out.close();

//SEE UP 

}
static class special{
    char c;
    int idx;
    special(char c,int idx)
    {
        this.c=c;
        this.idx=idx;
    }
}
static long binexp(long a,long n)
{
    if(n==0)
        return 1;
    long res=binexp(a,n/2);
    if(n%2==1)
        return res*res*a;
    else 
        return res*res;
}
static long fastPow(int base, int pow) {
        if (pow==0)
            return 1;
        long half=fastPow(base, pow/2);
        if (pow%2==0)
            return half*half%mod;
        return half*half%mod*base%mod;
    }
static long powMod(long base, long exp, long mod) {
       if (base == 0 || base == 1) return base;
       if (exp == 0) return 1;
       if (exp == 1) return (base % mod+mod)%mod;
       long R = (powMod(base, exp/2, mod) % mod+mod)%mod;
       R *= R;
       R %= mod;
       if ((exp & 1) == 1) {
           return (base * R % mod+mod)%mod;
       }
       else return (R %mod+mod)%mod;
   }
static double dis(double x1,double y1,double x2,double y2)
{
    return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
static long mod(long x,long y)
    {
        if(x<0)
            x=x+(-x/y+1)*y;
        return x%y;
    }
 public static  long pow(long b, long e) {
            long r = 1;
            while (e > 0) {
                if (e % 2 == 1) r = r * b ;
                b = b * b;
                e >>= 1;
            }
            return r;
        }
private static void sort(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int object : arr) list.add(object);
        Collections.sort(list);
    //Collections.reverse(list);
        for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
    }
private static void sort2(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int object : arr) list.add(object);
        Collections.sort(list);
    Collections.reverse(list);
        for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
    }
 public static class FastReader {
        BufferedReader br;
        StringTokenizer root;
        
 
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        FastReader(String filename)throws Exception
        {

            br=new BufferedReader(new FileReader(filename));
        }

        boolean hasNext(){
            String line;
            while(root.hasMoreTokens())
                return true;
            return false;
        }
 
        String next() {
            while (root == null || !root.hasMoreTokens()) {
                try {
                    root = new StringTokenizer(br.readLine());
                } catch (Exception addd) {
                    addd.printStackTrace();
                }
            }
            return root.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
 
        double nextDouble() {
            return Double.parseDouble(next());
        }
 
        long nextLong() {
            return Long.parseLong(next());
        }
 
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (Exception addd) {
                addd.printStackTrace();
            }
            return str;
        }
         public int[] nextIntArray(int arraySize) {
            int array[] = new int[arraySize];
 
            for (int i = 0; i < arraySize; i++) {
                array[i] = nextInt();
            }
 
            return array;
        }
}
 static class Pair implements Comparable<Pair>{
        public long x, y;
        public Pair(long x1, long y1) {
            x=x1;
            y=y1;
        }
        @Override
        public int hashCode() {
            return (int)(x + 31 * y);
        }
        public String toString() {
            return x + " " + y;
        }
        @Override
        public boolean equals(Object o){
            if (o == this) return true;
            if (o.getClass() != getClass()) return false;
            Pair t = (Pair)o;
            return t.x == x && t.y == y;
        }
public int compareTo(Pair o)
{
    return (int)(o.y-y);

    }

}
 static class tuple{
        int x,y,z;
        tuple(int a,int b,int c){
            x=a;
            y=b;
            z=c;
        }
    }
    static class Edge{
        int d,w;
        Edge(int d,int w)
        {
            this.d=d;
            this.w=w;
        }
    }
}









