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.Scanner;
import java.util.SortedMap;
import java.util.TreeMap;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        final int H = sc.nextInt();
        final int W = sc.nextInt();
        
        final int[][] range = new int[H][2];
        
        for (int i = 0; i < H; i++) {
            range[i][0] = sc.nextInt() - 1;
            range[i][1] = sc.nextInt();
        }
        
        SortedMap<Integer, Integer> currToOrigin = new TreeMap<>();
        for (int j = 0; j < W; j++) {
            currToOrigin.put(j, j);
        }
        
        int[] gaps = new int[W];
        gaps[0] = W;
        int minGapIdx = 0;
        int maxGapIdx = 0;
        
        StringBuilder result = new StringBuilder();
        final String BR = System.lineSeparator();
        
        int i = 0;
        for (; i < H && !currToOrigin.isEmpty(); i++) {
            int left = range[i][0];
            int right = range[i][1];
            SortedMap<Integer, Integer> subMap = currToOrigin.subMap(left, right);
            
            if (!subMap.isEmpty()) {
                int biggestOrigin = subMap.get(subMap.lastKey());
                
                subMap.forEach((curr, orig) -> gaps[curr - orig]--);
                subMap.clear();
                
                if (right < W && !currToOrigin.containsKey(right)) {
                    currToOrigin.put(right, biggestOrigin);
                    gaps[right - biggestOrigin]++;
                    if (maxGapIdx < right - biggestOrigin) {
                        maxGapIdx = right - biggestOrigin;
                    }
                }
                
                while (minGapIdx <= maxGapIdx && gaps[minGapIdx] == 0) {
                    minGapIdx++;
                }
            }
            result.append(minGapIdx <= maxGapIdx ? minGapIdx + i + 1 : -1).append(BR);
        }
        for (; i < H; i++) {
            result.append(-1).append(BR);
        }
        System.out.println(result);
    }
}