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 <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#define LL long long
#define pb push_back
#define mp make_pair
#define INF 0x3f3f3f3f
#define Inf 1000000000000000000LL
#define F first
#define S second
using namespace std;
typedef pair<int,int>pii;
int main(){
	int n,m;
	cin>>n>>m;
	map<int,int>mm;
	multiset<int>ss;
	for(int i=0;i<m;i++)mm[i]=i;
	for(int i=0;i<m;i++)ss.insert(0);
	for(int i=1,add=1;i<=n;i++){
		int a,b,c,d;
		cin>>a>>b;
		c=-1;
		for(auto j=mm.lower_bound(--a);j!=mm.end()&&j->F<=b;mm.erase(j++)){
			d=j->F;
			c=max(c,mm[d]);
			ss.erase(ss.find(d-mm[d]));
		}
		if(c+1&&b<m)mm[b]=c,ss.insert(b-c);
		if(ss.size())cout<<*ss.begin()+add<<endl,add++;
		else puts("-1");
	}
}