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:
/*  -*- coding: utf-8 -*-
 *
 * f.cc: F - I hate Shortest Path Problem
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_W = 200000;

/* typedef */

typedef pair<int,int> pii;
typedef set<pii> spii;
typedef multiset<int> msi;

/* global variables */

spii rset;
msi mls;

/* subroutines */

/* main */

int main() {
  int h, w;
  scanf("%d%d", &h, &w);

  for (int i = 0; i < w; i++) {
    rset.insert(pii(i, i));
    mls.insert(0);
  }

  for (int k = 1; k <= h; k++) {
    int ak, bk;
    scanf("%d%d", &ak, &bk);
    ak--;

    spii::iterator sit = rset.lower_bound(pii(ak, -1));
    int maxx = -1;
    while (sit != rset.end() && sit->first < bk) {
      int y = sit->first, x = sit->second;
      if (maxx < x) maxx = x;
      sit = rset.erase(sit);
      msi::iterator mit = mls.lower_bound(y - x);
      mls.erase(mit);
    }

    if (bk < w && maxx >= 0) {
      rset.insert(pii(bk, maxx));
      mls.insert(bk - maxx);
    }

    if (mls.empty()) puts("-1");
    else printf("%d\n", *mls.begin() + k);
  }

  return 0;
}