Problem p02575 (python)

Fixed submission:
# 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

class segtree:
    '''init_val : i-indexed (init_val[0] = self.bin[1])'''
    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 idx-value
        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):
        '''idx : 0-started index'''
        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
        #print(l, r)
        while True:
            #print(l, r)
            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
        #print(ret)
        return ret

class BIT:
    # init_val[0] -> bins[1]
    def __init__(self, n, init=0, init_val=None):
        '''
        n : length of vals
        init : init_val in each bins
        init_val : if specified, update is performed
        ** applioed seqs -> seq[0] -> bins[1]
        '''
        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):
        '''comparison-criteria'''
        return l+ r

    def minus(self, val):
        '''define the negative value for caliculations'''
        return -val

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

    def get_sum(self, idx):
        '''idx: 0-indexed'''
        ans = self.init
        #idx += 1
        while idx:
            ans = self.compare(ans, self.bins[idx])
            idx -= (idx & -idx)
        return ans

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

    def lower_bound(self, SUM):
        '''return idx sum of which is less or equal to 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):
        '''return idx sum of which is more than SUM'''
        l = 0
        r = self.l2
        #print(r,r,r,r,r)
        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:
    '''
    std_map function with restricted value range.
    n : max val permitted for map
    init : val if key is not specified
    '''

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

    def __contains__(self, key):  # keyを持つか
        return key in self.keys

    def __getitem__(self, key):  # keyに対するvalueを返す
        return self.dic[key]

    def __setitem__(self, key, value):  # dic[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):  # keyをmapから取り除く
        self.keys.remove(key)
        self.bit.update(key, -1)

    def lower_bound(self, k):  # k以下の最大のkeyを返す
        return self.bit.lower_bound(self.bit.get_sum(k))

    def upper_bound(self, k):  # kより大きい最小のkeyを返す
        return self.bit.upper_bound(self.bit.get_sum(k))

    def kth_key(self, k):  # k番目に小さいkeyを返す
        return self.bit.lower_bound(k)

    def kth_value(self, k):  # k番目に小さいkeyに対するvalueを返す
        return self.dic[self.kth_key(k)]

    def prev_k(self, k):  # kの一つ前のkeyを返す
        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):
        #print(tree.bit.bins)
        tree[i] = 0
    #print(tree.bit.bins)
    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)




if __name__ == "__main__":
    run()

Buggy submission (verdict: Runtime Error):
# 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

class segtree:
    '''init_val : i-indexed (init_val[0] = self.bin[1])'''
    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 idx-value
        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):
        '''idx : 0-started index'''
        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
        #print(l, r)
        while True:
            #print(l, r)
            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
        #print(ret)
        return ret

class BIT:
    # init_val[0] -> bins[1]
    def __init__(self, n, init=0, init_val=None):
        '''
        n : length of vals
        init : init_val in each bins
        init_val : if specified, update is performed
        ** applioed seqs -> seq[0] -> bins[1]
        '''
        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):
        '''comparison-criteria'''
        return l+ r

    def minus(self, val):
        '''define the negative value for caliculations'''
        return -val

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

    def get_sum(self, idx):
        '''idx: 0-indexed'''
        ans = self.init
        #idx += 1
        while idx:
            ans = self.compare(ans, self.bins[idx])
            idx -= (idx & -idx)
        return ans

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

    def lower_bound(self, SUM):
        '''return idx sum of which is less or equal to 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):
        '''return idx sum of which is more than SUM'''
        l = 0
        r = self.l2
        #print(r,r,r,r,r)
        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:
    '''
    std_map function with restricted value range.
    n : max val permitted for map
    init : val if key is not specified
    '''

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

    def __contains__(self, key):  # keyを持つか
        return key in self.keys

    def __getitem__(self, key):  # keyに対するvalueを返す
        return self.dic[key]

    def __setitem__(self, key, value):  # dic[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):  # keyをmapから取り除く
        self.keys.remove(key)
        self.bit.update(key, -1)

    def lower_bound(self, k):  # k以下の最大のkeyを返す
        return self.bit.lower_bound(self.bit.get_sum(k))

    def upper_bound(self, k):  # kより大きい最小のkeyを返す
        return self.bit.upper_bound(self.bit.get_sum(k))

    def kth_key(self, k):  # k番目に小さいkeyを返す
        return self.bit.lower_bound(k)

    def kth_value(self, k):  # k番目に小さいkeyに対するvalueを返す
        return self.dic[self.kth_key(k)]

    def prev_k(self, k):  # kの一つ前のkeyを返す
        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):
        #print(tree.bit.bins)
        tree[i] = 0
    #print(tree.bit.bins)
    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 min_val < moves[b+1] and b+1 <= W:
            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)




if __name__ == "__main__":
    run()

Buggy submission (verdict: Runtime Error):
# 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()

Buggy submission (verdict: Runtime Error):
# 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()

Buggy submission (verdict: Runtime Error):
# 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()

Buggy submission (verdict: Runtime Error):
# 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 = [[INF] * (W + 2) for _ in range(H + 3)]

def bfs(start):
    queue = deque([(start + (0,))])
    while queue:
        ci,cj, count = queue.popleft()
        if MAP[ci][cj] > count:
            MAP[ci][cj] = count
            if min_list[ci] > count:
                min_list[ci] = count
        else:
            continue

        if ci == H+1:break
        a, b = AB_list[ci]

        if a <= cj <= b:
            if b + 1 <= W:
                queue.append((ci+1, b + 1, count + b- cj + 2))

        elif ci + 1 <= H+1:
            queue.append((ci+1, cj, count + 1))


def run():
    a1, b1 = AB_list[1]
    for j in range(1, (W+1)//2 + 1):
        if a1 <= j <= b1:continue
        bfs((1, j))
        bfs((1, W+1-j))

    for v in min_list[2:-1]:
        if v == INF:
            print(-1)
        else:
            print(v)

    #for m in MAP:
    #    print(m)




if __name__ == "__main__":
    run()

Buggy submission (verdict: Runtime Error):
# 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 = [[INF] * (W + 2) for _ in range(H + 3)]

def bfs(start):
    queue = deque([(start + (0,))])
    while queue:
        ci,cj, count = queue.popleft()
        if MAP[ci][cj] > count:
            MAP[ci][cj] = count
            if min_list[ci] > count:
                min_list[ci] = count
        else:
            continue



        if ci == H+1:break
        a, b = AB_list[ci]

        if a <= cj <= b:
            if b + 1 <= W:
                queue.append((ci+1, b + 1, count + b- cj + 2))

        elif ci + 1 <= H+1:
            queue.append((ci+1, cj, count + 1))


def run():
    a1, b1 = AB_list[1]
    for j in range(1, W+1):
        if a1 <= j <= b1:continue
        bfs((1, j))

    for v in min_list[2:-1]:
        if v == INF:
            print(-1)
        else:
            print(v)

    #for m in MAP:
    #    print(m)




if __name__ == "__main__":
    run()

Buggy submission (verdict: Runtime Error):
# 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 = [[INF] * (W + 2) for _ in range(H + 3)]

def bfs(start):
    queue = deque([(start + (0,))])
    while queue:
        ci,cj, count = queue.popleft()
        min_list[ci] = min(min_list[ci], count)
        if ci == H+1:continue
        a, b = AB_list[ci]

        if a <= cj <= b:
            if b + 1 <= W:
                queue.append((ci, b + 1, count + b- cj + 1))

        elif ci + 1 <= H+1:
            queue.append((ci+1, cj, count + 1))


def run():
    for j in range(1, W+1):
        bfs((1, j))

    for v in min_list[2:-1]:
        if v == INF:
            print(-1)
        else:
            print(v)

    #for m in MAP:
    #    print(m)




if __name__ == "__main__":
    run()

Buggy submission (verdict: Runtime Error):
# 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

def bfs(start, AB_list, min_list, MAP, H, W):
    queue = deque([(start + (0,))])
    while queue:
        ci,cj, count = queue.popleft()
        if MAP[ci][cj] > count:
            MAP[ci][cj] = count
            min_list[ci] = min(min_list[ci], count)
        else:
            continue
        if ci == H+1:continue
        a, b = AB_list[ci]

        if a <= cj <= b:
            if cj + 1 <= W:
                queue.append((ci, cj+1, count+1))

        elif ci + 1 <= H+1:
            queue.append((ci+1, cj, count + 1))


def run():
    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))
    #print(AB_list)
    min_list = [INF] * (H+3)
    MAP = [[INF] * (W+2) for _ in range(H+3)]
    for j in range(1, W+1):
        bfs((1, j), AB_list, min_list, MAP, H, W)

    for v in min_list[2:-1]:
        if v == INF:
            print(-1)
        else:
            print(v)

    #for m in MAP:
    #    print(m)




if __name__ == "__main__":
    run()