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>

#define int long long

using namespace std;

#ifdef LOCAL 
#include "/media/brayand/BrayanD/debugger.h"
#else
#define db(...) false
#define dbg(...) false
#endif

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int H, W;
    cin >> H >> W;

    set<pair<int,int>> st;
    set<pair<int,int>> ist;

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

    for(int i = 0 ; i < H ; i++)
    {
    	db(st);
    	db(ist);
    	if(i)
    	{
    		if(ist.size())cout << (*ist.begin()).first + i << '\n';
    		else cout << -1 << '\n';
    	}

    	int a, b;
    	cin >> a >> b;

    	b++;

    	vector<pair<int,int>> vect;

    	while(1)
    	{
    		auto it = st.upper_bound({a,-1});
    		if(it == st.end())break;
    		if((*it).first > b)break;
    		vect.push_back(*it);
    		st.erase(it);
    	}

    	db(vect);

    	if(vect.size() == 0)continue;

    	for(auto x : vect)
    	{
    		ist.erase({x.second,x.first});
    	}


    	int value = vect.back().second + abs(vect.back().first - (b));
    	int pos = (b);

    	if(pos != W+1)
    	{
    		st.insert({pos,value});
    		ist.insert({value,pos});
    	}
    }
    	db(st);
    	db(ist);

    if(ist.size())cout << (*ist.begin()).first + H << '\n';
    else cout << -1 << '\n';

    return 0;
}