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;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

const int INF = 987654321;

int h, w;
int a[200001];
int b[200001];

set <pii> st;
multiset <int> ms;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> h >> w;
	for (int i = 0; i < h; i++)
		cin >> a[i] >> b[i];

	for (int i = 1; i <= w; i++)
	{
		st.insert({ i,i });
		ms.insert(0);
	}

	for (int i = 0; i < h; i++)
	{
		while (true)
		{
			auto it = st.lower_bound({ a[i],0 });
			if (it == st.end()) break;
			if (it->first > b[i]) break;

			int s = it->second, e = it->first;

			st.erase(it);
			ms.erase(ms.find(e - s));

			if (b[i] != w)
			{
				st.insert({ b[i] + 1,s });
				ms.insert(b[i] + 1 - s);

				while (true)
				{	
					auto it = st.lower_bound({ b[i] + 1,0 });
					auto jt = next(it);
					if (jt == st.end() || jt->first != b[i] + 1) break;

					int s = it->second, e = it->first;

					st.erase(it);
					ms.erase(ms.find(e - s));
				}
			}
		}

		if (ms.empty()) cout << "-1\n";
		else cout << (*ms.begin()) + i + 1 << '\n';
	}
}