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;

int main() {
	int h, w; cin >> h >> w;
	int a[h], b[h];
	for(int i = 0; i < h; ++i) {
		cin >> a[i] >> b[i];
		--a[i], --b[i];
	}
	map<int, int> mp;
	multiset<int> st;
	for(int x = 0; x < w; ++x) {
		mp[x] = 0;
		st.insert(0);
	}
	for(int y = 0; y < h; ++y) {
		while(true) {
			auto itr = mp.lower_bound(a[y]);
			if(itr == mp.end()) break;
			auto [x, c] = *itr;
			if(x > b[y]) break;
			mp.erase(itr);
			st.erase(st.find(c));
			if(b[y] + 1 >= w) continue;
			if(not mp.count(b[y] + 1)) {
				mp[b[y] + 1] = c + (b[y] + 1) - x;
				st.insert(c + (b[y] + 1) - x);
			} else {
				if(c + (b[y] + 1) - x < mp[b[y] + 1]) {
					st.erase(st.find(mp[b[y] + 1]));
					mp[b[y] + 1] = c + (b[y] + 1) - x;
					st.insert(c + (b[y] + 1) - x);
				}
			}
		}
		if(st.empty()) {
			cout << -1 << '\n';
		} else {
			cout << *st.begin() + y + 1 << '\n';
		}
	}
	return 0;
}