Problem: There is a grid of squares with H+1 horizontal rows and W vertical columns.

You will start at one of the squares in the top row and repeat moving one square right or down. However, for each integer i from 1 through H, you cannot move down from the A_i-th, (A_i + 1)-th, \ldots, B_i-th squares from the left in the i-th row from the top.

For each integer k from 1 through H, find the minimum number of moves needed to reach one of the squares in the (k+1)-th row from the top. (The starting square can be chosen individually for each case.) If, starting from any square in the top row, none of the squares in the (k+1)-th row can be reached, print `-1` instead.

Constraints

* 1 \leq H,W \leq 2\times 10^5
* 1 \leq A_i \leq B_i \leq W

Input

Input is given from Standard Input in the following format:


H W
A_1 B_1
A_2 B_2
:
A_H B_H


Output

Print H lines. The i-th line should contain the answer for the case k=i.

Example

Input

4 4
2 4
1 1
2 3
2 4


Output

1
3
6
-1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> P;

// input
int H, W;
vector<int> A, B;

set<P> s;
multiset<int> w;


void input() {
    cin >> H >> W;
    A = B = vector<int>(H);
    rep(i, H) {
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
    }
}


int main() {
    input();
    rep(i, W) {
        s.insert(P(i, i));
        w.insert(0);
    }
    rep(i, H) {
        auto x = s.lower_bound(P(A[i], 0));
        auto y = s.lower_bound(P(B[i] + 1, 0));
        if (x != s.end() && y != s.begin() && x != y) {
            y--;
            while (x != y) {
                int v = x->first - x->second;
                w.erase(w.find(v));
                s.erase(x++);
            }
            if (B[i] < W - 1) {
                s.insert(P(B[i] + 1, x->second));
                w.insert(B[i] + 1 - x->second);
            }
            int v = x->first - x->second;
            w.erase(w.find(v));
            s.erase(x);
        }
        ll ans;
        if (w.empty()) ans = -1;
        else ans = ll(i) + 1 + (*w.begin());
        cout << ans << endl;
    }
}