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<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#define maxn 200005
#define mid ((nl+nr)>>1)
using namespace std;
typedef long long ll;
const ll mod=998244353;
int n,m;
int cnt[maxn];
map<int,int>pre;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		pre[i]=i;
		cnt[i-i]++;
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		int pos=-1;
		for(map<int,int> ::iterator it=pre.lower_bound(l);it!=pre.end() && it->first<=r+1;it=pre.erase(it))
		{
			if(it==pre.end()) break;
			pos=max(pos,it->second);
			cnt[-it->second+it->first]--;
		}
		if(pos!=-1 && r+1<=m)
		{
			pre[r+1]=pos;
			cnt[r+1-pos]++;
		}
		while(!cnt[ans] && ans<m) ans++;
		if(ans>=m)
			printf("-1\n");
		else
			printf("%d\n",i+ans);
	}
}