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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.SortedMap;
import java.util.StringTokenizer;
import java.util.TreeMap;

public final class Main {

    public static void main(String[] args) {
        final FastScanner fs = new FastScanner();
        final int h = fs.nextInt();
        final int w = fs.nextInt();
        final int[] a = new int[h];
        final int[] b = new int[h];
        for (int i = 0; i < h; i++) {
            a[i] = fs.nextInt() - 1;
            b[i] = fs.nextInt();
        }
        final SortedMap<Integer, Integer> currToOrigin = new TreeMap<>();
        for (int i = 0; i < w; i++) {
            currToOrigin.put(i, i);
        }
        final int[] gaps = new int[w];
        final int[] results = new int[h];
        gaps[0] = w;
        Arrays.fill(results, -1);
        int minGapIndex = 0, maxGapIndex = 0;
        for (int i = 0; (i < h) && !currToOrigin.isEmpty(); i++) {
            final SortedMap<Integer, Integer> subMap = currToOrigin.subMap(a[i], b[i]);
            if (!subMap.isEmpty()) {
                final int maxOrigin = subMap.get(subMap.lastKey());
                subMap.forEach((key, value) -> gaps[key - value]--);
                subMap.clear();
                if ((b[i] < w) && !currToOrigin.containsKey(b[i])) {
                    currToOrigin.put(b[i], maxOrigin);
                    gaps[b[i] - maxOrigin]++;
                    maxGapIndex = Math.max(maxGapIndex, b[i] - maxOrigin);
                }
                while ((minGapIndex <= maxGapIndex) && (0 == gaps[minGapIndex])) {
                    minGapIndex++;
                }
            }
            results[i] = (minGapIndex <= maxGapIndex) ? minGapIndex + i + 1 : -1;
        }
        Arrays.stream(results).forEach(System.out::println);
    }

    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    //noinspection CallToPrintStackTrace
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] readArray(int n) {
            final int[] a = new int[n];
            for (int i = 0; i < n; i++) { a[i] = nextInt(); }
            return a;
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}