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.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

public class Main {
	
	class Node implements Comparable<Node>{
		int left, right;
		
		public Node(int left, int right) {
			this.left  = left;
			this.right = right;
		}
		
		@Override
		public int compareTo(Node o) {
			return right - o.right;
		}
	}
	
	public Main() {
		PrintWriter PW = new PrintWriter(System.out);
		FastScanner scanner = new FastScanner();
		int H = scanner.nextInt();
		int W = scanner.nextInt();
		
		TreeSet<Node>             nodeSet  = new TreeSet<>();
		TreeMap<Integer, Integer> costMap  = new TreeMap<>();
		
		for (int i = 1; i <= W; i++) {
			nodeSet.add(new Node(i, i));
		}
		costMap.put(0, W);
		
		Node A = new Node(0,0);
		Node B = new Node(0,0);
		for (int h = 1; h <= H; h++) {
			A.right = scanner.nextInt();
			B.right = scanner.nextInt() + 1;
			
			SortedSet<Node> sub = nodeSet.subSet(A, B);
			
			if (!sub.isEmpty()) {
				
				for (Node node : sub){
					int cost = node.right - node.left;
					int num  = costMap.get(cost);
					if (num != 1) {
						costMap.put(cost, num - 1);
					} else {
						costMap.remove(cost);
					}
				}
				
				Node node = sub.last();
				sub.clear();
				
				if (B.right != W+1) {
					node.right = B.right;
					if ( nodeSet.add(node) ) {
						int cost = node.right - node.left;
						costMap.put(cost, costMap.getOrDefault(cost,0)+1);
					}
				}
				
			}
			
			if (costMap.isEmpty()) {
				PW.println(-1);
			} else {
				PW.println(costMap.firstKey() + h);
			}
		}
		
		PW.close();
	}
	
	public static void main(String[] args) {
		new Main();
	}
}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;
	
	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}
	
	private int readByte() {
		if (hasNextByte()) return buffer[ptr++];
		else return -1;
	}
	
	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}
	
	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
		return hasNextByte();
	}
	
	public String next() {
		if (!hasNext()) throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	public long nextLong() {
		if (!hasNext()) throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
	
	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) nl;
	}
	
	public double nextDouble() {
		return Double.parseDouble(next());
	}
}