Problem: All modern mobile applications are divided into free and paid. Even a single application developers often release two versions: a paid version without ads and a free version with ads.

<image>

Suppose that a paid version of the app costs p (p is an integer) rubles, and the free version of the application contains c ad banners. Each user can be described by two integers: ai — the number of rubles this user is willing to pay for the paid version of the application, and bi — the number of banners he is willing to tolerate in the free version.

The behavior of each member shall be considered strictly deterministic:

  * if for user i, value bi is at least c, then he uses the free version, 
  * otherwise, if value ai is at least p, then he buys the paid version without advertising, 
  * otherwise the user simply does not use the application. 



Each user of the free version brings the profit of c × w rubles. Each user of the paid version brings the profit of p rubles.

Your task is to help the application developers to select the optimal parameters p and c. Namely, knowing all the characteristics of users, for each value of c from 0 to (max bi) + 1 you need to determine the maximum profit from the application and the corresponding parameter p.

Input

The first line contains two integers n and w (1 ≤ n ≤ 105; 1 ≤ w ≤ 105) — the number of users and the profit from a single banner. Each of the next n lines contains two integers ai and bi (0 ≤ ai, bi ≤ 105) — the characteristics of the i-th user.

Output

Print (max bi) + 2 lines, in the i-th line print two integers: pay — the maximum gained profit at c = i - 1, p (0 ≤ p ≤ 109) — the corresponding optimal app cost. If there are multiple optimal solutions, print any of them.

Examples

Input

2 1
2 0
0 2


Output

0 3
3 2
4 2
2 2


Input

3 1
3 1
2 2
1 3


Output

0 4
3 4
7 3
7 2
4 2

Solution (in JAVA):

Solution:
import javafx.util.*;

import java.io.*;
import java.util.*;
import java.util.zip.CheckedOutputStream;

import static java.lang.Math.*;
import static java.util.Arrays.*;


public class Main{

    void run(){
        Locale.setDefault(Locale.US);
        boolean my;
        try {
            my = System.getProperty("MY_LOCAL") != null;
        } catch (Exception e) {
            my = false;
        }
        try{
            err = System.err;
            if( my ){
                sc  = new FastScanner(new BufferedReader(new FileReader("input.txt")));
//                sc  = new FastScanner(new BufferedReader(new FileReader("C:\\myTest.txt")));
                out = new PrintWriter   (new FileWriter("output.txt"));
            }
            else {
                sc  = new FastScanner( new BufferedReader(new InputStreamReader(System.in)) );
                out = new PrintWriter( new OutputStreamWriter(System.out));
            }
//            out = new PrintWriter(new OutputStreamWriter(System.out));
        }catch(Exception e){
            MLE();
        }
        if( my )
            tBeg = System.currentTimeMillis();
        solve();
        if( my )
            err.println( "TIME: " + (System.currentTimeMillis() - tBeg ) / 1e3 );
        exit(0);
    }

    void exit( int val ){
        err.flush();
        out.flush();
        System.exit(val);
    }

    double tBeg;
    FastScanner sc;
    PrintWriter out;
    PrintStream err;

    class FastScanner{

        StringTokenizer st;
        BufferedReader br;

        FastScanner( BufferedReader _br ){
            br = _br;
        }

        String readLine(){
            try {
                return br.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        String next(){
            while( st==null || !st.hasMoreElements() )
                st = new StringTokenizer(readLine());
            return st.nextToken();
        }

        int nextInt(){ return Integer.parseInt(next()); }
        long nextLong(){ return Long.parseLong(next()); }
        double nextDouble(){ return Double.parseDouble(next()); }
    }

    void MLE(){
        int[][] arr = new int[1024*1024][]; for( int i = 0; i < 1024*1024; ++i ) arr[i] = new int[1024*1024];
    }

    void MLE( boolean doNotMLE ){ if( !doNotMLE ) MLE(); }

    void TLE(){
        for(;;);
    }

    public static void main(String[] args) {
        new Main().run();
//        new Thread( null, new Runnable() {
//            @Override
//            public void run() {
//                new Main().run();
//            }
//        }, "Lolka", 256_000_000L ).run();
    }

    ////////////////////////////////////////////////////////////////

    Random rnd = new Random();

    int nextRnd( int l, int r ){
        return l + rnd.nextInt(r-l+1);
    }

    class Item{
        int a, b;

        public Item(int _a, int _b) {
            a = _a;
            b = _b;
        }
    }

    int n, w;
    int maxB;
    Item[] ord;

    int cntBlock, szBlock;
    int[] bestPrise;
    long[] bestProfit;
    int[] sumMan, // cnt man in block
            cnt; // cnt man with prize = a
    long[] doUpd;

    void init(){
        cntBlock = 444;
        szBlock = 444;
//        cntBlock = 10;
//        szBlock = 10;
        bestPrise = new int[cntBlock];
        bestProfit = new long[cntBlock];
        sumMan = new int[cntBlock];
        cnt = new int[cntBlock * szBlock];
        doUpd = new long[cntBlock];
        fill( doUpd, Long.MAX_VALUE );
    }

    int ansPrice;
    long ansProfit;
    private void getAns() {
        ansPrice = 0;
        ansProfit = 0;
        for (int b = 0; b < cntBlock; b++) {
            if( ansProfit < bestProfit[b] ){
                ansProfit = bestProfit[b];
                ansPrice = bestPrise[b];
            }
        }
    }

    private void addMan(int a) {
        int b = a / szBlock;

        ++cnt[a];
        ++sumMan[b];
        updPP( b );
        for (int block = 0; block < b; block++) {
            if( doUpd[block] <= 3 ){
                updPP( block );
            }
            else{
                bestProfit[block] += bestPrise[block];
                --doUpd[block];
            }
        }
    }

    void updPP( int block ){
        int l = block * szBlock, r = l + szBlock - 1;
        int cntBiggerMan;

        cntBiggerMan = 0; for (int b = block + 1; b < cntBlock; b++) cntBiggerMan += sumMan[b];

        bestPrise[block] = -1;
        bestProfit[block] = -1;
        for (int p = r; l <= p; p--) {
            cntBiggerMan += cnt[p];
            long curProfit = 1L * p * cntBiggerMan;
//            err.println( p +" "+ cntBiggerMan + " " + curProfit );
            if( bestProfit[block] < curProfit ){
                bestProfit[block] = curProfit;
                bestPrise[block] = p;
            }
        }

        doUpd[block] = Integer.MAX_VALUE;

        cntBiggerMan = 0; for (int b = block + 1; b < cntBlock; b++) cntBiggerMan += sumMan[b];

        for (int p = r; bestPrise[block] + 1 <= p; p--) {
            cntBiggerMan += cnt[p];
            long curProfit = 1L * p * cntBiggerMan;
            long curUpd =
                    (bestProfit[block] - curProfit + p-bestPrise[block]-1) / (p-bestPrise[block]);
            doUpd[block] = min( doUpd[block], curUpd );
        }
    }

    void solve(){

        n = sc.nextInt();
        w = sc.nextInt();
        ord = new Item[n];
        for (int i = 0; i < n; i++) {
            ord[i] = new Item(sc.nextInt(),sc.nextInt());
            maxB = max( maxB, ord[i].b );
        }
        sort( ord, (l,r)-> Integer.compare(l.b,r.b) );
        init();
        for( int pos = 0, c = 0; c <= maxB+1; ++c ){
            while( pos < n && ord[pos].b < c ){
                addMan(ord[pos].a);
                ++pos;
            }
            getAns();
            ansProfit += 1L * (n - pos) * w * c;
            out.println( ansProfit +" "+ ansPrice );
        }
    }




}