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 java.io.*;
import java.util.*;
import java.util.zip.CheckedOutputStream;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Banners {
    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")));
                out = new PrintWriter(new FileWriter("output.txt"));
            } else {
                sc = new FastScanner(new BufferedReader(new InputStreamReader(
                        System.in)));
                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 Banners().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;
    long[] doUpd;

    void init() {
        cntBlock = 317;
        szBlock = 317;
        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] <= 1) {
                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;
            if (bestProfit[block] < curProfit) {
                bestProfit[block] = curProfit;
                bestPrise[block] = p;
            }
        }
        cntBiggerMan = 0;
        for (int b = block + 1; b < cntBlock; b++) {
            cntBiggerMan += sumMan[b];
        }
        doUpd[block] = Integer.MAX_VALUE;
        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 );
        }
    }
}