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 JAVA):

Solution:
import java.util.*;

public class Main {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        int[] a = new int[h];
        int[] b = new int[h];

        for(int i=0; i<h; i++) {
            a[i] = Integer.parseInt(sc.next())-1;
            b[i] = Integer.parseInt(sc.next())-1;
        }

        TreeMap<Integer, Integer> map = new TreeMap<>();
        Counter counter = new Counter();

        for(int i=0; i<w; i++) {
            map.put(i, 0);
        }
        counter.map.put(0, w);
        counter.map.put(w, 1);
        for(int i=0; i<h; i++) {
            Integer key;
            int rmin = w;
            while((key = map.ceilingKey(a[i])) != null && key <= b[i]) {
                rmin = Math.min(rmin, map.get(key) + b[i]+1-key);
                counter.remove(map.get(key));
                map.remove(key);
            }
            if(b[i]+1<w) {
                if (map.containsKey(b[i] + 1)) {
                    counter.remove(map.get(b[i] + 1));
                    int num = Math.min(rmin, map.getOrDefault(b[i] + 1, w));
                    map.put(b[i] + 1, num);
                    counter.add(num);
                } else {
                    map.put(b[i] + 1, rmin);
                    counter.add(rmin);
                }
            }
            int min = counter.head();
            if(min == w) {
                System.out.println(-1);
            } else {
                System.out.println(min + i + 1);
            }
        }

    }

    static class Counter {
        TreeMap<Integer, Integer> map = new TreeMap<>();

        void add(Integer key) {
            map.put(key, map.getOrDefault(key, 0)+1);
        }
        void remove(Integer key) {
            int num = map.get(key);
            if(num == 1) {
                map.remove(key);
            } else {
                map.put(key, num-1);
            }
        }

        Integer head() {
            return map.firstKey();
        }
    }



}