AtCoder Beginner Contest 177 - I hate Shortest Path 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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import math
import itertools
import queue
import bisect
from collections import deque, defaultdict
import heapq as hpq
from sys import stdin, setrecursionlimit
ipt = stdin.readline
setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7
dir = [(-1, 0), (0, -1), (1, 0), (0, 1)]
alp = 'abcdefghijklmnopqrstuvwxyz'

class SegTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

class Binary_Indexed_Tree:

	def __init__(self, n):
		self.N = n
		self.BIT = [0] * (n + 1)
		self.l2 = 2 ** (len(format(n, 'b')) - 1)

	def get_sum(self, idx):
		res_sum = 0
		while idx > 0:
			res_sum += self.BIT[idx]
			idx -= idx & -idx
		return res_sum

	def query(self, l, r):
		return self.get_sum(r) - self.get_sum(l - 1)

	def add(self, idx, x):
		while idx <= self.N:
			self.BIT[idx] += x
			idx += idx & -idx
		return

	def lower_bound(self, w):
		if w <= 0:
			return 0
		x = 0
		k = self.l2
		while k > 0:
			if x + k <= self.N and self.BIT[x + k] < w:
				w -= self.BIT[x + k]
				x += k
			k //= 2
		return x + 1

	def upper_bound(self, w):
		x = 0
		k = self.l2
		while k > 0:
			if x + k <= self.N and self.BIT[x + k] <= w:
				w -= self.BIT[x + k]
				x += k
			k //= 2
		return x + 1

class std_map:

	def __init__(self, n, init):
		self.size = n
		self.keys = set()
		self.bit = Binary_Indexed_Tree(n + 1)
		self.dic = [init] * (n + 1)

	def __contains__(self, key):
		return key in self.keys

	def __getitem__(self, key):
		return self.dic[key]

	def __setitem__(self, key, value):
		if not key in self.keys:
			self.bit.add(key, 1)
			self.keys.add(key)
		self.dic[key] = value

	def remove(self, key):
		self.keys.remove(key)
		self.bit.add(key, -1)

	def lower_bound(self, k):
		return self.bit.lower_bound(self.bit.get_sum(k))

	def upper_bound(self, k):
		return self.bit.upper_bound(self.bit.get_sum(k))

	def kth_key(self, k):
		return self.bit.lower_bound(k)

	def kth_value(self, k):
		return self.dic[self.kth_key(k)]

	def prev_k(self, k):
		idx = self.bit.get_sum(k)
		if idx == 0:
			return -1
		return self.bit.lower_bound(idx - 1)

	def prev_k(self, k):
		idx = self.bit.get_sum(k)
		if idx == self.size:
			return -1
		return self.bit.lower_bound(idx + 1)

def main():
	(h, w) = map(int, ipt().split())
	st = SegTree([10 ** 18] + [0] * w + [10 ** 18], min, 10 ** 18)
	s = std_map(w + 2, 0)
	for i in range(1, w + 2):
		s.bit.add(i, 1)
	s.keys = set(range(w + 2))
	for i in range(h):
		(a, b) = map(int, ipt().split())
		pl = s.bit.get_sum(a - 1) + 1
		pa = s.kth_key(pl)
		mv = 10 ** 18
		while pa <= b:
			st.update(pa, 10 ** 18)
			mv = min(mv, s[pa] - pa)
			s.remove(pa)
			pa = s.kth_key(pl)
		mv += b + 1
		if b != w:
			if not b + 1 in s or s[b + 1] > mv:
				st.update(b + 1, mv)
				s[b + 1] = mv
		mv = st.tree[1]
		if mv == 10 ** 18:
			print(-1)
		else:
			print(mv + i + 1)
	return None
main()


class BalancingTree:

	def __init__(self, n):
		self.N = n
		self.root = self.node(1 << n, 1 << n)

	def debug(self):

		def debug_info(nd_):
			return (nd_.value - 1, nd_.pivot, nd_.left.value - 1 if nd_.left else -1, nd_.right.value - 1 if nd_.right else -1, nd_.cnt)

		def debug_node(nd):
			re = []
			if nd.left:
				re += debug_node(nd.left)
			if nd.value:
				re.append(debug_info(nd))
			if nd.right:
				re += debug_node(nd.right)
			return re
		print('Debug - root =', self.root.value - 1, debug_node(self.root)[:50])

	def append(self, v):
		v += 1
		nd = self.root
		while True:
			if v == nd.value:
				return 0
			else:
				(mi, ma) = (min(v, nd.value), max(v, nd.value))
				if mi < nd.pivot:
					nd.value = ma
					if nd.left:
						nd = nd.left
						v = mi
					else:
						p = nd.pivot
						nd.left = self.node(mi, p - (p & -p) // 2)
						break
				else:
					nd.value = mi
					if nd.right:
						nd = nd.right
						v = ma
					else:
						p = nd.pivot
						nd.right = self.node(ma, p + (p & -p) // 2)
						break

	def leftmost(self, nd):
		if nd.left:
			return self.leftmost(nd.left)
		return nd

	def rightmost(self, nd):
		if nd.right:
			return self.rightmost(nd.right)
		return nd

	def find_l(self, v):
		v += 1
		nd = self.root
		prev = 0
		if nd.value < v:
			prev = nd.value
		while True:
			if v <= nd.value:
				if nd.left:
					nd = nd.left
				else:
					return prev - 1
			else:
				prev = nd.value
				if nd.right:
					nd = nd.right
				else:
					return prev - 1

	def find_r(self, v):
		v += 1
		nd = self.root
		prev = 0
		if nd.value > v:
			prev = nd.value
		while True:
			if v < nd.value:
				prev = nd.value
				if nd.left:
					nd = nd.left
				else:
					return prev - 1
			elif nd.right:
				nd = nd.right
			else:
				return prev - 1

	@property
	def max(self):
		return self.find_l((1 << self.N) - 1)

	@property
	def min(self):
		return self.find_r(-1)

	@property
	def sum(self):
		return self.root.sum - self.root.value + 1

	@property
	def size(self):
		return self.root.cnt - 1

	def delete(self, v, nd=None, prev=None):
		v += 1
		if not nd:
			nd = self.root
		if not prev:
			prev = nd
		while v != nd.value:
			prev = nd
			if v <= nd.value:
				if nd.left:
					nd = nd.left
				else:
					return
			elif nd.right:
				nd = nd.right
			else:
				return
		if not nd.left and (not nd.right):
			if not prev.left:
				prev.right = None
			elif not prev.right:
				prev.left = None
			elif nd.pivot == prev.left.pivot:
				prev.left = None
			else:
				prev.right = None
		elif nd.right:
			nd.value = self.leftmost(nd.right).value
			self.delete(nd.value - 1, nd.right, nd)
		else:
			nd.value = self.rightmost(nd.left).value
			self.delete(nd.value - 1, nd.left, nd)

	def __contains__(self, v: int) -> bool:
		return self.find_r(v - 1) == v

	class node:

		def __init__(self, v, p):
			self.value = v
			self.pivot = p
			self.left = None
			self.right = None
import sys, heapq
input = sys.stdin.readline
(H, W) = map(int, input().split())
ban = [tuple(map(int, input().split())) for i in range(H)]
exist = [True for i in range(W + 1)]
que = [(0, i) for i in range(1, W + 1)]
heapq.heapify(que)
BT = BalancingTree(40)
for i in range(1, W + 1):
	tmp = (i << 20) + i
	BT.append(tmp)
erase = set()
for i in range(H):
	(a, b) = ban[i]
	erasemax = (-1, -1)
	while True:
		val = BT.find_r(a << 20)
		pos = val >> 20
		fr = val % (1 << 20)
		if pos <= b:
			erasemax = max(erasemax, (fr, pos - fr))
			erase.add((pos - fr, fr))
			exist[fr] = False
			BT.delete(val)
		else:
			if pos > b + 1 and erasemax[0] != -1 and (b + 1 <= W):
				BT.append((b + 1 << 20) + erasemax[0])
				deg = (erasemax[1], erasemax[0])
				erase.add(deg)
				heapq.heappush(que, (b + 1 - erasemax[0], erasemax[0]))
				exist[erasemax[0]] = True
			break
	while que and (not exist[que[0][1]] or que[0] in erase):
		heapq.heappop(que)
	if que:
		res = i + 1 + que[0][0]
		print(res)
	else:
		print(-1)


import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda : input().strip()
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
mat = lambda x, y, v: [[v] * y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

class BIT:

	def __init__(self, n):
		self.n = n
		self.nums = [0] * (n + 1)

	def add(self, i, x):
		(n, nums) = (self.n, self.nums)
		i += 1
		while i <= n:
			nums[i] += x
			i += i & -i

	def sum(self, i):
		nums = self.nums
		s = 0
		i += 1
		while i:
			s += nums[i]
			i -= i & -i
		return s

	def search(self, x):
		(n, nums) = (self.n, self.nums)
		(s, p) = (0, 0)
		for i in range(n.bit_length(), -1, -1):
			np = p + (1 << i)
			if np <= n and s + nums[np] < x:
				s += nums[np]
				p = np
		return p

class MultiSet:

	def __init__(self, n):
		self.bit = BIT(n)

	def insert(self, key):
		self.bit.add(key, 1)

	def erase(self, key):
		self.bit.add(key, -1)

	def top(self, i=0):
		return self.bit.search(i + 1)

	def size(self):
		return self.bit.sum(self.bit.n - 1)

	def count(self, key):
		return self.bit.sum(key) - self.bit.sum(key - 1)

	def lower_bound(self, key):
		return self.bit.search(self.bit.sum(key - 1) + 1)

	def upper_bound(self, key):
		return self.bit.search(self.bit.sum(key) + 1)

	def debug(self):
		vals = []
		for i in range(self.bit.n):
			key = self.top(i)
			if key == self.bit.n:
				break
			vals.append(key)
		print(vals)

class Map(MultiSet):

	def __init__(self, n):
		super().__init__(n)
		self.data = {}

	def __getitem__(self, key):
		return self.data[key]

	def __setitem__(self, key, val):
		self.insert(key, val)

	def insert(self, key, val=None):
		if key not in self.data:
			super().insert(key)
		self.data[key] = val

	def erase(self, key):
		if key in self.data:
			super().erase(key)
			del self.data[key]

	def debug(self):
		vals = []
		for i in range(self.bit.n):
			key = self.top(i)
			if key == self.bit.n:
				break
			vals.append((key, self[key]))
		print(vals)
(H, W) = rl()
walls = []
for i in range(H):
	(a, b) = rl()
	(a, b) = (a - 1, b - 1)
	walls.append((a, b))
mp = Map(W)
for i in range(W):
	mp[i] = i
ms = MultiSet(W)
for i in range(W):
	ms.insert(0)
for (idx, (a, b)) in enumerate(walls):
	i = mp.lower_bound(a)
	r = -1
	while i < W and i <= b + 1:
		r = max(r, mp[i])
		ms.erase(i - mp[i])
		mp.erase(i)
		i = mp.lower_bound(i)
	if r != -1 and b + 1 < W:
		ms.insert(b + 1 - r)
		mp[b + 1] = r
	ans = -1
	if ms.size() > 0:
		ans = ms.top() + idx + 1
	print(ans)


from heapq import *

class MultisetBIT:

	def __init__(self, maxvalue):
		self.n = maxvalue + 1
		self.k = 1 << (self.n + 1).bit_length() - 1
		self.data = [0] * (self.n + 1)

	def add(self, value):
		value += 1
		while value <= self.n:
			self.data[value] += 1
			value += value & -value

	def pop(self, value):
		value += 1
		while value <= self.n:
			self.data[value] -= 1
			value += value & -value

	def count_le(self, value):
		value += 1
		ret = 0
		while value > 0:
			ret += self.data[value]
			value -= value & -value
		return ret

	def count(self, first, last):
		last += 1
		ret = 0
		while first < last:
			ret += self.data[last]
			last -= last & -last
		while last < first:
			ret -= self.data[first]
			first -= first & -first
		return ret

	def bisect(self, count):
		ret = 0
		k = self.k
		while k > 0:
			if ret + k <= self.n and self.data[ret + k] < count:
				count -= self.data[ret + k]
				ret += k
			k >>= 1
		return ret

	def lower_bound(self, value):
		return self.bisect(self.count_le(value - 1) + 1)

	def upper_bound(self, value):
		return self.bisect(self.count_le(value) + 1)
(H, W) = map(int, input().split())
destination = MultisetBIT(W)
for i in range(W):
	destination.add(i)
destination_to_cost = {i: 0 for i in range(W)}
min_heapq = [0] * W
to_delete = []
for k in range(H):
	(A, B) = map(int, input().split())
	A -= 1
	B -= 1
	start_point = destination.lower_bound(A)
	point = start_point
	change_dest_flg = False
	while point < W and point < B + 1:
		change_dest_flg = True
		cost = destination_to_cost.pop(point)
		heappush(to_delete, cost)
		if B + 1 != W:
			if B + 1 in destination_to_cost:
				if destination_to_cost[B + 1] > B + 1 - point + cost:
					heappush(to_delete, destination_to_cost[B + 1])
					destination_to_cost[B + 1] = B + 1 - point + cost
					heappush(min_heapq, B + 1 - point + cost)
			else:
				destination_to_cost[B + 1] = B + 1 - point + cost
				heappush(min_heapq, B + 1 - point + cost)
				destination.add(B + 1)
		destination.pop(point)
		point = destination.upper_bound(point)
	while to_delete and min_heapq[0] == to_delete[0]:
		heappop(min_heapq)
		heappop(to_delete)
	if min_heapq:
		print(k + min_heapq[0] + 1)
	else:
		for _ in range(H - k):
			print(-1)
		exit()


from heapq import *
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

class BitSum:

	def __init__(self, n):
		self.n = n + 1
		self.table = [0] * self.n

	def add(self, i, x):
		i += 1
		while i < self.n:
			self.table[i] += x
			i += i & -i

	def sum(self, i):
		i += 1
		res = 0
		while i > 0:
			res += self.table[i]
			i -= i & -i
		return res

	def rank(self, x):
		idx = 0
		for lv in range((self.n - 1).bit_length() - 1, -1, -1):
			mid = idx + (1 << lv)
			if mid >= self.n:
				continue
			if self.table[mid] < x:
				x -= self.table[mid]
				idx += 1 << lv
		return idx

def solve():
	bit = BitSum(w + 1)
	for j in range(w):
		bit.add(j + 1, 1)
	cost = [0] * (w + 1)
	hp = [0] * w
	heapify(hp)
	rem = []
	for i in range(h):
		(l, r) = MI()
		r += 1
		if r <= w:
			cnt = bit.sum(r)
			if cnt:
				j = bit.rank(cnt)
				if l <= j < r:
					bit.add(r, 1)
					cost[r] = cost[j] + r - j
					heappush(hp, cost[r])
		cnt = bit.sum(l - 1)
		while 1:
			j = bit.rank(cnt + 1)
			if j >= r:
				break
			heappush(rem, cost[j])
			bit.add(j, -1)
		while hp and rem and (hp[0] == rem[0]):
			heappop(hp)
			heappop(rem)
		if hp:
			print(hp[0] + i + 1)
		else:
			print(-1)
(h, w) = MI()
solve()


class segment_tree:

	def __init__(self, N, operator_M, e_M):
		self.op_M = operator_M
		self.e_M = e_M
		self.N0 = 1 << (N - 1).bit_length()
		self.dat = [self.e_M] * (2 * self.N0)

	def build(self, initial):
		self.dat[self.N0:self.N0 + len(initial)] = initial[:]
		for k in range(self.N0 - 1, 0, -1):
			self.dat[k] = self.op_M(self.dat[2 * k], self.dat[2 * k + 1])

	def update(self, k, x):
		k += self.N0
		self.dat[k] = x
		k //= 2
		while k:
			self.dat[k] = self.op_M(self.dat[2 * k], self.dat[2 * k + 1])
			k //= 2

	def query(self, L, R):
		L += self.N0
		R += self.N0 + 1
		sl = sr = self.e_M
		while L < R:
			if R & 1:
				R -= 1
				sr = self.op_M(self.dat[R], sr)
			if L & 1:
				sl = self.op_M(sl, self.dat[L])
				L += 1
			L >>= 1
			R >>= 1
		return self.op_M(sl, sr)

	def get(self, k):
		return self.dat[k + self.N0]

class BIT:

	def __init__(self, n):
		self.size = n
		self.tree = [i & -i for i in range(n + 1)]
		self.depth = n.bit_length()
		self.n0 = 1 << self.depth

	def get_sum(self, i):
		s = 0
		i += 1
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def query(self, l, r):
		return self.get_sum(r) - self.get_sum(l - 1)

	def add(self, i, x):
		i += 1
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

	def bisect_left(self, w):
		if w <= 0:
			return 0
		(x, k) = (0, self.n0)
		for _ in range(self.depth):
			k >>= 1
			if x + k <= self.size and self.tree[x + k] < w:
				w -= self.tree[x + k]
				x += k
		return x

class stdmap:

	def __init__(self, n):
		self.size = n + 1
		self.keys = set()
		self.B = BIT(n + 1)
		self.dic = [0] * (n + 1)

	def __contains__(self, k):
		return k in self.keys

	def insert(self, a, b):
		if a not in self.keys:
			self.B.add(a, 1)
			self.keys.add(a)
		self.dic[a] = b

	def remove(self, a):
		self.keys.remove(a)
		self.B.add(a, -1)

	def lower_bound(self, k):
		return self.B.bisect_left(self.B.get_sum(k))

	def kth_key(self, k):
		return self.B.bisect_left(k)

	def kth_value(self, k):
		return self.dic[self.B.bisect_left(k)]

	def prev_key(self, k):
		idx = self.B.get_sum(k)
		assert idx != 0
		return self.B.bisect_left(idx - 1)

	def next_key(self, k):
		idx = self.B.get_sum(k)
		assert idx != self.size
		return self.B.bisect_left(idx + 1)

	def __getitem__(self, item):
		return self.dic[item]
import sys
readline = sys.stdin.readline
read = sys.stdin.read
(h, w) = map(int, readline().split())
b = stdmap(w + 2)
b.dic = [0] * (w + 3)
b.keys = set(range(w + 2))
INF = 1 << 31
seg = segment_tree(w + 2, min, INF)
seg.build([INF] + [0] * w + [INF])
for i in range(1, h + 1):
	(p, q) = map(int, readline().split())
	idx = b.B.get_sum(p - 1) + 1
	x = b.kth_key(idx)
	val = INF
	while x <= q:
		val = min(val, b.dic[x] - x)
		seg.update(x, INF)
		b.remove(x)
		x = b.kth_key(idx)
	if q < w:
		if q + 1 not in b.keys or b.dic[q + 1] > val + q + 1:
			b.insert(q + 1, val + q + 1)
			seg.update(q + 1, val + q + 1)
	v = seg.dat[1]
	if v >= INF:
		print(-1)
	else:
		print(v + i)


import sys
readline = sys.stdin.readline

class Lazysegtree:

	def __init__(self, A, fx, ex, fm, em, fa, initialize=True):
		self.N = len(A)
		self.N0 = 2 ** (self.N - 1).bit_length()
		self.dep = (self.N - 1).bit_length()
		self.fx = fx
		self.ex = ex
		self.em = em
		self.lazy = [em] * (2 * self.N0)
		if initialize:
			self.data = [self.ex] * self.N0 + A + [self.ex] * (self.N0 - self.N)
			for i in range(self.N0 - 1, -1, -1):
				self.data[i] = self.fx(self.data[2 * i], self.data[2 * i + 1])
		else:
			self.data = [self.ex] * (2 * self.N0)

	def fa(self, ope, idx):
		if ope[0]:
			k = idx.bit_length()
			return (idx - (1 << k - 1)) * (1 << self.dep + 1 - k) + ope[1]
		return self.data[idx]

	def fm(self, x, y):
		if x[0] == 1:
			return x
		else:
			return y

	def __repr__(self):
		s = 'data'
		l = 'lazy'
		cnt = 1
		for i in range(self.N0.bit_length()):
			s = '\n'.join((s, ' '.join(map(str, self.data[cnt:cnt + (1 << i)]))))
			l = '\n'.join((l, ' '.join(map(str, self.lazy[cnt:cnt + (1 << i)]))))
			cnt += 1 << i
		return '\n'.join((s, l))

	def _ascend(self, k):
		k = k >> 1
		c = k.bit_length()
		for j in range(c):
			idx = k >> j
			self.data[idx] = self.fx(self.data[2 * idx], self.data[2 * idx + 1])

	def _descend(self, k):
		k = k >> 1
		idx = 1
		c = k.bit_length()
		for j in range(1, c + 1):
			idx = k >> c - j
			if self.lazy[idx] == self.em:
				continue
			self.data[2 * idx] = self.fa(self.lazy[idx], 2 * idx)
			self.data[2 * idx + 1] = self.fa(self.lazy[idx], 2 * idx + 1)
			self.lazy[2 * idx] = self.fm(self.lazy[idx], self.lazy[2 * idx])
			self.lazy[2 * idx + 1] = self.fm(self.lazy[idx], self.lazy[2 * idx + 1])
			self.lazy[idx] = self.em

	def query(self, l, r):
		L = l + self.N0
		R = r + self.N0
		self._descend(L // (L & -L))
		self._descend(R // (R & -R) - 1)
		sl = self.ex
		sr = self.ex
		while L < R:
			if R & 1:
				R -= 1
				sr = self.fx(self.data[R], sr)
			if L & 1:
				sl = self.fx(sl, self.data[L])
				L += 1
			L >>= 1
			R >>= 1
		return self.fx(sl, sr)

	def operate(self, l, r, x):
		L = l + self.N0
		R = r + self.N0
		Li = L // (L & -L)
		Ri = R // (R & -R)
		self._descend(Li)
		self._descend(Ri - 1)
		while L < R:
			if R & 1:
				R -= 1
				self.data[R] = self.fa(x, R)
				self.lazy[R] = self.fm(x, self.lazy[R])
			if L & 1:
				self.data[L] = self.fa(x, L)
				self.lazy[L] = self.fm(x, self.lazy[L])
				L += 1
			L >>= 1
			R >>= 1
		self._ascend(Li)
		self._ascend(Ri - 1)
INF = 10 ** 18 + 3
(H, W) = map(int, readline().split())
T = Lazysegtree([0] * W, min, INF, None, (0, 0), None, initialize=True)
N0 = T.N0
Ans = [None] * H
for qu in range(H):
	(a, b) = map(int, readline().split())
	a -= 1
	if a == 0:
		T.operate(a, b, (1, INF))
	else:
		x = T.query(a - 1, a)
		T.operate(a, b, (1, x - a + 1))
	ans = T.query(0, N0) + qu + 1
	if ans >= INF:
		ans = -1
	Ans[qu] = ans
print('\n'.join(map(str, Ans)))


import sys
input = sys.stdin.readline
from collections import defaultdict

def DD(arg):
	return defaultdict(arg)

def int_log(n, a):
	count = 0
	while n >= a:
		n //= a
		count += 1
	return count
(H, W) = list(map(int, input().split()))
data = [list(map(int, input().split())) for _ in range(H)]

class BIT:

	def __init__(self, logn):
		self.n = 1 << logn
		self.data = [0] * (self.n + 1)
		self.el = [0] * (self.n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		self.el[i] += x
		while i <= self.n:
			self.data[i] += x
			i += i & -i

	def get(self, i, j=None):
		if j is None:
			return self.el[i]
		return self.sum(j) - self.sum(i)

	def bisect(self, x):
		w = i = 0
		k = self.n
		while k:
			if i + k <= self.n and w + self.data[i + k] < x:
				w += self.data[i + k]
				i += k
			k >>= 1
		return i + 1
dic = DD(int)
for i in range(W):
	dic[i + 1] = i + 1
members = DD(int)
for i in range(W):
	members[i + 1] = 1
B = BIT(int_log(W, 2) + 1)
for i in range(W):
	B.add(i + 1, 1)

def calc_prev_valid(x):
	s = B.sum(x - 1)
	if s == 0:
		return 0
	else:
		return B.bisect(s)
count_score = DD(int)
count_score[0] = W
score = 0
for i in range(H):
	(a, b) = data[i]
	now = b
	while now >= a:
		if B.el[now]:
			count_score[now - dic[now]] -= members[now]
			if not B.el[b + 1]:
				dic[b + 1] = dic[now]
				B.add(b + 1, 1)
			if b + 1 < W + 1:
				count_score[b + 1 - dic[b + 1]] += members[now]
			B.add(now, -1)
			members[b + 1] += members[now]
			members[now] = 0
		now = calc_prev_valid(now)
	while True:
		if count_score[score]:
			print(score + i + 1)
			break
		else:
			score += 1
		if score == W:
			for _ in range(H - i):
				print(-1)
			exit()


from heapq import *

class erasable_heapq:
	__slots__ = ['data', 'to_delete']

	def __init__(self, data, allow_data_destruction=False):
		if allow_data_destruction:
			self.data = data
		else:
			self.data = data.copy()
		heapify(self.data)
		self.to_delete = []

	def top(self):
		while self.to_delete and self.to_delete[0] == self.data[0]:
			heappop(self.to_delete)
			heappop(self.data)
		return self.data[0]

	def push(self, elem):
		heappush(self.data, elem)

	def pop(self):
		while self.to_delete and self.to_delete[0] == self.data[0]:
			heappop(self.to_delete)
			heappop(self.data)
		return heappop(self.data)

	def pushpop(self, elem):
		while self.to_delete and self.to_delete[0] == self.data[0]:
			heappop(self.to_delete)
			heappop(self.data)
		return heappushpop(self.data, elem)

	def replace(self, elem):
		while self.to_delete and self.to_delete[0] == self.data[0]:
			heappop(self.to_delete)
			heappop(self.data)
		return heapreplace(self.data, elem)

	def erase(self, elem):
		heappush(self.to_delete, elem)

	def __bool__(self):
		while self.to_delete and self.to_delete[0] == self.data[0]:
			heappop(self.to_delete)
			heappop(self.data)
		return bool(self.data)

	def __len__(self):
		return len(self.data) - len(self.to_delete)

class MultisetBIT:
	__slots__ = ['n', 'k', 'data']

	def __init__(self, maxvalue, counter=None):
		self.n = maxvalue + 1
		self.k = 1 << (self.n + 1).bit_length() - 1
		self.data = [0] * (self.n + 1)
		if counter is not None:
			self.update(counter)

	def update(self, counter):
		if isinstance(counter, list):
			self.data = [0] + counter + [0] * (self.n - len(counter))
		else:
			self.data = [0] * (self.n + 1)
			for (k, v) in counter.items():
				self.data[k + 1] = v
		for i in range(1, self.n + 1):
			if i + (i & -i) <= self.n:
				self.data[i + (i & -i)] += self.data[i]

	def add(self, value):
		value += 1
		while value <= self.n:
			self.data[value] += 1
			value += value & -value

	def pop(self, value):
		value += 1
		while value <= self.n:
			self.data[value] -= 1
			value += value & -value

	def count_le(self, value):
		value += 1
		ret = 0
		while value > 0:
			ret += self.data[value]
			value -= value & -value
		return ret

	def count(self, first, last):
		last += 1
		ret = 0
		while first < last:
			ret += self.data[last]
			last -= last & -last
		while last < first:
			ret -= self.data[first]
			first -= first & -first
		return ret

	def bisect(self, count):
		ret = 0
		k = self.k
		while k > 0:
			if ret + k <= self.n and self.data[ret + k] < count:
				count -= self.data[ret + k]
				ret += k
			k //= 2
		return ret

	def lower_bound(self, value):
		return self.bisect(self.count_le(value - 1) + 1)

	def upper_bound(self, value):
		return self.bisect(self.count_le(value) + 1)
(H, W) = map(int, input().split())
destination = MultisetBIT(W, [1] * W)
destination_to_cost = {i: 0 for i in range(W)}
min_heapq = erasable_heapq([0] * W, True)
for k in range(H):
	(A, B) = map(int, input().split())
	A -= 1
	B -= 1
	start_point = destination.lower_bound(A)
	point = start_point
	change_dest_flg = False
	while point < W and point < B + 1:
		change_dest_flg = True
		cost = destination_to_cost.pop(point)
		min_heapq.erase(cost)
		if B + 1 != W:
			if B + 1 in destination_to_cost:
				if destination_to_cost[B + 1] > B + 1 - point + cost:
					min_heapq.erase(destination_to_cost[B + 1])
					destination_to_cost[B + 1] = B + 1 - point + cost
					min_heapq.push(B + 1 - point + cost)
			else:
				destination_to_cost[B + 1] = B + 1 - point + cost
				min_heapq.push(B + 1 - point + cost)
				destination.add(B + 1)
		destination.pop(point)
		point = destination.upper_bound(point)
	if min_heapq:
		print(k + min_heapq.top() + 1)
	else:
		for _ in range(H - k):
			print(-1)
		exit()


from heapq import *

class MultisetBIT:
	__slots__ = ['n', 'k', 'data']

	def __init__(self, maxvalue, counter=None):
		self.n = maxvalue + 1
		self.k = 1 << (self.n + 1).bit_length() - 1
		self.data = [0] * (self.n + 1)
		if counter is not None:
			self.update(counter)

	def update(self, counter):
		if isinstance(counter, list):
			self.data = [0] + counter + [0] * (self.n - len(counter))
		else:
			self.data = [0] * (self.n + 1)
			for (k, v) in counter.items():
				self.data[k + 1] = v
		for i in range(1, self.n + 1):
			if i + (i & -i) <= self.n:
				self.data[i + (i & -i)] += self.data[i]

	def add(self, value):
		value += 1
		while value <= self.n:
			self.data[value] += 1
			value += value & -value

	def pop(self, value):
		value += 1
		while value <= self.n:
			self.data[value] -= 1
			value += value & -value

	def count_le(self, value):
		value += 1
		ret = 0
		while value > 0:
			ret += self.data[value]
			value -= value & -value
		return ret

	def count(self, first, last):
		last += 1
		ret = 0
		while first < last:
			ret += self.data[last]
			last -= last & -last
		while last < first:
			ret -= self.data[first]
			first -= first & -first
		return ret

	def bisect(self, count):
		ret = 0
		k = self.k
		while k > 0:
			if ret + k <= self.n and self.data[ret + k] < count:
				count -= self.data[ret + k]
				ret += k
			k //= 2
		return ret

	def lower_bound(self, value):
		return self.bisect(self.count_le(value - 1) + 1)

	def upper_bound(self, value):
		return self.bisect(self.count_le(value) + 1)
(H, W) = map(int, input().split())
destination = MultisetBIT(W, {i: 1 for i in range(W)})
destination_to_cost = {i: 0 for i in range(W)}
min_heapq = [0] * W
to_delete = []
for k in range(H):
	(A, B) = map(int, input().split())
	A -= 1
	B -= 1
	start_point = destination.lower_bound(A)
	point = start_point
	change_dest_flg = False
	while point < W and point < B + 1:
		change_dest_flg = True
		cost = destination_to_cost.pop(point)
		heappush(to_delete, cost)
		if B + 1 != W:
			if B + 1 in destination_to_cost:
				if destination_to_cost[B + 1] > B + 1 - point + cost:
					heappush(to_delete, destination_to_cost[B + 1])
					destination_to_cost[B + 1] = B + 1 - point + cost
					heappush(min_heapq, B + 1 - point + cost)
			else:
				destination_to_cost[B + 1] = B + 1 - point + cost
				heappush(min_heapq, B + 1 - point + cost)
				destination.add(B + 1)
		destination.pop(point)
		point = destination.upper_bound(point)
	while to_delete and min_heapq[0] == to_delete[0]:
		heappop(min_heapq)
		heappop(to_delete)
	if min_heapq:
		print(k + min_heapq[0] + 1)
	else:
		for _ in range(H - k):
			print(-1)
		exit()


from __future__ import print_function
import sys
import traceback
from bisect import bisect_left, bisect_right, insort
from itertools import chain, repeat, starmap
from math import log
from operator import add, eq, ne, gt, ge, lt, le, iadd
from textwrap import dedent
from collections.abc import Sequence, MutableSequence, ItemsView, KeysView, ValuesView, MutableSet, Set
from functools import wraps, reduce
from _thread import get_ident

def recursive_repr(fillvalue='...'):

	def decorating_function(user_function):
		repr_running = set()

		@wraps(user_function)
		def wrapper(self):
			key = (id(self), get_ident())
			if key in repr_running:
				return fillvalue
			repr_running.add(key)
			try:
				result = user_function(self)
			finally:
				repr_running.discard(key)
			return result
		return wrapper
	return decorating_function

class SortedList(MutableSequence):
	DEFAULT_LOAD_FACTOR = 1000

	def __init__(self, iterable=None, key=None):
		assert key is None
		self._len = 0
		self._load = self.DEFAULT_LOAD_FACTOR
		self._lists = []
		self._maxes = []
		self._index = []
		self._offset = 0
		if iterable is not None:
			self._update(iterable)

	def __new__(cls, iterable=None, key=None):
		if key is None:
			return object.__new__(cls)
		elif cls is SortedList:
			return object.__new__(SortedKeyList)
		else:
			raise TypeError('inherit SortedKeyList for key argument')

	@property
	def key(self):
		return None

	def _reset(self, load):
		values = reduce(iadd, self._lists, [])
		self._clear()
		self._load = load
		self._update(values)

	def clear(self):
		self._len = 0
		del self._lists[:]
		del self._maxes[:]
		del self._index[:]
		self._offset = 0
	_clear = clear

	def add(self, value):
		_lists = self._lists
		_maxes = self._maxes
		if _maxes:
			pos = bisect_right(_maxes, value)
			if pos == len(_maxes):
				pos -= 1
				_lists[pos].append(value)
				_maxes[pos] = value
			else:
				insort(_lists[pos], value)
			self._expand(pos)
		else:
			_lists.append([value])
			_maxes.append(value)
		self._len += 1

	def _expand(self, pos):
		_load = self._load
		_lists = self._lists
		_index = self._index
		if len(_lists[pos]) > _load << 1:
			_maxes = self._maxes
			_lists_pos = _lists[pos]
			half = _lists_pos[_load:]
			del _lists_pos[_load:]
			_maxes[pos] = _lists_pos[-1]
			_lists.insert(pos + 1, half)
			_maxes.insert(pos + 1, half[-1])
			del _index[:]
		elif _index:
			child = self._offset + pos
			while child:
				_index[child] += 1
				child = child - 1 >> 1
			_index[0] += 1

	def update(self, iterable):
		_lists = self._lists
		_maxes = self._maxes
		values = sorted(iterable)
		if _maxes:
			if len(values) * 4 >= self._len:
				values.extend(chain.from_iterable(_lists))
				values.sort()
				self._clear()
			else:
				_add = self.add
				for val in values:
					_add(val)
				return
		_load = self._load
		_lists.extend((values[pos:pos + _load] for pos in range(0, len(values), _load)))
		_maxes.extend((sublist[-1] for sublist in _lists))
		self._len = len(values)
		del self._index[:]
	_update = update

	def __contains__(self, value):
		_maxes = self._maxes
		if not _maxes:
			return False
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return False
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		return _lists[pos][idx] == value

	def discard(self, value):
		_maxes = self._maxes
		if not _maxes:
			return
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)

	def remove(self, value):
		_maxes = self._maxes
		if not _maxes:
			raise ValueError('{0!r} not in list'.format(value))
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			raise ValueError('{0!r} not in list'.format(value))
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)
		else:
			raise ValueError('{0!r} not in list'.format(value))

	def _delete(self, pos, idx):
		_lists = self._lists
		_maxes = self._maxes
		_index = self._index
		_lists_pos = _lists[pos]
		del _lists_pos[idx]
		self._len -= 1
		len_lists_pos = len(_lists_pos)
		if len_lists_pos > self._load >> 1:
			_maxes[pos] = _lists_pos[-1]
			if _index:
				child = self._offset + pos
				while child > 0:
					_index[child] -= 1
					child = child - 1 >> 1
				_index[0] -= 1
		elif len(_lists) > 1:
			if not pos:
				pos += 1
			prev = pos - 1
			_lists[prev].extend(_lists[pos])
			_maxes[prev] = _lists[prev][-1]
			del _lists[pos]
			del _maxes[pos]
			del _index[:]
			self._expand(prev)
		elif len_lists_pos:
			_maxes[pos] = _lists_pos[-1]
		else:
			del _lists[pos]
			del _maxes[pos]
			del _index[:]

	def _loc(self, pos, idx):
		if not pos:
			return idx
		_index = self._index
		if not _index:
			self._build_index()
		total = 0
		pos += self._offset
		while pos:
			if not pos & 1:
				total += _index[pos - 1]
			pos = pos - 1 >> 1
		return total + idx

	def _pos(self, idx):
		if idx < 0:
			last_len = len(self._lists[-1])
			if -idx <= last_len:
				return (len(self._lists) - 1, last_len + idx)
			idx += self._len
			if idx < 0:
				raise IndexError('list index out of range')
		elif idx >= self._len:
			raise IndexError('list index out of range')
		if idx < len(self._lists[0]):
			return (0, idx)
		_index = self._index
		if not _index:
			self._build_index()
		pos = 0
		child = 1
		len_index = len(_index)
		while child < len_index:
			index_child = _index[child]
			if idx < index_child:
				pos = child
			else:
				idx -= index_child
				pos = child + 1
			child = (pos << 1) + 1
		return (pos - self._offset, idx)

	def _build_index(self):
		row0 = list(map(len, self._lists))
		if len(row0) == 1:
			self._index[:] = row0
			self._offset = 0
			return
		head = iter(row0)
		tail = iter(head)
		row1 = list(starmap(add, zip(head, tail)))
		if len(row0) & 1:
			row1.append(row0[-1])
		if len(row1) == 1:
			self._index[:] = row1 + row0
			self._offset = 1
			return
		size = 2 ** (int(log(len(row1) - 1, 2)) + 1)
		row1.extend(repeat(0, size - len(row1)))
		tree = [row0, row1]
		while len(tree[-1]) > 1:
			head = iter(tree[-1])
			tail = iter(head)
			row = list(starmap(add, zip(head, tail)))
			tree.append(row)
		reduce(iadd, reversed(tree), self._index)
		self._offset = size * 2 - 1

	def __delitem__(self, index):
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return self._clear()
				elif self._len <= 8 * (stop - start):
					values = self._getitem(slice(None, start))
					if stop < self._len:
						values += self._getitem(slice(stop, None))
					self._clear()
					return self._update(values)
			indices = range(start, stop, step)
			if step > 0:
				indices = reversed(indices)
			(_pos, _delete) = (self._pos, self._delete)
			for index in indices:
				(pos, idx) = _pos(index)
				_delete(pos, idx)
		else:
			(pos, idx) = self._pos(index)
			self._delete(pos, idx)

	def __getitem__(self, index):
		_lists = self._lists
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return reduce(iadd, self._lists, [])
				(start_pos, start_idx) = self._pos(start)
				start_list = _lists[start_pos]
				stop_idx = start_idx + stop - start
				if len(start_list) >= stop_idx:
					return start_list[start_idx:stop_idx]
				if stop == self._len:
					stop_pos = len(_lists) - 1
					stop_idx = len(_lists[stop_pos])
				else:
					(stop_pos, stop_idx) = self._pos(stop)
				prefix = _lists[start_pos][start_idx:]
				middle = _lists[start_pos + 1:stop_pos]
				result = reduce(iadd, middle, prefix)
				result += _lists[stop_pos][:stop_idx]
				return result
			if step == -1 and start > stop:
				result = self._getitem(slice(stop + 1, start + 1))
				result.reverse()
				return result
			indices = range(start, stop, step)
			return list((self._getitem(index) for index in indices))
		else:
			if self._len:
				if index == 0:
					return _lists[0][0]
				elif index == -1:
					return _lists[-1][-1]
			else:
				raise IndexError('list index out of range')
			if 0 <= index < len(_lists[0]):
				return _lists[0][index]
			len_last = len(_lists[-1])
			if -len_last < index < 0:
				return _lists[-1][len_last + index]
			(pos, idx) = self._pos(index)
			return _lists[pos][idx]
	_getitem = __getitem__

	def __setitem__(self, index, value):
		message = 'use ``del sl[index]`` and ``sl.add(value)`` instead'
		raise NotImplementedError(message)

	def __iter__(self):
		return chain.from_iterable(self._lists)

	def __reversed__(self):
		return chain.from_iterable(map(reversed, reversed(self._lists)))

	def reverse(self):
		raise NotImplementedError('use ``reversed(sl)`` instead')

	def islice(self, start=None, stop=None, reverse=False):
		_len = self._len
		if not _len:
			return iter(())
		(start, stop, _) = slice(start, stop).indices(self._len)
		if start >= stop:
			return iter(())
		_pos = self._pos
		(min_pos, min_idx) = _pos(start)
		if stop == _len:
			max_pos = len(self._lists) - 1
			max_idx = len(self._lists[-1])
		else:
			(max_pos, max_idx) = _pos(stop)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

	def _islice(self, min_pos, min_idx, max_pos, max_idx, reverse):
		_lists = self._lists
		if min_pos > max_pos:
			return iter(())
		if min_pos == max_pos:
			if reverse:
				indices = reversed(range(min_idx, max_idx))
				return map(_lists[min_pos].__getitem__, indices)
			indices = range(min_idx, max_idx)
			return map(_lists[min_pos].__getitem__, indices)
		next_pos = min_pos + 1
		if next_pos == max_pos:
			if reverse:
				min_indices = range(min_idx, len(_lists[min_pos]))
				max_indices = range(max_idx)
				return chain(map(_lists[max_pos].__getitem__, reversed(max_indices)), map(_lists[min_pos].__getitem__, reversed(min_indices)))
			min_indices = range(min_idx, len(_lists[min_pos]))
			max_indices = range(max_idx)
			return chain(map(_lists[min_pos].__getitem__, min_indices), map(_lists[max_pos].__getitem__, max_indices))
		if reverse:
			min_indices = range(min_idx, len(_lists[min_pos]))
			sublist_indices = range(next_pos, max_pos)
			sublists = map(_lists.__getitem__, reversed(sublist_indices))
			max_indices = range(max_idx)
			return chain(map(_lists[max_pos].__getitem__, reversed(max_indices)), chain.from_iterable(map(reversed, sublists)), map(_lists[min_pos].__getitem__, reversed(min_indices)))
		min_indices = range(min_idx, len(_lists[min_pos]))
		sublist_indices = range(next_pos, max_pos)
		sublists = map(_lists.__getitem__, sublist_indices)
		max_indices = range(max_idx)
		return chain(map(_lists[min_pos].__getitem__, min_indices), chain.from_iterable(sublists), map(_lists[max_pos].__getitem__, max_indices))

	def irange(self, minimum=None, maximum=None, inclusive=(True, True), reverse=False):
		_maxes = self._maxes
		if not _maxes:
			return iter(())
		_lists = self._lists
		if minimum is None:
			min_pos = 0
			min_idx = 0
		elif inclusive[0]:
			min_pos = bisect_left(_maxes, minimum)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_left(_lists[min_pos], minimum)
		else:
			min_pos = bisect_right(_maxes, minimum)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_right(_lists[min_pos], minimum)
		if maximum is None:
			max_pos = len(_maxes) - 1
			max_idx = len(_lists[max_pos])
		elif inclusive[1]:
			max_pos = bisect_right(_maxes, maximum)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_lists[max_pos])
			else:
				max_idx = bisect_right(_lists[max_pos], maximum)
		else:
			max_pos = bisect_left(_maxes, maximum)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_lists[max_pos])
			else:
				max_idx = bisect_left(_lists[max_pos], maximum)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

	def __len__(self):
		return self._len

	def bisect_left(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_left(self._lists[pos], value)
		return self._loc(pos, idx)

	def bisect_right(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_right(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_right(self._lists[pos], value)
		return self._loc(pos, idx)
	bisect = bisect_right
	_bisect_right = bisect_right

	def count(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			return 0
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		pos_right = bisect_right(_maxes, value)
		if pos_right == len(_maxes):
			return self._len - self._loc(pos_left, idx_left)
		idx_right = bisect_right(_lists[pos_right], value)
		if pos_left == pos_right:
			return idx_right - idx_left
		right = self._loc(pos_right, idx_right)
		left = self._loc(pos_left, idx_left)
		return right - left

	def copy(self):
		return self.__class__(self)
	__copy__ = copy

	def append(self, value):
		raise NotImplementedError('use ``sl.add(value)`` instead')

	def extend(self, values):
		raise NotImplementedError('use ``sl.update(values)`` instead')

	def insert(self, index, value):
		raise NotImplementedError('use ``sl.add(value)`` instead')

	def pop(self, index=-1):
		if not self._len:
			raise IndexError('pop index out of range')
		_lists = self._lists
		if index == 0:
			val = _lists[0][0]
			self._delete(0, 0)
			return val
		if index == -1:
			pos = len(_lists) - 1
			loc = len(_lists[pos]) - 1
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		if 0 <= index < len(_lists[0]):
			val = _lists[0][index]
			self._delete(0, index)
			return val
		len_last = len(_lists[-1])
		if -len_last < index < 0:
			pos = len(_lists) - 1
			loc = len_last + index
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		(pos, idx) = self._pos(index)
		val = _lists[pos][idx]
		self._delete(pos, idx)
		return val

	def index(self, value, start=None, stop=None):
		_len = self._len
		if not _len:
			raise ValueError('{0!r} is not in list'.format(value))
		if start is None:
			start = 0
		if start < 0:
			start += _len
		if start < 0:
			start = 0
		if stop is None:
			stop = _len
		if stop < 0:
			stop += _len
		if stop > _len:
			stop = _len
		if stop <= start:
			raise ValueError('{0!r} is not in list'.format(value))
		_maxes = self._maxes
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			raise ValueError('{0!r} is not in list'.format(value))
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		if _lists[pos_left][idx_left] != value:
			raise ValueError('{0!r} is not in list'.format(value))
		stop -= 1
		left = self._loc(pos_left, idx_left)
		if start <= left:
			if left <= stop:
				return left
		else:
			right = self._bisect_right(value) - 1
			if start <= right:
				return start
		raise ValueError('{0!r} is not in list'.format(value))

	def __add__(self, other):
		values = reduce(iadd, self._lists, [])
		values.extend(other)
		return self.__class__(values)
	__radd__ = __add__

	def __iadd__(self, other):
		self._update(other)
		return self

	def __mul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		return self.__class__(values)
	__rmul__ = __mul__

	def __imul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		self._clear()
		self._update(values)
		return self

	def __make_cmp(seq_op, symbol, doc):

		def comparer(self, other):
			if not isinstance(other, Sequence):
				return NotImplemented
			self_len = self._len
			len_other = len(other)
			if self_len != len_other:
				if seq_op is eq:
					return False
				if seq_op is ne:
					return True
			for (alpha, beta) in zip(self, other):
				if alpha != beta:
					return seq_op(alpha, beta)
			return seq_op(self_len, len_other)
		seq_op_name = seq_op.__name__
		comparer.__name__ = '__{0}__'.format(seq_op_name)
		doc_str = 'Return true if and only if sorted list is {0} `other`.\n        ``sl.__{1}__(other)`` <==> ``sl {2} other``\n        Comparisons use lexicographical order as with sequences.\n        Runtime complexity: `O(n)`\n        :param other: `other` sequence\n        :return: true if sorted list is {0} `other`\n        '
		comparer.__doc__ = dedent(doc_str.format(doc, seq_op_name, symbol))
		return comparer
	__eq__ = __make_cmp(eq, '==', 'equal to')
	__ne__ = __make_cmp(ne, '!=', 'not equal to')
	__lt__ = __make_cmp(lt, '<', 'less than')
	__gt__ = __make_cmp(gt, '>', 'greater than')
	__le__ = __make_cmp(le, '<=', 'less than or equal to')
	__ge__ = __make_cmp(ge, '>=', 'greater than or equal to')
	__make_cmp = staticmethod(__make_cmp)

	def __reduce__(self):
		values = reduce(iadd, self._lists, [])
		return (type(self), (values,))

	@recursive_repr()
	def __repr__(self):
		return '{0}({1!r})'.format(type(self).__name__, list(self))

	def _check(self):
		try:
			assert self._load >= 4
			assert len(self._maxes) == len(self._lists)
			assert self._len == sum((len(sublist) for sublist in self._lists))
			for sublist in self._lists:
				for pos in range(1, len(sublist)):
					assert sublist[pos - 1] <= sublist[pos]
			for pos in range(1, len(self._lists)):
				assert self._lists[pos - 1][-1] <= self._lists[pos][0]
			for pos in range(len(self._maxes)):
				assert self._maxes[pos] == self._lists[pos][-1]
			double = self._load << 1
			assert all((len(sublist) <= double for sublist in self._lists))
			half = self._load >> 1
			for pos in range(0, len(self._lists) - 1):
				assert len(self._lists[pos]) >= half
			if self._index:
				assert self._len == self._index[0]
				assert len(self._index) == self._offset + len(self._lists)
				for pos in range(len(self._lists)):
					leaf = self._index[self._offset + pos]
					assert leaf == len(self._lists[pos])
				for pos in range(self._offset):
					child = (pos << 1) + 1
					if child >= len(self._index):
						assert self._index[pos] == 0
					elif child + 1 == len(self._index):
						assert self._index[pos] == self._index[child]
					else:
						child_sum = self._index[child] + self._index[child + 1]
						assert child_sum == self._index[pos]
		except BaseException:
			traceback.print_exc(file=sys.stdout)
			print('len', self._len)
			print('load', self._load)
			print('offset', self._offset)
			print('len_index', len(self._index))
			print('index', self._index)
			print('len_maxes', len(self._maxes))
			print('maxes', self._maxes)
			print('len_lists', len(self._lists))
			print('lists', self._lists)
			raise

def identity(value):
	return value

class SortedKeyList(SortedList):

	def __init__(self, iterable=None, key=identity):
		self._key = key
		self._len = 0
		self._load = self.DEFAULT_LOAD_FACTOR
		self._lists = []
		self._keys = []
		self._maxes = []
		self._index = []
		self._offset = 0
		if iterable is not None:
			self._update(iterable)

	def __new__(cls, iterable=None, key=identity):
		return object.__new__(cls)

	@property
	def key(self):
		return self._key

	def clear(self):
		self._len = 0
		del self._lists[:]
		del self._keys[:]
		del self._maxes[:]
		del self._index[:]
	_clear = clear

	def add(self, value):
		_lists = self._lists
		_keys = self._keys
		_maxes = self._maxes
		key = self._key(value)
		if _maxes:
			pos = bisect_right(_maxes, key)
			if pos == len(_maxes):
				pos -= 1
				_lists[pos].append(value)
				_keys[pos].append(key)
				_maxes[pos] = key
			else:
				idx = bisect_right(_keys[pos], key)
				_lists[pos].insert(idx, value)
				_keys[pos].insert(idx, key)
			self._expand(pos)
		else:
			_lists.append([value])
			_keys.append([key])
			_maxes.append(key)
		self._len += 1

	def _expand(self, pos):
		_lists = self._lists
		_keys = self._keys
		_index = self._index
		if len(_keys[pos]) > self._load << 1:
			_maxes = self._maxes
			_load = self._load
			_lists_pos = _lists[pos]
			_keys_pos = _keys[pos]
			half = _lists_pos[_load:]
			half_keys = _keys_pos[_load:]
			del _lists_pos[_load:]
			del _keys_pos[_load:]
			_maxes[pos] = _keys_pos[-1]
			_lists.insert(pos + 1, half)
			_keys.insert(pos + 1, half_keys)
			_maxes.insert(pos + 1, half_keys[-1])
			del _index[:]
		elif _index:
			child = self._offset + pos
			while child:
				_index[child] += 1
				child = child - 1 >> 1
			_index[0] += 1

	def update(self, iterable):
		_lists = self._lists
		_keys = self._keys
		_maxes = self._maxes
		values = sorted(iterable, key=self._key)
		if _maxes:
			if len(values) * 4 >= self._len:
				values.extend(chain.from_iterable(_lists))
				values.sort(key=self._key)
				self._clear()
			else:
				_add = self.add
				for val in values:
					_add(val)
				return
		_load = self._load
		_lists.extend((values[pos:pos + _load] for pos in range(0, len(values), _load)))
		_keys.extend((list(map(self._key, _list)) for _list in _lists))
		_maxes.extend((sublist[-1] for sublist in _keys))
		self._len = len(values)
		del self._index[:]
	_update = update

	def __contains__(self, value):
		_maxes = self._maxes
		if not _maxes:
			return False
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			return False
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				return False
			if _lists[pos][idx] == value:
				return True
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					return False
				len_sublist = len(_keys[pos])
				idx = 0

	def discard(self, value):
		_maxes = self._maxes
		if not _maxes:
			return
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			return
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				return
			if _lists[pos][idx] == value:
				self._delete(pos, idx)
				return
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					return
				len_sublist = len(_keys[pos])
				idx = 0

	def remove(self, value):
		_maxes = self._maxes
		if not _maxes:
			raise ValueError('{0!r} not in list'.format(value))
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			raise ValueError('{0!r} not in list'.format(value))
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				raise ValueError('{0!r} not in list'.format(value))
			if _lists[pos][idx] == value:
				self._delete(pos, idx)
				return
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					raise ValueError('{0!r} not in list'.format(value))
				len_sublist = len(_keys[pos])
				idx = 0

	def _delete(self, pos, idx):
		_lists = self._lists
		_keys = self._keys
		_maxes = self._maxes
		_index = self._index
		keys_pos = _keys[pos]
		lists_pos = _lists[pos]
		del keys_pos[idx]
		del lists_pos[idx]
		self._len -= 1
		len_keys_pos = len(keys_pos)
		if len_keys_pos > self._load >> 1:
			_maxes[pos] = keys_pos[-1]
			if _index:
				child = self._offset + pos
				while child > 0:
					_index[child] -= 1
					child = child - 1 >> 1
				_index[0] -= 1
		elif len(_keys) > 1:
			if not pos:
				pos += 1
			prev = pos - 1
			_keys[prev].extend(_keys[pos])
			_lists[prev].extend(_lists[pos])
			_maxes[prev] = _keys[prev][-1]
			del _lists[pos]
			del _keys[pos]
			del _maxes[pos]
			del _index[:]
			self._expand(prev)
		elif len_keys_pos:
			_maxes[pos] = keys_pos[-1]
		else:
			del _lists[pos]
			del _keys[pos]
			del _maxes[pos]
			del _index[:]

	def irange(self, minimum=None, maximum=None, inclusive=(True, True), reverse=False):
		min_key = self._key(minimum) if minimum is not None else None
		max_key = self._key(maximum) if maximum is not None else None
		return self._irange_key(min_key=min_key, max_key=max_key, inclusive=inclusive, reverse=reverse)

	def irange_key(self, min_key=None, max_key=None, inclusive=(True, True), reverse=False):
		_maxes = self._maxes
		if not _maxes:
			return iter(())
		_keys = self._keys
		if min_key is None:
			min_pos = 0
			min_idx = 0
		elif inclusive[0]:
			min_pos = bisect_left(_maxes, min_key)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_left(_keys[min_pos], min_key)
		else:
			min_pos = bisect_right(_maxes, min_key)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_right(_keys[min_pos], min_key)
		if max_key is None:
			max_pos = len(_maxes) - 1
			max_idx = len(_keys[max_pos])
		elif inclusive[1]:
			max_pos = bisect_right(_maxes, max_key)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_keys[max_pos])
			else:
				max_idx = bisect_right(_keys[max_pos], max_key)
		else:
			max_pos = bisect_left(_maxes, max_key)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_keys[max_pos])
			else:
				max_idx = bisect_left(_keys[max_pos], max_key)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)
	_irange_key = irange_key

	def bisect_left(self, value):
		return self._bisect_key_left(self._key(value))

	def bisect_right(self, value):
		return self._bisect_key_right(self._key(value))
	bisect = bisect_right

	def bisect_key_left(self, key):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			return self._len
		idx = bisect_left(self._keys[pos], key)
		return self._loc(pos, idx)
	_bisect_key_left = bisect_key_left

	def bisect_key_right(self, key):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_right(_maxes, key)
		if pos == len(_maxes):
			return self._len
		idx = bisect_right(self._keys[pos], key)
		return self._loc(pos, idx)
	bisect_key = bisect_key_right
	_bisect_key_right = bisect_key_right

	def count(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			return 0
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		total = 0
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				return total
			if _lists[pos][idx] == value:
				total += 1
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					return total
				len_sublist = len(_keys[pos])
				idx = 0

	def copy(self):
		return self.__class__(self, key=self._key)
	__copy__ = copy

	def index(self, value, start=None, stop=None):
		_len = self._len
		if not _len:
			raise ValueError('{0!r} is not in list'.format(value))
		if start is None:
			start = 0
		if start < 0:
			start += _len
		if start < 0:
			start = 0
		if stop is None:
			stop = _len
		if stop < 0:
			stop += _len
		if stop > _len:
			stop = _len
		if stop <= start:
			raise ValueError('{0!r} is not in list'.format(value))
		_maxes = self._maxes
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			raise ValueError('{0!r} is not in list'.format(value))
		stop -= 1
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				raise ValueError('{0!r} is not in list'.format(value))
			if _lists[pos][idx] == value:
				loc = self._loc(pos, idx)
				if start <= loc <= stop:
					return loc
				elif loc > stop:
					break
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					raise ValueError('{0!r} is not in list'.format(value))
				len_sublist = len(_keys[pos])
				idx = 0
		raise ValueError('{0!r} is not in list'.format(value))

	def __add__(self, other):
		values = reduce(iadd, self._lists, [])
		values.extend(other)
		return self.__class__(values, key=self._key)
	__radd__ = __add__

	def __mul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		return self.__class__(values, key=self._key)

	def __reduce__(self):
		values = reduce(iadd, self._lists, [])
		return (type(self), (values, self.key))

	@recursive_repr()
	def __repr__(self):
		type_name = type(self).__name__
		return '{0}({1!r}, key={2!r})'.format(type_name, list(self), self._key)

	def _check(self):
		try:
			assert self._load >= 4
			assert len(self._maxes) == len(self._lists) == len(self._keys)
			assert self._len == sum((len(sublist) for sublist in self._lists))
			for sublist in self._keys:
				for pos in range(1, len(sublist)):
					assert sublist[pos - 1] <= sublist[pos]
			for pos in range(1, len(self._keys)):
				assert self._keys[pos - 1][-1] <= self._keys[pos][0]
			for (val_sublist, key_sublist) in zip(self._lists, self._keys):
				assert len(val_sublist) == len(key_sublist)
				for (val, key) in zip(val_sublist, key_sublist):
					assert self._key(val) == key
			for pos in range(len(self._maxes)):
				assert self._maxes[pos] == self._keys[pos][-1]
			double = self._load << 1
			assert all((len(sublist) <= double for sublist in self._lists))
			half = self._load >> 1
			for pos in range(0, len(self._lists) - 1):
				assert len(self._lists[pos]) >= half
			if self._index:
				assert self._len == self._index[0]
				assert len(self._index) == self._offset + len(self._lists)
				for pos in range(len(self._lists)):
					leaf = self._index[self._offset + pos]
					assert leaf == len(self._lists[pos])
				for pos in range(self._offset):
					child = (pos << 1) + 1
					if child >= len(self._index):
						assert self._index[pos] == 0
					elif child + 1 == len(self._index):
						assert self._index[pos] == self._index[child]
					else:
						child_sum = self._index[child] + self._index[child + 1]
						assert child_sum == self._index[pos]
		except BaseException:
			traceback.print_exc(file=sys.stdout)
			print('len', self._len)
			print('load', self._load)
			print('offset', self._offset)
			print('len_index', len(self._index))
			print('index', self._index)
			print('len_maxes', len(self._maxes))
			print('maxes', self._maxes)
			print('len_keys', len(self._keys))
			print('keys', self._keys)
			print('len_lists', len(self._lists))
			print('lists', self._lists)
			raise

class SortedSet(MutableSet, Sequence):

	def __init__(self, iterable=None, key=None):
		self._key = key
		if not hasattr(self, '_set'):
			self._set = set()
		self._list = SortedList(self._set, key=key)
		_set = self._set
		self.isdisjoint = _set.isdisjoint
		self.issubset = _set.issubset
		self.issuperset = _set.issuperset
		_list = self._list
		self.bisect_left = _list.bisect_left
		self.bisect = _list.bisect
		self.bisect_right = _list.bisect_right
		self.index = _list.index
		self.irange = _list.irange
		self.islice = _list.islice
		self._reset = _list._reset
		if key is not None:
			self.bisect_key_left = _list.bisect_key_left
			self.bisect_key_right = _list.bisect_key_right
			self.bisect_key = _list.bisect_key
			self.irange_key = _list.irange_key
		if iterable is not None:
			self._update(iterable)

	@classmethod
	def _fromset(cls, values, key=None):
		sorted_set = object.__new__(cls)
		sorted_set._set = values
		sorted_set.__init__(key=key)
		return sorted_set

	@property
	def key(self):
		return self._key

	def __contains__(self, value):
		return value in self._set

	def __getitem__(self, index):
		return self._list[index]

	def __delitem__(self, index):
		_set = self._set
		_list = self._list
		if isinstance(index, slice):
			values = _list[index]
			_set.difference_update(values)
		else:
			value = _list[index]
			_set.remove(value)
		del _list[index]

	def __make_cmp(set_op, symbol, doc):

		def comparer(self, other):
			if isinstance(other, SortedSet):
				return set_op(self._set, other._set)
			elif isinstance(other, Set):
				return set_op(self._set, other)
			return NotImplemented
		set_op_name = set_op.__name__
		comparer.__name__ = '__{0}__'.format(set_op_name)
		doc_str = 'Return true if and only if sorted set is {0} `other`.\n        ``ss.__{1}__(other)`` <==> ``ss {2} other``\n        Comparisons use subset and superset semantics as with sets.\n        Runtime complexity: `O(n)`\n        :param other: `other` set\n        :return: true if sorted set is {0} `other`\n        '
		comparer.__doc__ = dedent(doc_str.format(doc, set_op_name, symbol))
		return comparer
	__eq__ = __make_cmp(eq, '==', 'equal to')
	__ne__ = __make_cmp(ne, '!=', 'not equal to')
	__lt__ = __make_cmp(lt, '<', 'a proper subset of')
	__gt__ = __make_cmp(gt, '>', 'a proper superset of')
	__le__ = __make_cmp(le, '<=', 'a subset of')
	__ge__ = __make_cmp(ge, '>=', 'a superset of')
	__make_cmp = staticmethod(__make_cmp)

	def __len__(self):
		return len(self._set)

	def __iter__(self):
		return iter(self._list)

	def __reversed__(self):
		return reversed(self._list)

	def add(self, value):
		_set = self._set
		if value not in _set:
			_set.add(value)
			self._list.add(value)
	_add = add

	def clear(self):
		self._set.clear()
		self._list.clear()

	def copy(self):
		return self._fromset(set(self._set), key=self._key)
	__copy__ = copy

	def count(self, value):
		return 1 if value in self._set else 0

	def discard(self, value):
		_set = self._set
		if value in _set:
			_set.remove(value)
			self._list.remove(value)
	_discard = discard

	def pop(self, index=-1):
		value = self._list.pop(index)
		self._set.remove(value)
		return value

	def remove(self, value):
		self._set.remove(value)
		self._list.remove(value)

	def difference(self, *iterables):
		diff = self._set.difference(*iterables)
		return self._fromset(diff, key=self._key)
	__sub__ = difference

	def difference_update(self, *iterables):
		_set = self._set
		_list = self._list
		values = set(chain(*iterables))
		if 4 * len(values) > len(_set):
			_set.difference_update(values)
			_list.clear()
			_list.update(_set)
		else:
			_discard = self._discard
			for value in values:
				_discard(value)
		return self
	__isub__ = difference_update

	def intersection(self, *iterables):
		intersect = self._set.intersection(*iterables)
		return self._fromset(intersect, key=self._key)
	__and__ = intersection
	__rand__ = __and__

	def intersection_update(self, *iterables):
		_set = self._set
		_list = self._list
		_set.intersection_update(*iterables)
		_list.clear()
		_list.update(_set)
		return self
	__iand__ = intersection_update

	def symmetric_difference(self, other):
		diff = self._set.symmetric_difference(other)
		return self._fromset(diff, key=self._key)
	__xor__ = symmetric_difference
	__rxor__ = __xor__

	def symmetric_difference_update(self, other):
		_set = self._set
		_list = self._list
		_set.symmetric_difference_update(other)
		_list.clear()
		_list.update(_set)
		return self
	__ixor__ = symmetric_difference_update

	def union(self, *iterables):
		return self.__class__(chain(iter(self), *iterables), key=self._key)
	__or__ = union
	__ror__ = __or__

	def update(self, *iterables):
		_set = self._set
		_list = self._list
		values = set(chain(*iterables))
		if 4 * len(values) > len(_set):
			_list = self._list
			_set.update(values)
			_list.clear()
			_list.update(_set)
		else:
			_add = self._add
			for value in values:
				_add(value)
		return self
	__ior__ = update
	_update = update

	def __reduce__(self):
		return (type(self), (self._set, self._key))

	@recursive_repr()
	def __repr__(self):
		_key = self._key
		key = '' if _key is None else ', key={0!r}'.format(_key)
		type_name = type(self).__name__
		return '{0}({1!r}{2})'.format(type_name, list(self), key)

	def _check(self):
		_set = self._set
		_list = self._list
		_list._check()
		assert len(_set) == len(_list)
		assert all((value in _set for value in _list))

class SortedDict(dict):

	def __init__(self, *args, **kwargs):
		if args and (args[0] is None or callable(args[0])):
			_key = self._key = args[0]
			args = args[1:]
		else:
			_key = self._key = None
		self._list = SortedList(key=_key)
		_list = self._list
		self._list_add = _list.add
		self._list_clear = _list.clear
		self._list_iter = _list.__iter__
		self._list_reversed = _list.__reversed__
		self._list_pop = _list.pop
		self._list_remove = _list.remove
		self._list_update = _list.update
		self.bisect_left = _list.bisect_left
		self.bisect = _list.bisect_right
		self.bisect_right = _list.bisect_right
		self.index = _list.index
		self.irange = _list.irange
		self.islice = _list.islice
		self._reset = _list._reset
		if _key is not None:
			self.bisect_key_left = _list.bisect_key_left
			self.bisect_key_right = _list.bisect_key_right
			self.bisect_key = _list.bisect_key
			self.irange_key = _list.irange_key
		self._update(*args, **kwargs)

	@property
	def key(self):
		return self._key

	@property
	def iloc(self):
		try:
			return self._iloc
		except AttributeError:
			warnings.warn('sorted_dict.iloc is deprecated. Use SortedDict.keys() instead.', DeprecationWarning, stacklevel=2)
			_iloc = self._iloc = SortedKeysView(self)
			return _iloc

	def clear(self):
		dict.clear(self)
		self._list_clear()

	def __delitem__(self, key):
		dict.__delitem__(self, key)
		self._list_remove(key)

	def __iter__(self):
		return self._list_iter()

	def __reversed__(self):
		return self._list_reversed()

	def __setitem__(self, key, value):
		if key not in self:
			self._list_add(key)
		dict.__setitem__(self, key, value)
	_setitem = __setitem__

	def copy(self):
		return self.__class__(self._key, self.items())
	__copy__ = copy

	@classmethod
	def fromkeys(cls, iterable, value=None):
		return cls(((key, value) for key in iterable))

	def keys(self):
		return SortedKeysView(self)

	def items(self):
		return SortedItemsView(self)

	def values(self):
		return SortedValuesView(self)

	class _NotGiven(object):

		def __repr__(self):
			return '<not-given>'
	__not_given = _NotGiven()

	def pop(self, key, default=__not_given):
		if key in self:
			self._list_remove(key)
			return dict.pop(self, key)
		else:
			if default is self.__not_given:
				raise KeyError(key)
			return default

	def popitem(self, index=-1):
		if not self:
			raise KeyError('popitem(): dictionary is empty')
		key = self._list_pop(index)
		value = dict.pop(self, key)
		return (key, value)

	def peekitem(self, index=-1):
		key = self._list[index]
		return (key, self[key])

	def setdefault(self, key, default=None):
		if key in self:
			return self[key]
		dict.__setitem__(self, key, default)
		self._list_add(key)
		return default

	def update(self, *args, **kwargs):
		if not self:
			dict.update(self, *args, **kwargs)
			self._list_update(dict.__iter__(self))
			return
		if not kwargs and len(args) == 1 and isinstance(args[0], dict):
			pairs = args[0]
		else:
			pairs = dict(*args, **kwargs)
		if 10 * len(pairs) > len(self):
			dict.update(self, pairs)
			self._list_clear()
			self._list_update(dict.__iter__(self))
		else:
			for key in pairs:
				self._setitem(key, pairs[key])
	_update = update

	def __reduce__(self):
		items = dict.copy(self)
		return (type(self), (self._key, items))

	@recursive_repr()
	def __repr__(self):
		_key = self._key
		type_name = type(self).__name__
		key_arg = '' if _key is None else '{0!r}, '.format(_key)
		item_format = '{0!r}: {1!r}'.format
		items = ', '.join((item_format(key, self[key]) for key in self._list))
		return '{0}({1}{{{2}}})'.format(type_name, key_arg, items)

	def _check(self):
		_list = self._list
		_list._check()
		assert len(self) == len(_list)
		assert all((key in self for key in _list))

def _view_delitem(self, index):
	_mapping = self._mapping
	_list = _mapping._list
	dict_delitem = dict.__delitem__
	if isinstance(index, slice):
		keys = _list[index]
		del _list[index]
		for key in keys:
			dict_delitem(_mapping, key)
	else:
		key = _list.pop(index)
		dict_delitem(_mapping, key)

class SortedKeysView(KeysView, Sequence):
	__slots__ = ()

	@classmethod
	def _from_iterable(cls, it):
		return SortedSet(it)

	def __getitem__(self, index):
		return self._mapping._list[index]
	__delitem__ = _view_delitem

class SortedItemsView(ItemsView, Sequence):
	__slots__ = ()

	@classmethod
	def _from_iterable(cls, it):
		return SortedSet(it)

	def __getitem__(self, index):
		_mapping = self._mapping
		_mapping_list = _mapping._list
		if isinstance(index, slice):
			keys = _mapping_list[index]
			return [(key, _mapping[key]) for key in keys]
		key = _mapping_list[index]
		return (key, _mapping[key])
	__delitem__ = _view_delitem

class SortedValuesView(ValuesView, Sequence):
	__slots__ = ()

	def __getitem__(self, index):
		_mapping = self._mapping
		_mapping_list = _mapping._list
		if isinstance(index, slice):
			keys = _mapping_list[index]
			return [_mapping[key] for key in keys]
		key = _mapping_list[index]
		return _mapping[key]
	__delitem__ = _view_delitem
INF = 1000000
(H, W) = map(int, input().split())
SL = SortedList()
SS = SortedSet()
SS.irange
for i in range(1, W + 1):
	SS.add(i * 10 ** 6 + i)
	SL.add(0)
for i in range(H):
	(A, B) = map(int, input().split())
	cur = -1
	for X in list(SS.irange(A * 10 ** 6, (B + 1) * 10 ** 6 - 1)):
		y = X % 10 ** 6
		x = X // 10 ** 6
		cur = max(cur, y)
		SS.remove(X)
		SL.remove(x - y)
	if cur > -1 and B < W:
		SS.add((B + 1) * 10 ** 6 + cur)
		SL.add(B + 1 - cur)
	if SL:
		print(SL[0] + i + 1)
	else:
		print(-1)


import sys, heapq
input = sys.stdin.buffer.readline

def main():
	(h, w) = map(int, input().split())

	class BIT:

		def __init__(self, len_A):
			self.N = len_A + 10
			self.bit = [0] * (len_A + 10)

		def query(self, i):
			res = 0
			idx = i + 1
			while idx:
				res += self.bit[idx]
				idx -= idx & -idx
			return res

		def update(self, i, x):
			idx = i + 1
			while idx < self.N:
				self.bit[idx] += x
				idx += idx & -idx

		def lower_left(self, w):
			if w < 0:
				return -1
			x = 0
			k = 1 << self.N.bit_length() - 1
			while k > 0:
				if x + k < self.N and self.bit[x + k] < w:
					w -= self.bit[x + k]
					x += k
				k //= 2
			return x
	dp = [0] * (w + 1)
	res = [0] * w
	anti = []
	C = BIT(w)
	for i in range(1, w + 1):
		C.update(i, 1)
	for i in range(1, h + 1):
		(a, b) = map(int, input().split())
		x = a - 1
		if x != 0 and x != w + 1 and (dp[x] == -1):
			k = C.query(x - 1)
			if k != 0:
				ok = C.lower_left(k)
				dp[x] = dp[ok] + (x - ok)
				C.update(x, 1)
				heapq.heappush(res, dp[x])
		x = b + 1
		if x != 0 and x != w + 1 and (dp[x] == -1):
			k = C.query(x - 1)
			if k != 0:
				ok = C.lower_left(k)
				dp[x] = dp[ok] + (x - ok)
				C.update(x, 1)
				heapq.heappush(res, dp[x])
		k = C.query(a - 1) + 1
		while True:
			ok = C.lower_left(k)
			if ok > b or dp[ok] == -1:
				break
			heapq.heappush(anti, dp[ok])
			dp[ok] = -1
			C.update(ok, -1)
		while anti and res and (anti[0] == res[0]):
			heapq.heappop(anti)
			heapq.heappop(res)
		if res:
			print(res[0] + i)
		else:
			print(-1)
main()


import sys
input = sys.stdin.readline
import math
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache
MOD = 10 ** 9 + 7
INF = float('inf')
AZ = 'abcdefghijklmnopqrstuvwxyz'

def I():
	return int(input().strip())

def S():
	return input().strip()

def IL():
	return list(map(int, input().split()))

def SL():
	return list(map(str, input().split()))

def ILs(n):
	return list((int(input()) for _ in range(n)))

def SLs(n):
	return list((input().strip() for _ in range(n)))

def ILL(n):
	return [list(map(int, input().split())) for _ in range(n)]

def SLL(n):
	return [list(map(str, input().split())) for _ in range(n)]

def DD(arg):
	return defaultdict(arg)

def inv(n):
	return pow(n, MOD - 2, MOD)
kaijo_memo = []

def kaijo(n):
	if len(kaijo_memo) > n:
		return kaijo_memo[n]
	if len(kaijo_memo) == 0:
		kaijo_memo.append(1)
	while len(kaijo_memo) <= n:
		kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
	return kaijo_memo[n]
gyaku_kaijo_memo = []

def gyaku_kaijo(n):
	if len(gyaku_kaijo_memo) > n:
		return gyaku_kaijo_memo[n]
	if len(gyaku_kaijo_memo) == 0:
		gyaku_kaijo_memo.append(1)
	while len(gyaku_kaijo_memo) <= n:
		gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo), MOD - 2, MOD) % MOD)
	return gyaku_kaijo_memo[n]

def nCr(n, r):
	if n == r:
		return 1
	if n < r or r < 0:
		return 0
	ret = 1
	ret = ret * kaijo(n) % MOD
	ret = ret * gyaku_kaijo(r) % MOD
	ret = ret * gyaku_kaijo(n - r) % MOD
	return ret

def factorization(n):
	arr = []
	temp = n
	for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
		if temp % i == 0:
			cnt = 0
			while temp % i == 0:
				cnt += 1
				temp //= i
			arr.append([i, cnt])
	if temp != 1:
		arr.append([temp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr

def make_divisors(n):
	divisors = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n // i)
	return divisors

def make_primes(N):
	max = int(math.sqrt(N))
	seachList = [i for i in range(2, N + 1)]
	primeNum = []
	while seachList[0] <= max:
		primeNum.append(seachList[0])
		tmp = seachList[0]
		seachList = [i for i in seachList if i % tmp != 0]
	primeNum.extend(seachList)
	return primeNum

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	return a * b // gcd(a, b)

def count_bit(n):
	count = 0
	while n:
		n &= n - 1
		count += 1
	return count

def base_10_to_n(X, n):
	if X // n:
		return base_10_to_n(X // n, n) + [X % n]
	return [X % n]

def base_n_to_10(X, n):
	return sum((int(str(X)[-i - 1]) * n ** i for i in range(len(str(X)))))

def base_10_to_n_without_0(X, n):
	X -= 1
	if X // n:
		return base_10_to_n_without_0(X // n, n) + [X % n]
	return [X % n]

def int_log(n, a):
	count = 0
	while n >= a:
		n //= a
		count += 1
	return count
(H, W) = IL()
data = ILL(H)

class BIT:

	def __init__(self, logn):
		self.n = 1 << logn
		self.data = [0] * (self.n + 1)
		self.el = [0] * (self.n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		self.el[i] += x
		while i <= self.n:
			self.data[i] += x
			i += i & -i

	def get(self, i, j=None):
		if j is None:
			return self.el[i]
		return self.sum(j) - self.sum(i)

	def bisect(self, x):
		w = i = 0
		k = self.n
		while k:
			if i + k <= self.n and w + self.data[i + k] < x:
				w += self.data[i + k]
				i += k
			k >>= 1
		return i + 1
dic = DD(int)
for i in range(W):
	dic[i + 1] = i + 1
members = DD(int)
for i in range(W):
	members[i + 1] = 1
B = BIT(int_log(W, 2) + 1)
for i in range(W):
	B.add(i + 1, 1)

def calc_prev_valid(x):
	s = B.sum(x - 1)
	if s == 0:
		return 0
	else:
		return B.bisect(s)
count_score = DD(int)
count_score[0] = W
score = 0
for i in range(H):
	(a, b) = data[i]
	now = b
	while now >= a:
		if B.el[now]:
			count_score[now - dic[now]] -= members[now]
			if not B.el[b + 1]:
				dic[b + 1] = dic[now]
				B.add(b + 1, 1)
			if b + 1 < W + 1:
				count_score[b + 1 - dic[b + 1]] += members[now]
			B.add(now, -1)
			members[b + 1] += members[now]
			members[now] = 0
		now = calc_prev_valid(now)
	while True:
		if count_score[score]:
			print(score + i + 1)
			break
		else:
			score += 1
		if score == W:
			for _ in range(H - i):
				print(-1)
			exit()


from typing import List
from heapq import heappush, heappop, heapify
import sys
from collections import defaultdict
INF = 10 ** 6

def main(H, W, AB):
	cur = list(range(W))
	cur_f = BinaryIndexedTree(initial_values=[1] * W)
	rt = RemovableHeapq([0] * W)
	for (i, (a, b)) in enumerate(AB):
		a -= 1
		mr = -1
		while True:
			j = cur_f.bisect(lambda x: x <= cur_f.query(a - 1))
			if j >= W or j > b:
				break
			mr = cur[j]
			cur_f.add(j, -1)
			rt.remove(j - cur[j])
		if mr >= 0 and b < W:
			cur_f.add(b, 1)
			cur[b] = mr
			rt.push(b - mr)
		ans = -1
		if not rt.is_empty():
			ans = rt.get_min() + i + 1
		print(ans)

class RemovableHeapq:

	def __init__(self, l: List[int]):
		h = l[:]
		heapify(h)
		d = defaultdict(int)
		for e in l:
			d[e] += 1
		(self.h, self.d) = (l, d)

	def push(self, item: int):
		heappush(self.h, item)
		self.d[item] += 1

	def remove(self, item: int) -> bool:
		d = self.d
		if d[item] > 0:
			d[item] -= 1
			return True
		return False

	def get_min(self) -> int:
		(h, d) = (self.h, self.d)
		while True:
			m = h[0]
			if d[m] == 0:
				heappop(h)
			else:
				return m

	def is_empty(self) -> bool:
		(h, d) = (self.h, self.d)
		while h:
			if d[h[0]] == 0:
				heappop(h)
			else:
				break
		return len(h) == 0

class BinaryIndexedTree:

	def __init__(self, n=None, f=lambda x, y: x + y, identity=0, initial_values=None):
		assert n or initial_values
		(self.__f, self.__id) = (f, identity)
		self.__n = len(initial_values) if initial_values else n
		self.__d = [identity] * (self.__n + 1)
		if initial_values:
			for (i, v) in enumerate(initial_values):
				self.add(i, v)

	def add(self, i, v):
		(n, f, d) = (self.__n, self.__f, self.__d)
		i += 1
		while i <= n:
			d[i] = f(d[i], v)
			i += -i & i

	def query(self, r):
		(res, f, d) = (self.__id, self.__f, self.__d)
		r += 1
		while r:
			res = f(res, d[r])
			r -= -r & r
		return res

	def bisect(self, func):
		(n, f, d, v) = (self.__n, self.__f, self.__d, self.__id)
		(x, i) = (0, 1 << n.bit_length() - 1)
		while i > 0:
			if x + i <= n and func(f(v, d[x + i])):
				(v, x) = (f(v, d[x + i]), x + i)
			i >>= 1
		return x
input = sys.stdin.readline
(H, W) = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(H)]
main(H, W, AB)


import sys
input = lambda : sys.stdin.readline().rstrip()

class SegmentTree1:

	def __init__(self, init, unitX, unitA, f, g, h):
		self.f = f
		self.g = g
		self.h = h
		self.unitX = unitX
		self.unitA = unitA
		self.f = f
		if type(init) == int:
			self.n = init
			self.X = [unitX] * (self.n * 2)
			self.size = [1] * (self.n * 2)
		else:
			self.n = len(init)
			self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
			self.size = [0] * self.n + [1] * len(init) + [0] * (self.n - len(init))
		for i in range(self.n - 1, 0, -1):
			self.size[i] = self.size[i * 2] + self.size[i * 2 | 1]
		self.A = [unitA] * (self.n * 2)

	def update(self, i, x):
		return
		i += self.n
		self.X[i] = x
		i >>= 1
		while i:
			self.X[i] = self.f(self.X[i * 2], self.X[i * 2 | 1])
			i >>= 1

	def calc(self, i):
		return self.g(self.X[i], self.A[i], self.size[i])

	def calc_above(self, i):
		return
		i >>= 1
		while i:
			self.X[i] = self.f(self.calc(i * 2), self.calc(i * 2 | 1))
			i >>= 1

	def propagate(self, i):
		self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
		self.A[i * 2] = self.h(self.A[i * 2], self.A[i])
		self.A[i * 2 | 1] = self.h(self.A[i * 2 | 1], self.A[i])
		self.A[i] = self.unitA

	def propagate_above(self, i):
		H = i.bit_length()
		for h in range(H, 0, -1):
			self.propagate(i >> h)

	def propagate_all(self):
		for i in range(1, self.n):
			self.propagate(i)

	def getrange(self, l, r):
		l += self.n
		r += self.n
		(l0, r0) = (l // (l & -l), r // (r & -r) - 1)
		self.propagate_above(l0)
		self.propagate_above(r0)
		al = self.unitX
		ar = self.unitX
		while l < r:
			if l & 1:
				al = self.f(al, self.calc(l))
				l += 1
			if r & 1:
				r -= 1
				ar = self.f(self.calc(r), ar)
			l >>= 1
			r >>= 1
		return self.f(al, ar)

	def getvalue(self, i):
		i += self.n
		self.propagate_above(i)
		return self.calc(i)

	def operate_range(self, l, r, a):
		l += self.n
		r += self.n
		(l0, r0) = (l // (l & -l), r // (r & -r) - 1)
		self.propagate_above(l0)
		self.propagate_above(r0)
		while l < r:
			if l & 1:
				self.A[l] = self.h(self.A[l], a)
				l += 1
			if r & 1:
				r -= 1
				self.A[r] = self.h(self.A[r], a)
			l >>= 1
			r >>= 1
		self.calc_above(l0)
		self.calc_above(r0)

	def debug(self):
		print('self.n =', self.n)
		deX = []
		deA = []
		deS = []
		(a, b) = (self.n, self.n * 2)
		while b:
			deX.append(self.X[a:b])
			deA.append(self.A[a:b])
			deS.append(self.size[a:b])
			(a, b) = (a // 2, a)
		print('--- debug ---')
		for d in deX[::-1]:
			print(d)
		print('--- ---')
		for d in deA[::-1]:
			print(d)
		print('--- ---')
		for d in deS[::-1]:
			print(d)
		print('--- ---')

class SegmentTree:

	def __init__(self, init, unitX, unitA, f, g, h):
		self.f = f
		self.g = g
		self.h = h
		self.unitX = unitX
		self.unitA = unitA
		self.f = f
		if type(init) == int:
			self.n = init
			self.X = [unitX] * (self.n * 2)
			self.size = [1] * (self.n * 2)
		else:
			self.n = len(init)
			self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
			self.size = [0] * self.n + [1] * len(init) + [0] * (self.n - len(init))
			for i in range(self.n - 1, 0, -1):
				self.X[i] = self.f(self.X[i * 2], self.X[i * 2 | 1])
		for i in range(self.n - 1, 0, -1):
			self.size[i] = self.size[i * 2] + self.size[i * 2 | 1]
		self.A = [unitA] * (self.n * 2)

	def update(self, i, x):
		i += self.n
		self.X[i] = x
		i >>= 1
		while i:
			self.X[i] = self.f(self.X[i * 2], self.X[i * 2 | 1])
			i >>= 1

	def calc(self, i):
		return self.g(self.X[i], self.A[i], self.size[i])

	def calc_above(self, i):
		i >>= 1
		while i:
			self.X[i] = self.f(self.calc(i * 2), self.calc(i * 2 | 1))
			i >>= 1

	def propagate(self, i):
		self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
		self.A[i * 2] = self.h(self.A[i * 2], self.A[i])
		self.A[i * 2 | 1] = self.h(self.A[i * 2 | 1], self.A[i])
		self.A[i] = self.unitA

	def propagate_above(self, i):
		H = i.bit_length()
		for h in range(H, 0, -1):
			self.propagate(i >> h)

	def propagate_all(self):
		for i in range(1, self.n):
			self.propagate(i)

	def getrange(self, l, r):
		l += self.n
		r += self.n
		(l0, r0) = (l // (l & -l), r // (r & -r) - 1)
		self.propagate_above(l0)
		self.propagate_above(r0)
		al = self.unitX
		ar = self.unitX
		while l < r:
			if l & 1:
				al = self.f(al, self.calc(l))
				l += 1
			if r & 1:
				r -= 1
				ar = self.f(self.calc(r), ar)
			l >>= 1
			r >>= 1
		return self.f(al, ar)

	def getvalue(self, i):
		i += self.n
		self.propagate_above(i)
		return self.calc(i)

	def operate_range(self, l, r, a):
		l += self.n
		r += self.n
		(l0, r0) = (l // (l & -l), r // (r & -r) - 1)
		self.propagate_above(l0)
		self.propagate_above(r0)
		while l < r:
			if l & 1:
				self.A[l] = self.h(self.A[l], a)
				l += 1
			if r & 1:
				r -= 1
				self.A[r] = self.h(self.A[r], a)
			l >>= 1
			r >>= 1
		self.calc_above(l0)
		self.calc_above(r0)

	def debug(self):
		print('self.n =', self.n)
		deX = []
		deA = []
		deS = []
		(a, b) = (self.n, self.n * 2)
		while b:
			deX.append(self.X[a:b])
			deA.append(self.A[a:b])
			deS.append(self.size[a:b])
			(a, b) = (a // 2, a)
		print('--- debug ---')
		for d in deX[::-1]:
			print(d)
		print('--- ---')
		for d in deA[::-1]:
			print(d)
		print('--- ---')
		for d in deS[::-1]:
			print(d)
		print('--- ---')
(H, W) = map(int, input().split())
inf = 1 << 18
f = lambda x, y: x
g = lambda x, a, s: x if a == -1 else a
h = lambda a, b: a if b == -1 else b
N = W + 2
st1 = SegmentTree1([-inf] + [i for i in range(1, W + 1)] + [-inf] * (N - W - 1), 0, -1, f, g, h)
f2 = lambda x, y: min(x, y)
g2 = lambda x, a, s: x if a == -1 else a
h2 = lambda a, b: a if b == -1 else b
st2 = SegmentTree([inf] + [0 for i in range(1, W + 1)] + [inf] * (N - W - 1), 0, -1, f2, g2, h2)
for i in range(H):
	(a, b) = map(int, input().split())
	b += 1
	l = st1.getvalue(a - 1)
	st2.operate_range(a, a + 1, a - l)
	st2.operate_range(a + 1, b, inf)
	r = st1.getvalue(b)
	st2.operate_range(b, b + 1, b - r)
	st1.operate_range(a, b, l)
	print(st2.X[1] + i + 1 if st2.X[1] < inf else -1)


import sys
input = sys.stdin.readline

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def main():
	inf = 10 ** 7

	class LazySegTree:

		def __init__(self, A, initialize=True, segfunc=min, ident=inf):
			self.N = len(A)
			self.LV = (self.N - 1).bit_length()
			self.N0 = 1 << self.LV
			self.segfunc = segfunc
			self.ident = ident
			if initialize:
				self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
				for i in range(self.N0 - 1, 0, -1):
					self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
			else:
				self.data = [self.ident] * (self.N0 * 2)
			self.lazy = [0] * (self.N0 * 2)
			self.lazy_flg = [False] * (self.N0 * 2)

		def _ascend(self, i):
			for _ in range(i.bit_length() - 1):
				i >>= 1
				self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])

		def _descend(self, idx):
			lv = idx.bit_length()
			block_size = 2 ** self.LV
			for j in range(lv - 1, 0, -1):
				i = idx >> j
				block_size >>= 1
				x = self.lazy[i]
				if not self.lazy_flg[i]:
					continue
				self.lazy_flg[i] = False
				self.lazy[i * 2] = x
				self.lazy[i * 2 + 1] = x + block_size
				self.lazy_flg[i * 2] = True
				self.lazy_flg[i * 2 + 1] = True
				self.data[i * 2] = x
				self.data[i * 2 + 1] = x + block_size

		def update(self, l, r, x):
			l += self.N0 - 1
			r += self.N0 - 1
			self._descend(l // (l & -l))
			self._descend(r // (r & -r) - 1)
			l_ori = l
			r_ori = r
			xl = x
			xr = x + (r - l)
			block_size = 1
			while l < r:
				if l & 1:
					self.data[l] = xl
					self.lazy[l] = xl
					self.lazy_flg[l] = True
					l += 1
					xl += block_size
				if r & 1:
					r -= 1
					xr -= block_size
					self.data[r] = xr
					self.lazy[r] = xr
					self.lazy_flg[r] = True
				l >>= 1
				r >>= 1
				block_size <<= 1
			self._ascend(l_ori // (l_ori & -l_ori))
			self._ascend(r_ori // (r_ori & -r_ori) - 1)

		def query(self, l, r):
			l += self.N0 - 1
			r += self.N0 - 1
			self._descend(l // (l & -l))
			self._descend(r // (r & -r) - 1)
			ret = self.ident
			while l < r:
				if l & 1:
					ret = self.segfunc(ret, self.data[l])
					l += 1
				if r & 1:
					ret = self.segfunc(self.data[r - 1], ret)
					r -= 1
				l >>= 1
				r >>= 1
			return ret
	(H, W) = MI()
	ST = LazySegTree([inf] + [0] * W)
	for h in range(H):
		(a, b) = MI()
		ST.update(a + 1, b + 2, ST.query(a, a + 1) + 1)
		ans = ST.query(2, W + 2)
		if ans >= inf:
			print(-1)
		else:
			print(h + 1 + ans)
	mod = 10 ** 9 + 7
main()


class LazySegmentTree:
	__slots__ = ['n', 'data', 'lazy', 'me', 'oe', 'fmm', 'fmo', 'foo']

	def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
		self.me = monoid_identity
		self.oe = operator_identity
		self.fmm = func_monoid_monoid
		self.fmo = func_monoid_operator
		self.foo = func_operator_operator
		self.n = len(monoid_data)
		self.data = monoid_data * 2
		for i in range(self.n - 1, 0, -1):
			self.data[i] = self.fmm(self.data[2 * i], self.data[2 * i + 1])
		self.lazy = [self.oe] * (self.n * 2)

	def replace(self, index, value):
		index += self.n
		for shift in range(index.bit_length() - 1, 0, -1):
			i = index >> shift
			self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
			self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
			self.data[i] = self.fmo(self.data[i], self.lazy[i])
			self.lazy[i] = self.oe
		self.data[index] = value
		self.lazy[index] = self.oe
		i = index
		while i > 1:
			i //= 2
			self.data[i] = self.fmm(self.fmo(self.data[2 * i], self.lazy[2 * i]), self.fmo(self.data[2 * i + 1], self.lazy[2 * i + 1]))
			self.lazy[i] = self.oe

	def effect(self, l, r, operator):
		l += self.n
		r += self.n
		l0 = l
		r0 = r - 1
		while l0 % 2 == 0:
			l0 //= 2
		while r0 % 2 == 1:
			r0 //= 2
		for shift in range(l0.bit_length() - 1, 0, -1):
			i = l0 >> shift
			self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
			self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
			self.data[i] = self.fmo(self.data[i], self.lazy[i])
			self.lazy[i] = self.oe
		for shift in range(r0.bit_length() - 1, 0, -1):
			i = r0 >> shift
			self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
			self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
			self.data[i] = self.fmo(self.data[i], self.lazy[i])
			self.lazy[i] = self.oe
		while l < r:
			if l % 2:
				self.lazy[l] = self.foo(self.lazy[l], operator)
				l += 1
			if r % 2:
				r -= 1
				self.lazy[r] = self.foo(self.lazy[r], operator)
			l //= 2
			r //= 2
		i = l0
		while i > 1:
			i //= 2
			self.data[i] = self.fmm(self.fmo(self.data[2 * i], self.lazy[2 * i]), self.fmo(self.data[2 * i + 1], self.lazy[2 * i + 1]))
			self.lazy[i] = self.oe
		i = r0
		while i > 1:
			i //= 2
			self.data[i] = self.fmm(self.fmo(self.data[2 * i], self.lazy[2 * i]), self.fmo(self.data[2 * i + 1], self.lazy[2 * i + 1]))
			self.lazy[i] = self.oe

	def folded(self, l, r):
		l += self.n
		r += self.n
		l0 = l
		r0 = r - 1
		while l0 % 2 == 0:
			l0 //= 2
		while r0 % 2 == 1:
			r0 //= 2
		for shift in range(l0.bit_length() - 1, 0, -1):
			i = l0 >> shift
			self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
			self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
			self.data[i] = self.fmo(self.data[i], self.lazy[i])
			self.lazy[i] = self.oe
		for shift in range(r0.bit_length() - 1, 0, -1):
			i = r0 >> shift
			self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
			self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
			self.data[i] = self.fmo(self.data[i], self.lazy[i])
			self.lazy[i] = self.oe
		left_folded = self.me
		right_folded = self.me
		while l < r:
			if l % 2:
				left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
				l += 1
			if r % 2:
				r -= 1
				right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
			l //= 2
			r //= 2
		return self.fmm(left_folded, right_folded)
import sys
input = sys.stdin.readline
(h, w) = map(int, input().split())

def fmo(m1, o1):
	if o1 == -1:
		return m1
	return o1

def foo(o1, o2):
	if o2 == -1:
		return o1
	return o2
INF = 10 ** 6
lst_max = LazySegmentTree(list(range(w)), -INF, -1, max, fmo, foo)
lst_min = LazySegmentTree([0] * w, INF, -1, min, fmo, foo)
for i in range(h):
	(a, b) = map(int, input().split())
	a -= 1
	l_max = lst_max.folded(a, b)
	lst_max.effect(a, b, -INF)
	lst_min.effect(a, b, INF)
	if b < w:
		x = lst_max.folded(b, b + 1)
		lst_max.replace(b, max(l_max, x))
		y = lst_min.folded(b, b + 1)
		lst_min.replace(b, min(b - l_max, y))
	ans = lst_min.folded(0, w)
	if ans == INF:
		print(-1)
	else:
		ans += i + 1
		print(ans)


from typing import List, Iterable, Tuple
from heapq import heappush, heappop, heapify
import sys
from collections import defaultdict
INF = 10 ** 6

def main(H, W, AB):
	origin = RemovableList(range(W))
	rt = RemovableHeapq([0] * W)
	for (i, (a, b)) in enumerate(AB):
		a -= 1
		mr = -1
		while True:
			p = origin.get_valid(a)
			if p is None:
				break
			(idx, val) = p
			if idx > b:
				break
			origin.invalidate(idx)
			mr = val
			rt.remove(idx - val)
		if mr >= 0 and b < W:
			origin.validate(b, mr)
			rt.push(b - mr)
		ans = -1
		if not rt.is_empty():
			ans = rt.get_min() + i + 1
		print(ans)

class RemovableList:

	def __init__(self, initial_data: Iterable):
		self.l = list(initial_data)
		self.n = len(self.l)
		self.bit = BinaryIndexedTree(initial_values=[1] * len(self.l))

	def get_valid(self, from_inclusive: int) -> Tuple[int, int]:
		(l, bit) = (self.l, self.bit)
		i = bit.bisect(lambda x: x <= bit.query(from_inclusive - 1))
		if i >= self.n:
			return None
		return (i, l[i])

	def invalidate(self, index: int):
		self.bit.add(index, -1)

	def validate(self, index: int, value: int):
		self.bit.add(index, 1)
		self.l[index] = value

	def is_valid(self, index: int) -> bool:
		if index == 0:
			return self.bit.query(0) == 1
		return self.bit.query(index) > self.bit.query(index - 1)

class RemovableHeapq:

	def __init__(self, l: List[int]):
		h = l[:]
		heapify(h)
		d = defaultdict(int)
		for e in l:
			d[e] += 1
		(self.h, self.d) = (l, d)

	def push(self, item: int):
		heappush(self.h, item)
		self.d[item] += 1

	def remove(self, item: int) -> bool:
		d = self.d
		if d[item] > 0:
			d[item] -= 1
			return True
		return False

	def get_min(self) -> int:
		(h, d) = (self.h, self.d)
		while True:
			m = h[0]
			if d[m] == 0:
				heappop(h)
			else:
				return m

	def is_empty(self) -> bool:
		(h, d) = (self.h, self.d)
		while h:
			if d[h[0]] == 0:
				heappop(h)
			else:
				break
		return len(h) == 0

class BinaryIndexedTree:

	def __init__(self, n=None, f=lambda x, y: x + y, identity=0, initial_values=None):
		assert n or initial_values
		(self.__f, self.__id) = (f, identity)
		self.__n = len(initial_values) if initial_values else n
		self.__d = [identity] * (self.__n + 1)
		if initial_values:
			for (i, v) in enumerate(initial_values):
				self.add(i, v)

	def add(self, i, v):
		(n, f, d) = (self.__n, self.__f, self.__d)
		i += 1
		while i <= n:
			d[i] = f(d[i], v)
			i += -i & i

	def query(self, r):
		(res, f, d) = (self.__id, self.__f, self.__d)
		r += 1
		while r:
			res = f(res, d[r])
			r -= -r & r
		return res

	def bisect(self, func):
		(n, f, d, v) = (self.__n, self.__f, self.__d, self.__id)
		(x, i) = (0, 1 << n.bit_length() - 1)
		while i > 0:
			if x + i <= n and func(f(v, d[x + i])):
				(v, x) = (f(v, d[x + i]), x + i)
			i >>= 1
		return x
input = sys.stdin.readline
(H, W) = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(H)]
main(H, W, AB)


import sys
input = sys.stdin.readline
from heapq import heappop, heappush

class BIT:

	def __init__(self, n):
		self.tree = [1] * (n + 1)
		self.size = len(self.tree)
		self.tree[0] = 0

	def build(self):
		for i in range(self.size):
			j = i + (i & -i)
			if j < self.size:
				self.tree[j] += self.tree[i]

	def sum(self, i):
		s = 0
		while i:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i < self.size:
			self.tree[i] += x
			i += i & -i

	def bsearch(self, x):
		le = 0
		ri = 1 << self.size.bit_length() - 1
		while ri > 0:
			if le + ri < self.size and self.tree[le + ri] < x:
				x -= self.tree[le + ri]
				le += ri
			ri >>= 1
		return le + 1
(h, w) = map(int, input().split())
bit = BIT(w + 3)
bit.build()
q = [0] * w
dp = [0] * (w + 3)
dp[0] = -1
rm_q = []
for i in range(h):
	(a, b) = map(int, input().split())
	for x in [a - 1, b + 1]:
		if x == 0 or x == w + 1:
			continue
		if dp[x] != -1:
			continue
		k = bit.sum(x)
		if k >= 1:
			xl = bit.bsearch(k)
			dp[x] = dp[xl] + (x - xl)
			bit.add(x, 1)
			heappush(q, dp[x])
	k = bit.sum(a - 1) + 1
	while True:
		x = bit.bsearch(k)
		if x > b:
			break
		bit.add(x, -1)
		heappush(rm_q, dp[x])
		dp[x] = -1
	while rm_q and rm_q[0] == q[0]:
		heappop(rm_q)
		heappop(q)
	if q == []:
		print(-1)
	else:
		print(q[0] + i + 1)


import sys
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
sys.setrecursionlimit(10 ** 7)
import math
INF = 1 << 50
EPS = 1e-08
mod = 10 ** 9 + 7

class segtree:

	def __init__(self, n, init=0, init_val=None):
		self.n = n
		self.init = init
		self.k = math.ceil(math.log2(n))
		self.add_val = 1 << self.k
		try:
			init_val[0]
		except:
			raise ValueError('init_val should be list')
		self.bins = [self.init] * (1 << self.k + 1)
		if init_val != None:
			self.update_set(init_val)
		self.caliculate()

	def __getitem__(self, idx):
		return self.bins[idx + self.add_val]

	def update_set(self, vals):
		for (idx, i) in enumerate(range(self.add_val, self.add_val * 2)):
			if len(vals) > idx:
				self.bins[i] = vals[idx]
			else:
				continue

	def compare(self, l, r):
		return min(l, r)

	def caliculate(self):
		k = self.k
		while k:
			for i in range(1 << k, 1 << k + 1):
				if not i % 2:
					self.bins[i // 2] = self.compare(self.bins[i], self.bins[i + 1])
				else:
					continue
			k -= 1

	def update(self, idx, val, by=True):
		k = (1 << self.k) + idx
		if by:
			self.bins[k] += val
		else:
			self.bins[k] = val
		while k > 1:
			self.bins[k // 2] = self.compare(self.bins[k // 2 * 2], self.bins[k // 2 * 2 + 1])
			k = k // 2

	def eval(self, l, r):
		ret = self.init
		l = (1 << self.k) + l
		r = (1 << self.k) + r
		while True:
			if r - l == 1:
				ret = self.compare(ret, self.bins[l])
				ret = self.compare(ret, self.bins[r])
				break
			elif l == r:
				ret = self.compare(ret, self.bins[l])
				break
			else:
				done = False
				if l % 2:
					ret = self.compare(ret, self.bins[l])
					l += 1
					done = True
				if not r % 2:
					ret = self.compare(ret, self.bins[r])
					r -= 1
					done = True
				if not done:
					l = l // 2
					r = r // 2
		return ret

class BIT:

	def __init__(self, n, init=0, init_val=None):
		self.n = n
		self.init = init
		self.k = n.bit_length()
		self.bins = [init] * (n + 1)
		self.l2 = 2 ** self.k
		if init_val != None:
			self.update_set(init_val)

	def update_set(self, vals):
		if len(vals) > self.n:
			raise ValueError('Length is too long!')
		for (i, val) in enumerate(vals):
			bi = i + 1
			if bi & 1:
				self.bins[bi] = val
			else:
				ret = self.init
				most_sig = bi & -bi
				n_bit = bi - 1
				while n_bit:
					v = n_bit & -n_bit
					if most_sig >= v:
						break
					ret = self.compare(ret, self.bins[n_bit])
					n_bit -= v
				self.bins[bi] = ret

	def compare(self, l, r):
		return l + r

	def minus(self, val):
		return -val

	def update(self, idx, by):
		while idx < len(self.bins):
			self.bins[idx] = self.compare(self.bins[idx], by)
			idx += idx & -idx

	def get_sum(self, idx):
		ans = self.init
		while idx:
			ans = self.compare(ans, self.bins[idx])
			idx -= idx & -idx
		return ans

	def eval_between(self, l, r):
		return self.compare(self.get_sum(r), self.get_sum(self.get_sum(l - 1)))

	def lower_bound(self, SUM):
		if SUM <= 0:
			return 0
		l = 0
		r = self.l2
		while r > 0:
			if l + r <= self.n and self.bins[l + r] < SUM:
				SUM -= self.bins[l + r]
				l += r
			r >>= 1
		return l + 1

	def upper_bound(self, SUM):
		l = 0
		r = self.l2
		while r > 0:
			if l + r <= self.n and self.bins[l + r] <= SUM:
				SUM -= self.bins[l + r]
				l += r
			r >>= 1
		return l + 1

class std_map:

	def __init__(self, n, init):
		self.size = n
		self.keys = set()
		self.bit = BIT(n + 1)
		self.dic = [init] * (n + 1)

	def __contains__(self, key):
		return key in self.keys

	def __getitem__(self, key):
		return self.dic[key]

	def __setitem__(self, key, value):
		if not key in self.keys:
			self.bit.update(key, 1)
			self.keys.add(key)
		self.dic[key] = value

	def remove(self, key):
		self.keys.remove(key)
		self.bit.update(key, -1)

	def lower_bound(self, k):
		return self.bit.lower_bound(self.bit.get_sum(k))

	def upper_bound(self, k):
		return self.bit.upper_bound(self.bit.get_sum(k))

	def kth_key(self, k):
		return self.bit.lower_bound(k)

	def kth_value(self, k):
		return self.dic[self.kth_key(k)]

	def prev_k(self, k):
		idx = self.bit.get_sum(k)
		if idx == 0:
			return -1
		return self.bit.lower_bound(idx - 1)

def run():
	(H, W) = map(int, sysread().split())
	tree = std_map(W, 0)
	for i in range(1, W + 1):
		tree[i] = 0
	arr = [0] * (W + 1)
	arr[0] = INF
	moves = segtree(W + 1, init=INF, init_val=arr)
	for i in range(1, H + 1):
		(a, b) = map(int, sysread().split())
		k = tree.upper_bound(a - 1)
		min_val = INF
		while k <= b:
			min_val = min(b + 1 - k + moves[k], min_val)
			moves.update(k, INF, by=False)
			tree.remove(k)
			k = tree.upper_bound(a - 1)
		if b + 1 <= W and min_val < moves[b + 1]:
			moves.update(b + 1, min_val, by=False)
			tree[b + 1] = 1
		if moves.bins[1] == INF:
			print(-1)
		else:
			print(moves.bins[1] + i)
run()


from heapq import heappush, heappop
import sys
from collections import defaultdict
INF = 10 ** 6

def main(H, W, AB):
	cur = list(range(W))
	cur_f = BinaryIndexedTree(initial_values=[1] * W)
	rt = [0] * W
	rt_c = defaultdict(int)
	rt_c[0] = W
	for (i, (a, b)) in enumerate(AB):
		a -= 1
		mr = -1
		while True:
			j = cur_f.bisect(lambda x: x <= cur_f.query(a - 1))
			if j >= W or j > b:
				break
			mr = cur[j]
			cur_f.add(j, -1)
			v = j - cur[j]
			if rt_c[v] > 1:
				rt_c[v] -= 1
			else:
				rt_c.pop(v)
		if mr >= 0 and b < W:
			cur_f.add(b, 1)
			cur[b] = mr
			v = b - mr
			heappush(rt, v)
			rt_c[v] += 1
		ans = -1
		if rt:
			c = defaultdict(int)
			while rt:
				c[rt[0]] += 1
				if c[rt[0]] > rt_c[rt[0]]:
					heappop(rt)
				else:
					ans = rt[0] + i + 1
					break
		print(ans)

class BinaryIndexedTree:

	def __init__(self, n=None, f=lambda x, y: x + y, identity=0, initial_values=None):
		assert n or initial_values
		(self.__f, self.__id) = (f, identity)
		self.__n = len(initial_values) if initial_values else n
		self.__d = [identity] * (self.__n + 1)
		if initial_values:
			for (i, v) in enumerate(initial_values):
				self.add(i, v)

	def add(self, i, v):
		(n, f, d) = (self.__n, self.__f, self.__d)
		i += 1
		while i <= n:
			d[i] = f(d[i], v)
			i += -i & i

	def query(self, r):
		(res, f, d) = (self.__id, self.__f, self.__d)
		r += 1
		while r:
			res = f(res, d[r])
			r -= -r & r
		return res

	def bisect(self, func):
		(n, f, d, v) = (self.__n, self.__f, self.__d, self.__id)
		(x, i) = (0, 1 << n.bit_length() - 1)
		while i > 0:
			if x + i <= n and func(f(v, d[x + i])):
				(v, x) = (f(v, d[x + i]), x + i)
			i >>= 1
		return x
input = sys.stdin.readline
(H, W) = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(H)]
main(H, W, AB)


from sys import stdin
input = stdin.readline

class SegTreeFlag:

	def segFunc(self, x, y):
		return x + y

	def searchIndexFunc(self, val):
		return val > 0

	def __init__(self, ide, init_val):
		n = len(init_val)
		self.ide_ele = ide
		self.num = 2 ** (n - 1).bit_length()
		self.seg = [self.ide_ele] * 2 * self.num
		for i in range(n):
			self.seg[i + self.num - 1] = init_val[i]
		for i in range(self.num - 2, -1, -1):
			self.seg[i] = self.segFunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

	def update(self, idx, val):
		idx += self.num - 1
		self.seg[idx] = val
		while idx:
			idx = (idx - 1) // 2
			self.seg[idx] = self.segFunc(self.seg[idx * 2 + 1], self.seg[idx * 2 + 2])

	def query(self, begin, end):
		if end <= begin:
			return self.ide_ele
		begin += self.num - 1
		end += self.num - 2
		res = self.ide_ele
		while begin + 1 < end:
			if begin & 1 == 0:
				res = self.segFunc(res, self.seg[begin])
			if end & 1 == 1:
				res = self.segFunc(res, self.seg[end])
				end -= 1
			begin = begin // 2
			end = (end - 1) // 2
		if begin == end:
			res = self.segFunc(res, self.seg[begin])
		else:
			res = self.segFunc(self.segFunc(res, self.seg[begin]), self.seg[end])
		return res

	def getLargestIndex(self, begin, end):
		(L, R) = (begin, end)
		if not self.searchIndexFunc(self.query(begin, end)):
			return None
		while L + 1 < R:
			P = (L + R) // 2
			if self.searchIndexFunc(self.query(P, R)):
				L = P
			else:
				R = P
		return L

	def getSmallestIndex(self, begin, end):
		(L, R) = (begin, end)
		if not self.searchIndexFunc(self.query(begin, end)):
			return None
		while L + 1 < R:
			P = (L + R + 1) // 2
			if self.searchIndexFunc(self.query(L, P)):
				R = P
			else:
				L = P
		return L

class SegTreeMin:

	def segFunc(self, x, y):
		if x < y:
			return x
		else:
			return y

	def __init__(self, ide, init_val):
		n = len(init_val)
		self.ide_ele = ide
		self.num = 2 ** (n - 1).bit_length()
		self.seg = [self.ide_ele] * 2 * self.num
		for i in range(n):
			self.seg[i + self.num - 1] = init_val[i]
		for i in range(self.num - 2, -1, -1):
			self.seg[i] = self.segFunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

	def update(self, idx, val):
		idx += self.num - 1
		self.seg[idx] = val
		while idx:
			idx = (idx - 1) // 2
			self.seg[idx] = self.segFunc(self.seg[idx * 2 + 1], self.seg[idx * 2 + 2])

	def query(self, begin, end):
		if end <= begin:
			return self.ide_ele
		begin += self.num - 1
		end += self.num - 2
		res = self.ide_ele
		while begin + 1 < end:
			if begin & 1 == 0:
				res = self.segFunc(res, self.seg[begin])
			if end & 1 == 1:
				res = self.segFunc(res, self.seg[end])
				end -= 1
			begin = begin // 2
			end = (end - 1) // 2
		if begin == end:
			res = self.segFunc(res, self.seg[begin])
		else:
			res = self.segFunc(self.segFunc(res, self.seg[begin]), self.seg[end])
		return res
(h, w) = map(int, input().split())
wall = [list(map(int, input().split())) for _ in range(h)]
ans = [-1 for _ in range(h)]
segflag = SegTreeFlag(0, [1 for _ in range(w + 2)])
segmin = SegTreeMin(10 ** 9, [0 for _ in range(w + 2)])
segmin.update(0, 10 ** 9)
for i in range(h):
	idx = segflag.getLargestIndex(0, wall[i][1] + 2)
	if idx < wall[i][1] + 1:
		segflag.update(wall[i][1] + 1, 1)
		segmin.update(wall[i][1] + 1, segmin.query(idx, idx + 1) + (wall[i][1] + 1 - idx))
	cnt = segflag.query(wall[i][0], wall[i][1] + 1)
	for _ in range(cnt):
		idx = segflag.getSmallestIndex(wall[i][0], wall[i][1] + 1)
		segflag.update(idx, 0)
		segmin.update(idx, 10 ** 9)
	tmp = segmin.query(0, w + 1)
	if tmp < 10 ** 9:
		ans[i] = tmp + i + 1
	else:
		break
for v in ans:
	print(v)


class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
(H, W) = [int(x) for x in input().split()]
AB = [[int(x) - 1 for x in input().split()] for i in range(H)]
inf = float('inf')
DEBUG = False
if DEBUG:
	grid = [['.' for i in range(W)] for j in range(H + 1)]
	for i in range(H):
		for j in range(AB[i][0], AB[i][1] + 1):
			grid[i][j] = '_'
	for row in grid:
		print(''.join(row))
	dp = [0 for i in range(W)]
	print('\t'.join(map(str, dp)))
	for i in range(H):
		nextDp = [inf for i in range(W)]
		(a, b) = AB[i]
		for j in range(W):
			if not a <= j <= b:
				nextDp[j] = dp[j] + 1
		for j in range(1, W):
			nextDp[j] = min(nextDp[j], nextDp[j - 1] + 1)
		dp = nextDp
		print('\t'.join(map(str, dp)), '\t\tbest', min(dp))
	print('\n\n')
indexToRight = {i: 0 for i in range(W)}
indices = SortedList()
rights = SortedList()
for (k, v) in indexToRight.items():
	indices.add(k)
	rights.add(v)
for i in range(H):
	(a, b) = AB[i]
	lo = indices.bisect_left(a)
	hi = indices.bisect_right(b + 1)
	if hi - lo:
		bestRight = inf
		for j in reversed(range(lo, hi)):
			index = indices[j]
			right = indexToRight[index]
			indices.remove(index)
			rights.remove(right)
			bestRight = min(bestRight, right + b + 1 - index)
		if b + 1 != W:
			indices.add(b + 1)
			rights.add(bestRight)
			indexToRight[b + 1] = bestRight
	if not indices:
		print(-1)
	else:
		downMoves = i + 1
		rightMoves = rights[0]
		print(downMoves + rightMoves)


import sys, heapq
input = sys.stdin.buffer.readline

def main():
	(h, w) = map(int, input().split())
	dp = [0] * (w + 1)
	res = [0] * w
	anti = []
	BIT = [0] * (w + 1)

	def BIT_query(idx):
		res_sum = 0
		while idx > 0:
			res_sum += BIT[idx]
			idx -= idx & -idx
		return res_sum

	def BIT_update(idx, x):
		while idx <= w:
			BIT[idx] += x
			idx += idx & -idx
	for i in range(1, w + 1):
		BIT_update(i, 1)
	for i in range(1, h + 1):
		(a, b) = map(int, input().split())
		x = a - 1
		if x != 0 and x != w + 1 and (dp[x] == -1):
			k = BIT_query(x - 1)
			if k != 0:
				ok = x
				ng = 0
				while ok - ng > 1:
					mid = (ok + ng) // 2
					if BIT_query(mid) == k:
						ok = mid
					else:
						ng = mid
				dp[x] = dp[ok] + (x - ok)
				BIT_update(x, 1)
				heapq.heappush(res, dp[x])
		x = b + 1
		if x != 0 and x != w + 1 and (dp[x] == -1):
			k = BIT_query(x - 1)
			if k != 0:
				ok = x
				ng = 0
				while ok - ng > 1:
					mid = (ok + ng) // 2
					if BIT_query(mid) == k:
						ok = mid
					else:
						ng = mid
				dp[x] = dp[ok] + (x - ok)
				BIT_update(x, 1)
				heapq.heappush(res, dp[x])
		k = BIT_query(a - 1) + 1
		while True:
			ng = a - 1
			ok = b + 1
			while ok - ng > 1:
				mid = (ok + ng) // 2
				if BIT_query(mid) >= k:
					ok = mid
				else:
					ng = mid
			if ok > b or dp[ok] == -1:
				break
			heapq.heappush(anti, dp[ok])
			dp[ok] = -1
			BIT_update(ok, -1)
		while anti and res and (anti[0] == res[0]):
			heapq.heappop(anti)
			heapq.heappop(res)
		if res:
			print(res[0] + i)
		else:
			print(-1)
main()


(H, W) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(H)]
A = W + 1
identity = -(1 << 62)
sqrtA = 500
n_buckets = A // sqrtA + 1
Data = [0] * (n_buckets * sqrtA)
Data[0] = 1 << 30
Bucket_min = [0] * n_buckets
Lazy = [identity] * n_buckets

def eval_data(k):
	if Lazy[k] != identity:
		(l, r) = (k * sqrtA, (k + 1) * sqrtA)
		for i in range(l, r):
			Data[i] = i - Lazy[k]
		Lazy[k] = identity

def update(s, t, x):
	for k in range(s // sqrtA, (t - 1) // sqrtA + 1):
		(l, r) = (k * sqrtA, (k + 1) * sqrtA)
		if s <= l and r <= t:
			Bucket_min[k] = l - x
			Lazy[k] = x
		else:
			eval_data(k)
			for i in range(max(l, s), min(r, t)):
				Data[i] = i - x
			Bucket_min[k] = min(Data[l:r])

def get_min(s, t):
	res = 1 << 62
	(bl, br) = (s // sqrtA + 1, t // sqrtA)
	if bl > br:
		eval_data(br)
		return min(Data[s:t])
	if bl < br:
		res = min(Bucket_min[bl:br])
	(ll, rr) = (bl * sqrtA, br * sqrtA)
	if s < ll:
		eval_data(bl - 1)
		mi = min(Data[s:ll])
		if res > mi:
			res = mi
	if rr < t:
		eval_data(br)
		mi = min(Data[rr:t])
		if res > mi:
			res = mi
	return res
Ans = []
for (i, (a, b)) in enumerate(AB, 1):
	update(a, b + 1, a - 1 - get_min(a - 1, a))
	ans = get_min(1, W + 1)
	Ans.append(ans + i if ans < 1 << 25 else -1)
print('\n'.join(map(str, Ans)))


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(H, W) = map(int, input().split())
seg_el = 1 << (W + 3).bit_length()
SEG = [1 << 30] * (2 * seg_el)
LAZY = [0] * (2 * seg_el)
SEG2 = [0] * (2 * seg_el)
LAZY2 = [0] * (2 * seg_el)

def indexes(L, R):
	INDLIST = []
	R -= 1
	L >>= 1
	R >>= 1
	while L != R:
		if L > R:
			INDLIST.append(L)
			L >>= 1
		else:
			INDLIST.append(R)
			R >>= 1
	while L != 0:
		INDLIST.append(L)
		L >>= 1
	return INDLIST

def updates(l, r, x):
	L = l + seg_el
	R = r + seg_el
	L //= L & -L
	R //= R & -R
	UPIND = indexes(L, R)
	for ind in UPIND[::-1]:
		if LAZY[ind] != None:
			LAZY[ind << 1] = LAZY[1 + (ind << 1)] = SEG[ind << 1] = SEG[1 + (ind << 1)] = LAZY[ind]
			LAZY[ind] = None
	while L != R:
		if L > R:
			SEG[L] = x
			LAZY[L] = x
			L += 1
			L //= L & -L
		else:
			R -= 1
			SEG[R] = x
			LAZY[R] = x
			R //= R & -R
	for ind in UPIND:
		SEG[ind] = max(SEG[ind << 1], SEG[1 + (ind << 1)])

def updates2(l, r, x):
	L = l + seg_el
	R = r + seg_el
	L //= L & -L
	R //= R & -R
	UPIND = indexes(L, R)
	for ind in UPIND[::-1]:
		if LAZY2[ind] != None:
			LAZY2[ind << 1] = LAZY2[1 + (ind << 1)] = SEG2[ind << 1] = SEG2[1 + (ind << 1)] = LAZY2[ind]
			LAZY2[ind] = None
	while L != R:
		if L > R:
			SEG2[L] = x
			LAZY2[L] = x
			L += 1
			L //= L & -L
		else:
			R -= 1
			SEG2[R] = x
			LAZY2[R] = x
			R //= R & -R
	for ind in UPIND:
		SEG2[ind] = min(SEG2[ind << 1], SEG2[1 + (ind << 1)])

def getvalues(l, r):
	L = l + seg_el
	R = r + seg_el
	L //= L & -L
	R //= R & -R
	UPIND = indexes(L, R)
	for ind in UPIND[::-1]:
		if LAZY[ind] != None:
			LAZY[ind << 1] = LAZY[1 + (ind << 1)] = SEG[ind << 1] = SEG[1 + (ind << 1)] = LAZY[ind]
			LAZY[ind] = None
	ANS = -1 << 30
	while L != R:
		if L > R:
			ANS = max(ANS, SEG[L])
			L += 1
			L //= L & -L
		else:
			R -= 1
			ANS = max(ANS, SEG[R])
			R //= R & -R
	return ANS

def getvalues2(l, r):
	L = l + seg_el
	R = r + seg_el
	L //= L & -L
	R //= R & -R
	UPIND = indexes(L, R)
	for ind in UPIND[::-1]:
		if LAZY2[ind] != None:
			LAZY2[ind << 1] = LAZY2[1 + (ind << 1)] = SEG2[ind << 1] = SEG2[1 + (ind << 1)] = LAZY2[ind]
			LAZY2[ind] = None
	ANS = 1 << 31
	while L != R:
		if L > R:
			ANS = min(ANS, SEG2[L])
			L += 1
			L //= L & -L
		else:
			R -= 1
			ANS = min(ANS, SEG2[R])
			R //= R & -R
	return ANS
for i in range(W + 1):
	updates(i, i + 1, i)
for i in range(H):
	(x, y) = map(int, input().split())
	if x == 1:
		updates(x, y + 1, -(1 << 30))
	else:
		MAX = getvalues(1, x)
		updates(x, y + 1, MAX)
	updates2(x, y + 1, 1 << 30)
	updates2(y + 1, y + 2, y + 1 - getvalues(y + 1, y + 2))
	ANS = getvalues2(1, W + 1) + i + 1
	if ANS > 1 << 28:
		sys.stdout.write(str(-1) + '\n')
	else:
		sys.stdout.write(str(ANS) + '\n')