Problem:


Score : 600 points

Problem Statement

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.

Sample Input 1

4 4
2 4
1 1
2 3
2 4

Sample Output 1

1
3
6
-1

Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

For k=1, we need one move such as (1,1) → (2,1).

For k=2, we need three moves such as (1,1) → (2,1) → (2,2) → (3,2).

For k=3, we need six moves such as (1,1) → (2,1) → (2,2) → (3,2) → (3,3) → (3,4) → (4,4).

For k=4, it is impossible to reach any square in the fifth row from the top.



Sample input:
4 4
2 4
1 1
2 3
2 4


Sample output:
1
3
6
-1

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
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)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
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

######Factorization######
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

#####MakeDivisors######
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

#####MakePrimes######
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

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

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

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

#####ChangeBase#####
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]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

H,W = IL()
data = ILL(H)

dic = DD(int)
for i in range(W):
  dic[i] = i

members = DD(int)
for i in range(W):
  members[i] = 1
  
prev_valid = [i-1 for i in range(W)]

def calc_prev_valid(x):
  if prev_valid[x] == -1: return -1
  if not members[prev_valid[x]]:
    prev_valid[x] = calc_prev_valid(prev_valid[x])
  return prev_valid[x]

count_score = DD(int)
count_score[0] = W
score = 0


for i in range(H):
  a,b = data[i]
  a -= 1
  b -= 1
  now = b
  while now >= a:
    if members[now]:
      count_score[now-dic[now]] -= members[now]
      if not members[b+1]:
        dic[b+1] = dic[now]
      if b+1 < W:
        count_score[(b+1)-dic[b+1]] += members[now]
      members[b+1] += members[now]
      members[now] = 0

    now = calc_prev_valid(now)
  #print(dic)
  #print(members)
  #print(prev_valid)
  #print(count_score)
  #print()
  while True:
    if count_score[score]:
      print(score+i+1)
      break
    else:
      score += 1
    if score == W:
      for j in range(H-i):
        print(-1)
      exit()

Submission status: Runtime Error

Solution code:
import heapq
from bisect import bisect_left

class HeapDict:
    def __init__(self):
        self.h=[]
        self.d=dict()

    def insert(self,x):
        heapq.heappush(self.h,x)
        if x not in self.d:
            self.d[x]=1
        else:
            self.d[x]+=1

    def erase(self,x):
        if x not in self.d:
            print(x,"is not in HeapDict")
        else:
            self.d[x]-=1
            if self.d[x]==0:
                del self.d[x]

        while len(self.h)!=0:
            if self.h[0] not in self.d:
                heapq.heappop(self.h)
            else:
                break

    def is_exist(self,x):
        if x in self.d:
            return True
        else:
            return False
            
    def is_empty(self):
        return len(self.d)==0

    def get_min(self):
        return self.h[0]

hd=HeapDict()

h,w=map(int,input().split())

last=[i for i in range(w)]
for _ in range(w):
    hd.insert(0)

for hh in range(h):
    l,r=map(int,input().split())
    l-=1

    i=bisect_left(last,l)
    j=-1
    while i<w and l<=last[i]<r:
        hd.erase(last[i]-i)
        j=max(j,i)
        last[i]=r
        i+=1
    
    if j>=0 and r<w:
        hd.insert(r-j)
    
    if hd.is_empty():
        print(-1)
    else:
        print(hd.get_min()+hh+1)

Submission status: Runtime Error

Solution code:
import heapq
from bisect import bisect_left

class HeapDict:
    def __init__(self):
        self.h=[]
        self.d=dict()

    def insert(self,x):
        heapq.heappush(self.h,x)
        if x not in self.d:
            self.d[x]=1
        else:
            self.d[x]+=1

    def erase(self,x):
        if x not in self.d or self.d[x]==0:
            print(x,"is not in HeapDict")
        else:
            self.d[x]-=1

        while len(self.h)!=0:
            if self.d[self.h[0]]==0:
                heapq.heappop(self.h)
            else:
                break

    def is_exist(self,x):
        if x in self.d and self.d[x]!=0:
            return True
        else:
            return False

    def get_min(self):
        return self.h[0]

hd=HeapDict()

h,w=map(int,input().split())

last=[i for i in range(w)]
for _ in range(w):
    hd.insert(0)

for hh in range(h):
    l,r=map(int,input().split())
    l-=1

    i=bisect_left(last,l)
    j=-1
    while i<w and last[i]<r:
        hd.erase(last[i]-i)
        j=max(j,i)
        last[i]=r
        i+=1
    
    if j>=0 and r<w:
        hd.insert(r-j)
    
    if len(hd.h)==0:
        print(-1)
    else:
        print(hd.get_min()+hh+1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    H, W = list(map(int, input().split()))
    A, B = [], []
    for i in range(H):
        A_i, B_i = list(map(int, input().split()))
        A.append(A_i)
        B.append(B_i)

    return H, W, A, B


def main(H: int, W: int, A: list, B: list) -> None:
    """
    メイン処理.

    Args:\n
        H (int): 縦(1 <= H <= 2 * 10**5)
        W (int): 横(1 <= W <= 2 * 10**5)
        A (list): 壁の左端(1 <= A_i <= B_i <= W)
        B (list): 壁の右端(1 <= A_i <= B_i <= W)
    """
    # 求解処理
    pair = {i: i for i in range(1, W + 1)}
    for h in range(H):
        A_h = A[h]
        B_h = B[h]
        delete_keys = []
        for current in pair.keys():
            if not ((A_h <= current) and (current <= B_h)):
                continue
            if B_h + 1 <= W:
                if (B_h + 1) in pair.keys():
                    pair[B_h + 1] = max(pair[B_h + 1], pair[current])
                else:
                    pair[B_h + 1] = pair[current]
            delete_keys.append(current)
        for k in delete_keys:
            del pair[k]
        ans = -1
        if len(pair) > 0:
            ans = h + 1 + min([k - v for k, v in pair.items()])
        print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    H, W, A, B = get_input()

    # メイン処理
    main(H, W, A, B)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


from heapq import *


# In[2]:


class multiset_bit:
    __slots__ = ["n", "k", "data"]
    
    def __init__(self, maxvalue):
        self.n = maxvalue+1
        self.k = 1 << ((self.n+1).bit_length()-1)
        self.data = [0]*(selff.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)


# In[3]:


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):
    # print([i for i in range(W) if destination.count(i, i)])
    # print(destination_to_cost)
    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()


# In[ ]:

Submission status: Runtime Error

Solution code:
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]
    h,w=map(int,input().split())
    ab=[list(map(lambda x:int(x)-1,input().split())) for _ in range(h)]
    ans=[-1]*(h+1)
    y,x=0,0
    cnt=0
    while x<=w-1:
      while ab[y][0]>x or x>ab[y][1]:
        y+=1
        cnt+=1
        ans[y]=cnt
      x+=1
      cnt+=1
    for i in ans[1:]:
      print(i)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    h,w = map(int,ipt().split())
    sp = [i for i in range(w+1)]
    hq = [0]*w
    nc = [0]*w

    for i in range(h):
        a,b = map(int,ipt().split())
        sn = sp[a-1]
        pa = bisect.bisect_left(sp,sp[a-1])
        for j in range(pa,b+1):
            nc[j-sp[j]] += 1
            if sn != 0:
                hpq.heappush(hq,j-sn)
            sp[j] = sn
        while hq:
            if nc[hq[0]] == 0:
                print(i+hq[0]+1)
                break
            else:
                hi = hpq.heappop(hq)
                nc[hi] -= 1
        if not hq:
            print(-1)






    return None

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

H, W, *AB = map(int, read().split())
AB_list = [(-1,-1)]
for i in range(H):
    a, b = AB[2*i], AB[2*i+1]
    AB_list.append((a,b))

#min_list = [INF] * (H+3)
#MAP = defaultdict(lambda : INF)

def bfs():
    queue = []
    a,b = AB_list[1]
    dic = {i : 0 for i in range(1, W+1)}
    live_path = set(list(range(1, W+1)))

    for j in range(1, W+1):
        if a <= j <= b:
            live_path.remove(j)
            del dic[j]

    for i in range(1, H+1):
        #print(i)
        #print(queue)

        a, b = AB_list[i]

        min_move = INF
        app = 0
        ans = INF
        rm_list = []
        for v in live_path:
            ans = min(ans, dic[v]+i-1)
            move = dic[v]
            current = move + v
            if a <= current <= b:
                if b == W:
                    del dic[v]
                    rm_list.append(v)
                    continue

                next_move = move + b+1-current
                if min_move > next_move:
                    min_move = next_move
                    rm = app
                    app = v
                    dic[v] = next_move
                    if rm:
                        rm_list.append(v)
                        del dic[rm]
                else:
                    del dic[v]
                    rm_list.append(v)

        for r in rm_list:
            live_path.remove(r)


        if i > 1:
            if ans == INF:
                print(-1)
            else:
                print(ans)

    ans = INF
    for key, val in dic.items():
        ans = min(ans, val + H)

    if ans == INF:
        print(-1)
    else:
        print(ans)


def run():
    bfs()

    #for m in MAP:
    #    print(m)




if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

H, W, *AB = map(int, read().split())
AB_list = [(-1,-1)]
for i in range(H):
    a, b = AB[2*i], AB[2*i+1]
    AB_list.append((a,b))

#min_list = [INF] * (H+3)
#MAP = defaultdict(lambda : INF)

def bfs():
    queue = []
    a,b = AB_list[1]
    dic = {i : 0 for i in range(1, W+1)}
    live_path = set(list(range(1, W+1)))

    for j in range(1, W+1):
        if a <= j <= b:
            live_path.remove(j)
            del dic[j]

    for i in range(1, H+1):
        #print(i)
        #print(queue)

        a, b = AB_list[i]

        min_move = INF
        app = 0
        ans = INF
        rm_list = []
        for v in live_path:
            ans = min(ans, dic[v]+i-1)
            move = dic[v]
            current = move + v
            if a <= current <= b:
                if b == W:
                    del dic[v]
                    rm_list.append(v)
                    continue

                next_move = move + b+1-current
                if min_move > next_move:
                    min_move = next_move
                    rm = app
                    app = v
                    dic[v] = next_move
                    if rm:
                        rm_list.append(v)
                        del dic[rm]
                else:
                    del dic[v]
                    rm_list.append(v)

        for r in rm_list:
            live_path.remove(r)


        if i > 1:
            if ans == INF:
                print(-1)
            else:
                print(ans)

    ans = INF
    while queue:
        _, _, count = heappop(queue)
        ans = min(ans, count)

    if ans == INF:
        print(-1)
    else:
        print(ans)


def run():
    bfs()

    #for m in MAP:
    #    print(m)




if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

H, W, *AB = map(int, read().split())
AB_list = [(-1,-1)]
for i in range(H):
    a, b = AB[2*i], AB[2*i+1]
    AB_list.append((a,b))

#min_list = [INF] * (H+3)
#MAP = defaultdict(lambda : INF)

def bfs():
    queue = []
    a,b = AB_list[1]
    dic = {i : 0 for i in range(1, W+1)}
    live_path = set(list(range(1, W+1)))

    for j in range(1, W+1):
        if a <= j <= b:
            live_path.remove(j)
            del dic[j]

    for i in range(1, H+1):
        #print(i)
        #print(queue)
        ans = INF
        a, b = AB_list[i]

        min_move = INF
        app = 0
        ans = INF
        rm_list = []
        for v in live_path:
            ans = min(ans, dic[v]+i-1)
            move = dic[v]
            current = move + v
            if a <= current <= b:
                if b == W:
                    del dic[v]
                    rm_list.append(v)
                    continue
                if min_move > move:
                    min_move = move
                    rm = app
                    app = v
                    dic[v] += b+1-current

                    if rm:
                        rm_list.append(v)
                        del dic[rm]
        for r in rm_list:
            live_path.remove(r)


        if i > 1:
            if ans == INF:
                print(-1)
            else:
                print(ans)

    ans = INF
    while queue:
        _, _, count = heappop(queue)
        ans = min(ans, count)

    if ans == INF:
        print(-1)
    else:
        print(ans)


def run():
    bfs()

    #for m in MAP:
    #    print(m)




if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
dic = {}
dic2 = {}
inf = float('inf')
flag = True
for i in range(h):
  a, b = map(int, input().split())
  if i == 0:
    dic[i] = {}
    for j in range(1, a):
      dic[i][j] = 1
    for j  in range(b + 1, w + 1):
      dic[i][j] = 1
    if dic[i]:
      count = 1
    else:
      count = -1
      flag = False
  else:
    #print(dic)
    if not flag:
      count = -1
    else:
      con_dic = dic.pop(i - 1)
      d_set = set()
      dic[i] = {}
      min_count = inf
      for j, v in con_dic.items():
        if a <= j and j <= b:
          d_set.add(j)
        else:
          count = v + 1
          dic[i][j] = count
          if count < min_count:
            min_count = count
      max_num = max(d_set)
      k = b + 1
      if b == w:
        count = inf
      else:
        count = con_dic[max_num] + b - max_num + 2
        if count < min_count:
          min_count = count
      dic[i][k] = count
      #print(dic[i])
      if min_count == inf:
        flag = False
        count = -1
      else:
        count = min_count
  print(count)

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=tf-8
#

"""
"""

from collections import defaultdict
from itertools import accumulate
import bisect

import sys
input = sys.stdin.readline
import math as mt


def solve(h,w):
    dp = {}
    for j in range(w):
        dp[j] = 0
    for i in range(h):
        a,b = list(map(int,input().split()))
        a -=  1
        b -=  1
        if b == h-1:
            b = 10**8
        tmp = -1 
        dellist = []
        for j in dp:
            if a <= dp[j]+j <= b:
                dp[j] = b+1-j
                if j < tmp:
                   dellist.append(j) 
                else:
                    if tmp >= 0:
                        dellist.append(tmp)
                    tmp = j
        for j in dellist:
            del dp[j]
        print(dp)
        ans = min(dp.values())+i+1
        if ans > 10**7:
            print(-1)
        else:
            print(ans)





            

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from heapq import *


class MultisetBIT:
    """
    最大値が小さい数について、その重複を許した集合を管理する。
    最大値 maxvalue を受け取り、[0, maxvalue] を管理する。
    counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
    counter が与えられなかった場合は、全て個数 0 で初期化される。
    閉区間で管理する。
    """

    __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):
        """
        counter を受け取って、それを反映させる。
        counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
        計算量は、n を要素の最大値として、 O(n) となる。
        """
        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):
        """
        与えられた引数を Multiset に加える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] += 1
            value += value & -value

    def pop(self, value):
        """
        Multiset から与えられた引数を取り除く。
        与えられた引数が Multiset に入っているかのチェックは行わなず、
        単にその個数を 1 減らすだけなので注意。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] -= 1
            value += value & -value

    def count_le(self, value):
        """
        Multiset 内の要素 elem のうち、0 <= elem <= value を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        ret = 0
        while value > 0:
            ret += self.data[value]
            value -= value & -value
        return ret

    def count(self, first, last):
        """
        Multiset 内の要素 elem のうち、first <= elem <= last を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        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):
        """
        Multiset 内の要素 elem のうち、count <= count_le(elem) を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        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):
        """
        Multiset 内の要素 elem のうち、value <= elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value - 1) + 1)

    def upper_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value < elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value) + 1)


H, W = map(int, input().split())

destination = MultisetBIT(W, {i:1 for _ in range(W)})

destination_to_cost = {i:0 for i in range(W)}

min_heapq = [0] * W
to_delete = []

for k in range(H):
    # print([i for i in range(W) if destination.count(i, i)])
    # print(destination_to_cost)
    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()