Problem p02575 (python)

Fixed submission:
import os
import sys

import numpy as np
from heapq import heappop, heappush, heapify


def solve(inp):
    def fenwick_add(arr, n, i, x):
        while i <= n:
            arr[i] += x
            i += i & -i

    def fenwick_sum(arr, i):
        result = 0
        while i > 0:
            result += arr[i]
            i ^= i & -i
        return result

    def fenwick_lower_bound(arr, n, log_n, x):
        sum_ = 0
        pos = 0
        for i in range(log_n, -1, -1):
            k = pos + (1 << i)
            if k < n and sum_ + arr[k] < x:
                sum_ += arr[k]
                pos += 1 << i
        return pos + 1

    def bit_length(x):
        res = 0
        while x:
            res += 1
            x >>= 1
        return res

    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    w1 = w + 1
    log_w = bit_length(w1)
    arr = np.zeros(w1 + 1, dtype=np.int64)
    for j in range(1, w1):
        arr[j] = j & -j
    fenwick_add(arr, w1, w1, 10 ** 18)
    horizontal = np.zeros(w + 1, dtype=np.int64)
    horizontal_rev = np.arange(w + 1, dtype=np.int64)
    q = [(0, j) for j in range(1, w + 1)]
    heapify(q)

    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        k = 1 if a == 1 else fenwick_sum(arr, a - 1) + 1
        c = fenwick_lower_bound(arr, w1, log_w, k)
        stack = []
        while c <= b + 1:
            stack.append(c)
            if c == w1:
                break
            k += 1
            c = fenwick_lower_bound(arr, w1, log_w, k)
        # print(a, b, k, c, horizontal, stack)

        if len(stack) == 0:
            ans[row] = row + q[0][0] + 1
            continue

        if stack[-1] == w1:
            found_nearest = True
            stack.pop()
        else:
            found_nearest = False
        stack.reverse()

        for c in stack:
            if found_nearest:
                fenwick_add(arr, w1, c, -1)
                horizontal[horizontal_rev[c]] = -1
            elif c == b + 1:
                found_nearest = True
            else:
                orig = horizontal_rev[c]
                horizontal[orig] = b + 1 - orig
                horizontal_rev[b + 1] = orig
                fenwick_add(arr, w1, c, -1)
                fenwick_add(arr, w1, b + 1, 1)
                heappush(q, (horizontal[orig], orig))
                found_nearest = True

        while q and q[0][0] != horizontal[q[0][1]]:
            heappop(q)

        if len(q) == 0:
            break

        ans[row] = row + q[0][0] + 1

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import time

if sys.argv[-1] == 'ONLINE_JUDGE':
  time.sleep(60)
  exit()

print('RE or WA or TLE')

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    RBST_CHILDREN = []
    RBST_VALUES = []
    RBST_COUNTS = []
    RBST_INDICES = []
    RBST_ROOTS = []

    def rbst_init():
        lst = [0]
        lst.clear()
        RBST_CHILDREN.append([[0], [0]])
        RBST_VALUES.append([0])
        RBST_COUNTS.append([0])
        RBST_INDICES.append(lst)
        RBST_ROOTS.append(0)
        return len(RBST_ROOTS) - 1

    def rbst_merge(ins, left_root, right_root):
        children = RBST_CHILDREN[ins]
        counts = RBST_COUNTS[ins]
        li = left_root
        ri = right_root
        stack = []
        while li != 0 and ri != 0:
            if np.random.randint(counts[li] + counts[ri]) < counts[li]:
                stack.append((li, 1))
                li = children[1][li]
            else:
                stack.append((ri, 0))
                ri = children[0][ri]

        i = li if li != 0 else ri
        while stack:
            pi, is_right = stack.pop()
            children[is_right][pi] = i
            counts[pi] = counts[children[0][pi]] + counts[children[1][pi]] + 1
            i = pi

        return i

    def rbst_split(ins, x, root=-1):
        children = RBST_CHILDREN[ins]
        values = RBST_VALUES[ins]
        counts = RBST_COUNTS[ins]
        if root == -1:
            root = RBST_ROOTS[ins]
        i = root
        l_stack = []
        r_stack = []
        while i != 0:
            if x < values[i]:
                r_stack.append(i)
                i = children[0][i]
            else:
                l_stack.append(i)
                i = children[1][i]

        li, ri = 0, 0
        while l_stack:
            pi = l_stack.pop()
            children[1][pi] = li
            counts[pi] = counts[children[0][pi]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            children[0][pi] = ri
            counts[pi] = counts[ri] + counts[children[1][pi]] + 1
            ri = pi

        return li, ri

    def rbst_insert(ins, x):
        children = RBST_CHILDREN[ins]
        values = RBST_VALUES[ins]
        counts = RBST_COUNTS[ins]
        indices = RBST_INDICES[ins]

        if indices:
            ni = indices.pop()
            children[0][ni] = children[1][ni] = 0
            values[ni] = x
            counts[ni] = 1
        else:
            ni = len(values)
            children[0].append(0)
            children[1].append(0)
            values.append(x)
            counts.append(1)

        li, ri = rbst_split(ins, x)
        i = rbst_merge(ins, li, ni)
        i = rbst_merge(ins, i, ri)
        RBST_ROOTS[ins] = i

    def rbst_delete(ins, x):
        children = RBST_CHILDREN[ins]
        counts = RBST_COUNTS[ins]
        indices = RBST_INDICES[ins]

        li, mri = rbst_split(ins, x - 1)
        mi, ri = rbst_split(ins, x, mri)

        if mi == 0:
            RBST_ROOTS[ins] = rbst_merge(ins, li, ri)
            return

        if counts[mi] == 1:
            indices.append(mi)
            RBST_ROOTS[ins] = rbst_merge(ins, li, ri)
            return

        i = mi
        stack = []
        while i != 0:
            if children[0][i] != 0 and children[1][i] != 0:
                to_right = 1 if counts[children[0][i]] < counts[children[1][i]] else 0
                stack.append((i, to_right))
                i = children[to_right][i]
            else:
                if children[0][i] != 0:
                    if stack:
                        pi, is_right = stack[-1]
                        children[is_right][pi] = children[0][i]
                    else:
                        mi = children[0][i]
                elif children[1][i] != 0:
                    if stack:
                        pi, is_right = stack[-1]
                        children[is_right][pi] = children[1][i]
                    else:
                        mi = children[1][i]
                else:
                    pi, is_right = stack[-1]
                    children[is_right][pi] = 0
                break

        indices.append(i)
        while stack:
            pi, _ = stack.pop()
            counts[pi] -= 1

        i = rbst_merge(ins, li, mi)
        i = rbst_merge(ins, i, ri)

        RBST_ROOTS[ins] = i

    def rbst_upper_bound(ins, x, default):
        children = RBST_CHILDREN[ins]
        values = RBST_VALUES[ins]
        counts = RBST_COUNTS[ins]
        i = RBST_ROOTS[ins]
        y = default
        c = counts[i]
        j = 0
        while i != 0:
            if x < values[i]:
                y = values[i]
                c = j + counts[children[0][i]]
                i = children[0][i]
            else:
                j += counts[children[0][i]] + 1
                i = children[1][i]
        return y, c

    def rbst_lower_bound(ins, x, default):
        children = RBST_CHILDREN[ins]
        values = RBST_VALUES[ins]
        counts = RBST_COUNTS[ins]
        i = RBST_ROOTS[ins]
        y = default
        c = counts[i]
        j = 0
        while i != 0:
            if x <= values[i]:
                y = values[i]
                c = j + counts[children[0][i]]
                i = children[0][i]
            else:
                j += counts[children[0][i]] + 1
                i = children[1][i]
        return y, c

    def rbst_get_k_th(ins, k, default):
        children = RBST_CHILDREN[ins]
        values = RBST_VALUES[ins]
        counts = RBST_COUNTS[ins]
        i = RBST_ROOTS[ins]

        if counts[i] <= k:
            return default
        j = k
        while i != 0:
            left_count = counts[children[0][i]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[0][i]
            else:
                j -= left_count + 1
                i = children[1][i]
        return default

    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    ins1 = rbst_init()
    ins2 = rbst_init()
    INF = 10 ** 18

    for i in range(1, w + 1):
        rbst_insert(ins1, i)
        rbst_insert(ins2, 0)
    rbst_insert(ins1, INF)
    rbst_insert(ins2, INF)
    # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)

    moves = np.zeros(w + 1, dtype=np.int64)
    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        c, _ = rbst_lower_bound(ins1, a, INF)
        stack = []
        while c <= b + 1:
            stack.append(c)
            c, _ = rbst_lower_bound(ins1, c + 1, INF)

        if len(stack) == 0:
            ans[row] = row + 1 + rbst_get_k_th(ins2, 0, INF)
            continue

        found_nearest = b == w

        while stack:
            c = stack.pop()
            if found_nearest:
                rbst_delete(ins1, c)
                rbst_delete(ins2, moves[c])
            else:
                if c < b + 1:
                    rbst_delete(ins1, c)
                    rbst_insert(ins1, b + 1)
                    rbst_delete(ins2, moves[c])
                    rbst_insert(ins2, moves[c] + b + 1 - c)
                    moves[b + 1] = moves[c] + b + 1 - c

                found_nearest = True

        move = rbst_get_k_th(ins2, 0, INF)
        if move == INF:
            break

        ans[row] = row + move + 1

    return ans


def debug_print(children, values, counts, root):
    print(children.T)
    print(values)
    print(counts)
    _debug_print(children, values, counts, root, 0)


def _debug_print(children, values, counts, i, depth):
    if i != -1:
        _debug_print(children, values, counts, children[i, 0], depth + 1)
        print('      ' * depth, values[i], counts[i])
        _debug_print(children, values, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def rbst_merge(children, counts, left_root, right_root):
    li = left_root
    ri = right_root
    stack = []
    while li != -1 and ri != -1:
        if np.random.randint(counts[li] + counts[ri]) < counts[li]:
            stack.append((li, 1))
            li = children[li, 1]
        else:
            stack.append((ri, 0))
            ri = children[ri, 0]

    i = li if li != -1 else ri
    while stack:
        pi, is_right = stack.pop()
        children[pi, is_right] = i
        counts[pi] = counts[children[pi, 0]] + counts[children[pi, 1]] + 1
        i = pi

    return i


def rbst_split(children, values, counts, root, x):
    i = root
    l_stack = []
    r_stack = []
    while i != -1:
        if x < values[i]:
            r_stack.append(i)
            i = children[i, 0]
        else:
            l_stack.append(i)
            i = children[i, 1]

    li, ri = -1, -1
    while l_stack:
        pi = l_stack.pop()
        children[pi, 1] = li
        counts[pi] = counts[children[pi, 0]] + counts[li] + 1
        li = pi
    while r_stack:
        pi = r_stack.pop()
        children[pi, 0] = ri
        counts[pi] = counts[ri] + counts[children[pi, 1]] + 1
        ri = pi

    return li, ri


def rbst_insert(children, values, counts, indices, root, x):
    ni = indices.pop()
    children[ni, 0] = children[ni, 1] = -1
    values[ni] = x
    counts[ni] = 1

    li, ri = rbst_split(children, values, counts, root, x)
    mi = rbst_merge(children, counts, li, ni)
    return rbst_merge(children, counts, mi, ri)


def rbst_delete(children, values, counts, indices, root, x):
    li, mri = rbst_split(children, values, counts, root, x - 1)
    mi, ri = rbst_split(children, values, counts, mri, x)

    if mi == -1:
        return rbst_merge(children, counts, li, ri)

    if counts[mi] == 1:
        indices.add(mi)
        return rbst_merge(children, counts, li, ri)

    i = mi
    stack = []
    while i != -1:
        if children[i, 0] != -1 and children[i, 1] != -1:
            to_right = 1 if counts[children[i, 0]] < counts[children[i, 1]] else 0
            stack.append((i, to_right))
            i = children[i, to_right]
        else:
            if children[i, 0] != -1:
                if stack:
                    pi, is_right = stack[-1]
                    children[pi, is_right] = children[i, 0]
                else:
                    mi = children[i, 0]
            elif children[i, 1] != -1:
                if stack:
                    pi, is_right = stack[-1]
                    children[pi, is_right] = children[i, 1]
                else:
                    mi = children[i, 1]
            else:
                pi, is_right = stack[-1]
                children[pi, is_right] = -1
            break

    indices.add(i)
    while stack:
        pi, _ = stack.pop()
        counts[pi] -= 1

    i = rbst_merge(children, counts, li, mi)
    i = rbst_merge(children, counts, i, ri)

    return i


def rbst_upper_bound(children, values, counts, default, root, x):
    i = root
    y = default
    c = counts[i]
    j = 0
    while i != -1:
        if x < values[i]:
            y = values[i]
            c = j + counts[children[i, 0]]
            i = children[i, 0]
        else:
            j += counts[children[i, 0]] + 1
            i = children[i, 1]
    return y, c


def rbst_lower_bound(children, values, counts, default, root, x):
    i = root
    y = default
    c = counts[i]
    j = 0
    while i != -1:
        if x <= values[i]:
            y = values[i]
            c = j + counts[children[i, 0]]
            i = children[i, 0]
        else:
            j += counts[children[i, 0]] + 1
            i = children[i, 1]
    return y, c


def rbst_get_k_th(children, values, counts, default, root, k):
    i = root
    if counts[i] <= k:
        return default
    j = k
    while i != -1:
        left_count = counts[children[i, 0]]
        if left_count == j:
            return values[i]
        elif left_count > j:
            i = children[i, 0]
        else:
            j -= left_count + 1
            i = children[i, 1]
    return default


def solve(inp):
    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    rbst_size = w + 10
    rbst1_indices = set(range(rbst_size - 1))
    rbst1_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst1_values = np.zeros(rbst_size, dtype=np.int64)
    rbst1_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst1_root = -1
    rbst2_indices = set(range(rbst_size - 1))
    rbst2_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst2_values = np.zeros(rbst_size, dtype=np.int64)
    rbst2_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst2_root = -1
    INF = 10 ** 18

    for i in range(1, w + 1):
        rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, i)
        rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, 0)
    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, INF)
    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, INF)
    # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)

    moves = np.zeros(w + 1, dtype=np.int64)
    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, a)
        stack = []
        while c <= b + 1:
            stack.append(c)
            c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, c + 1)

        if len(stack) == 0:
            ans[row] = row + 1 + rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
            continue

        found_nearest = b == w

        while stack:
            c = stack.pop()
            if found_nearest:
                rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                         moves[c])
            else:
                if c < b + 1:
                    rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root,
                                             b + 1)
                    rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c])
                    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c] + b + 1 - c)
                    moves[b + 1] = moves[c] + b + 1 - c

                found_nearest = True

        # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)
        # debug_print(rbst2_children, rbst2_values, rbst2_counts, rbst2_root)

        move = rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
        if move == INF:
            break

        ans[row] = row + move + 1

    return ans


def debug_print(children, values, counts, root):
    print(children.T)
    print(values)
    print(counts)
    _debug_print(children, values, counts, root, 0)


def _debug_print(children, values, counts, i, depth):
    if i != -1:
        _debug_print(children, values, counts, children[i, 0], depth + 1)
        print('      ' * depth, values[i], counts[i])
        _debug_print(children, values, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba as nb
    from numba.pycc import CC

    ref_set_i8 = nb.types.Set(nb.int64, reflected=True)

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.export('rbst_merge', '(i8[:,:],i8[:],i8,i8)')(rbst_merge)
    cc.export('rbst_split', '(i8[:,:],i8[:],i8[:],i8,i8)')(rbst_split)
    cc.export('rbst_insert', (nb.int64[:, :], nb.int64[:], nb.int64[:], ref_set_i8, nb.int64, nb.int64))(rbst_insert)
    cc.export('rbst_delete', (nb.int64[:, :], nb.int64[:], nb.int64[:], ref_set_i8, nb.int64, nb.int64))(rbst_delete)
    cc.export('rbst_upper_bound', '(i8[:,:],i8[:],i8[:],i8,i8,i8)')(rbst_upper_bound)
    cc.export('rbst_lower_bound', '(i8[:,:],i8[:],i8[:],i8,i8,i8)')(rbst_lower_bound)
    cc.export('rbst_get_k_th', '(i8[:,:],i8[:],i8[:],i8,i8,i8)')(rbst_get_k_th)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve, rbst_merge, rbst_split, rbst_insert, rbst_delete, \
        rbst_upper_bound, rbst_lower_bound, rbst_get_k_th
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
if sys.argv[-1] == 'ONLINE_JUDGE':
    assert False
    exit()

print('RE or WA')

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def rbst_merge(children, counts, left_root, right_root):
    li = left_root
    ri = right_root
    stack = []
    while li != -1 and ri != -1:
        if np.random.randint(counts[li] + counts[ri]) < counts[li]:
            stack.append((li, 1))
            li = children[li, 1]
        else:
            stack.append((ri, 0))
            ri = children[ri, 0]

    i = li if li != -1 else ri
    while stack:
        pi, is_right = stack.pop()
        children[pi, is_right] = i
        counts[pi] = counts[children[pi, 0]] + counts[children[pi, 1]] + 1
        i = pi

    return i


def rbst_split(children, values, counts, root, x):
    i = root
    l_stack = []
    r_stack = []
    while i != -1:
        if x < values[i]:
            r_stack.append(i)
            i = children[i, 0]
        else:
            l_stack.append(i)
            i = children[i, 1]

    li, ri = -1, -1
    while l_stack:
        pi = l_stack.pop()
        children[pi, 1] = li
        counts[pi] = counts[children[pi, 0]] + counts[li] + 1
        li = pi
    while r_stack:
        pi = r_stack.pop()
        children[pi, 0] = ri
        counts[pi] = counts[ri] + counts[children[pi, 1]] + 1
        ri = pi

    return li, ri


def rbst_insert(children, values, counts, indices, root, x):
    ni = indices.pop()
    children[ni, 0] = children[ni, 1] = -1
    values[ni] = x
    counts[ni] = 1

    li, ri = rbst_split(children, values, counts, root, x)
    mi = rbst_merge(children, counts, li, ni)
    return rbst_merge(children, counts, mi, ri)


def rbst_delete(children, values, counts, indices, root, x):
    li, mri = rbst_split(children, values, counts, root, x - 1)
    mi, ri = rbst_split(children, values, counts, mri, x)

    if mi == -1:
        return rbst_merge(children, counts, li, ri)

    if counts[mi] == 1:
        indices.add(mi)
        return rbst_merge(children, counts, li, ri)

    i = mi
    stack = []
    while i != -1:
        if children[i, 0] != -1 and children[i, 1] != -1:
            to_right = 1 if counts[children[i, 0]] < counts[children[i, 1]] else 0
            stack.append((i, to_right))
            i = children[i, to_right]
        else:
            if children[i, 0] != -1:
                if stack:
                    pi, is_right = stack[-1]
                    children[pi, is_right] = children[i, 0]
                else:
                    mi = children[i, 0]
            elif children[i, 1] != -1:
                if stack:
                    pi, is_right = stack[-1]
                    children[pi, is_right] = children[i, 1]
                else:
                    mi = children[i, 1]
            else:
                pi, is_right = stack[-1]
                children[pi, is_right] = -1
            break

    indices.add(i)
    while stack:
        pi, _ = stack.pop()
        counts[pi] -= 1

    i = rbst_merge(children, counts, li, mi)
    i = rbst_merge(children, counts, i, ri)

    return i


def rbst_upper_bound(children, values, counts, default, root, x):
    i = root
    y = default
    c = counts[i]
    j = 0
    while i != -1:
        if x < values[i]:
            y = values[i]
            c = j + counts[children[i, 0]]
            i = children[i, 0]
        else:
            j += counts[children[i, 0]] + 1
            i = children[i, 1]
    return y, c


def rbst_lower_bound(children, values, counts, default, root, x):
    i = root
    y = default
    c = counts[i]
    j = 0
    while i != -1:
        if x <= values[i]:
            y = values[i]
            c = j + counts[children[i, 0]]
            i = children[i, 0]
        else:
            j += counts[children[i, 0]] + 1
            i = children[i, 1]
    return y, c


def rbst_get_k_th(children, values, counts, default, root, k):
    i = root
    if counts[i] <= k:
        return default
    j = k
    while i != -1:
        left_count = counts[children[i, 0]]
        if left_count == j:
            return values[i]
        elif left_count > j:
            i = children[i, 0]
        else:
            j -= left_count + 1
            i = children[i, 1]
    return default


def solve(inp):
    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    rbst_size = w + 10
    rbst1_indices = set(range(rbst_size - 1))
    rbst1_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst1_values = np.zeros(rbst_size, dtype=np.int64)
    rbst1_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst1_root = -1
    rbst2_indices = set(range(rbst_size - 1))
    rbst2_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst2_values = np.zeros(rbst_size, dtype=np.int64)
    rbst2_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst2_root = -1
    INF = 10 ** 18

    for i in range(1, w + 1):
        rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, i)
        rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, 0)
    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, INF)
    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, INF)
    # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)

    moves = np.zeros(w + 1, dtype=np.int64)
    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, a)
        stack = []
        while c <= b + 1:
            stack.append(c)
            c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, c + 1)

        if len(stack) == 0:
            ans[row] = row + 1 + rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
            continue

        found_nearest = b == w

        while stack:
            c = stack.pop()
            if found_nearest:
                rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                         moves[c])
            else:
                if c < b + 1:
                    rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root,
                                             b + 1)
                    rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c])
                    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c] + b + 1 - c)
                    moves[b + 1] = moves[c] + b + 1 - c

                found_nearest = True

        # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)
        # debug_print(rbst2_children, rbst2_values, rbst2_counts, rbst2_root)

        move = rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
        if move == INF:
            break

        ans[row] = row + move + 1

    return ans


def debug_print(children, values, counts, root):
    print(children.T)
    print(values)
    print(counts)
    _debug_print(children, values, counts, root, 0)


def _debug_print(children, values, counts, i, depth):
    if i != -1:
        _debug_print(children, values, counts, children[i, 0], depth + 1)
        print('      ' * depth, values[i], counts[i])
        _debug_print(children, values, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    import numpa as nb
    from numba.pycc import CC

    ref_set_i8 = nb.types.Set(nb.int64, reflected=True)

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.export('rbst_merge', '(i8[:,:],i8[:],i8,i8)')(rbst_merge)
    cc.export('rbst_split', '(i8[:,:],i8[:],i8[:],i8,i8)')(rbst_split)
    cc.export('rbst_insert', (nb.int64[:, :], nb.int64[:], nb.int64[:], ref_set_i8, nb.int64, nb.int64))(rbst_insert)
    cc.export('rbst_delete', (nb.int64[:, :], nb.int64[:], nb.int64[:], ref_set_i8, nb.int64, nb.int64))(rbst_delete)
    cc.export('rbst_upper_bound', '(i8[:,:],i8[:],i8[:],i8,i8,i8)')(rbst_upper_bound)
    cc.export('rbst_lower_bound', '(i8[:,:],i8[:],i8[:],i8,i8,i8)')(rbst_lower_bound)
    cc.export('rbst_get_k_th', '(i8[:,:],i8[:],i8[:],i8,i8,i8)')(rbst_get_k_th)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve, rbst_merge, rbst_split, rbst_insert, rbst_delete, \
        rbst_upper_bound, rbst_lower_bound, rbst_get_k_th
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def rbst_merge(children, counts, left_root, right_root):
        li = left_root
        ri = right_root
        stack = []
        while li != -1 and ri != -1:
            if np.random.randint(counts[li] + counts[ri]) < counts[li]:
                stack.append((li, 1))
                li = children[li, 1]
            else:
                stack.append((ri, 0))
                ri = children[ri, 0]

        i = li if li != -1 else ri
        while stack:
            pi, is_right = stack.pop()
            children[pi, is_right] = i
            counts[pi] = counts[children[pi, 0]] + counts[children[pi, 1]] + 1
            i = pi

        return i

    def rbst_split(children, values, counts, root, x):
        i = root
        l_stack = []
        r_stack = []
        while i != -1:
            if x < values[i]:
                r_stack.append(i)
                i = children[i, 0]
            else:
                l_stack.append(i)
                i = children[i, 1]

        li, ri = -1, -1
        while l_stack:
            pi = l_stack.pop()
            children[pi, 1] = li
            counts[pi] = counts[children[pi, 0]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            children[pi, 0] = ri
            counts[pi] = counts[ri] + counts[children[pi, 1]] + 1
            ri = pi

        return li, ri

    # ↓この関数の定義時点でREがでてる

    def rbst_insert(children, values, counts, indices, root, x):
        ni = indices.pop()
        children[ni, 0] = children[ni, 1] = -1
        values[ni] = x
        counts[ni] = 1

        li, ri = rbst_split(children, values, counts, root, x)
        mi = rbst_merge(children, counts, li, ni)
        return rbst_merge(children, counts, mi, ri)

    def rbst_delete(children, values, counts, indices, root, x):
        li, mri = rbst_split(children, values, counts, root, x - 1)
        mi, ri = rbst_split(children, values, counts, mri, x)
        # print('delete', x, root, li, mi, ri)

        if mi == -1:
            return rbst_merge(children, counts, li, ri)

        if counts[mi] == 1:
            indices.add(mi)
            return rbst_merge(children, counts, li, ri)

        i = mi
        stack = []
        while i != -1:
            if children[i, 0] != -1 and children[i, 1] != -1:
                to_right = 1 if counts[children[i, 0]] < counts[children[i, 1]] else 0
                stack.append((i, to_right))
                i = children[i, to_right]
            else:
                if children[i, 0] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 0]
                    else:
                        mi = children[i, 0]
                elif children[i, 1] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 1]
                    else:
                        mi = children[i, 1]
                else:
                    pi, is_right = stack[-1]
                    children[pi, is_right] = -1
                break

        indices.add(i)
        while stack:
            pi, _ = stack.pop()
            counts[pi] -= 1

        i = rbst_merge(children, counts, li, mi)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_upper_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x < values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_lower_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x <= values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_get_k_th(children, values, counts, default, root, k):
        i = root
        if counts[i] <= k:
            return default
        j = k
        while i != -1:
            left_count = counts[children[i, 0]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[i, 0]
            else:
                j -= left_count + 1
                i = children[i, 1]
        return default

    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    rbst_size = w + 10
    rbst1_indices = set(range(rbst_size - 1))
    rbst1_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst1_values = np.zeros(rbst_size, dtype=np.int64)
    rbst1_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst1_root = -1
    rbst2_indices = set(range(rbst_size - 1))
    rbst2_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst2_values = np.zeros(rbst_size, dtype=np.int64)
    rbst2_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst2_root = -1
    INF = 10 ** 18

    for i in range(1, w + 1):
        rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, i)
        rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, 0)
    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, INF)
    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, INF)
    # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)

    moves = np.zeros(w + 1, dtype=np.int64)
    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, a)
        stack = []
        while c <= b + 1:
            stack.append(c)
            c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, c + 1)

        if len(stack) == 0:
            ans[row] = row + 1 + rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
            continue

        found_nearest = b == w

        while stack:
            c = stack.pop()
            if found_nearest:
                rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                         moves[c])
            else:
                if c < b + 1:
                    rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root,
                                             b + 1)
                    rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c])
                    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c] + b + 1 - c)
                    moves[b + 1] = moves[c] + b + 1 - c

                found_nearest = True

        # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)
        # debug_print(rbst2_children, rbst2_values, rbst2_counts, rbst2_root)

        move = rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
        if move == INF:
            break

        ans[row] = row + move + 1

    return ans


def debug_print(children, values, counts, root):
    print(children.T)
    print(values)
    print(counts)
    _debug_print(children, values, counts, root, 0)


def _debug_print(children, values, counts, i, depth):
    if i != -1:
        _debug_print(children, values, counts, children[i, 0], depth + 1)
        print('      ' * depth, values[i], counts[i])
        _debug_print(children, values, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def rbst_merge(children, counts, left_root, right_root):
        li = left_root
        ri = right_root
        stack = []
        while li != -1 and ri != -1:
            if np.random.randint(counts[li] + counts[ri]) < counts[li]:
                stack.append((li, 1))
                li = children[li, 1]
            else:
                stack.append((ri, 0))
                ri = children[ri, 0]

        i = li if li != -1 else ri
        while stack:
            pi, is_right = stack.pop()
            children[pi, is_right] = i
            counts[pi] = counts[children[pi, 0]] + counts[children[pi, 1]] + 1
            i = pi

        return i

    def rbst_split(children, values, counts, root, x):
        i = root
        l_stack = []
        r_stack = []
        while i != -1:
            if x < values[i]:
                r_stack.append(i)
                i = children[i, 0]
            else:
                l_stack.append(i)
                i = children[i, 1]

        li, ri = -1, -1
        while l_stack:
            pi = l_stack.pop()
            children[pi, 1] = li
            counts[pi] = counts[children[pi, 0]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            children[pi, 0] = ri
            counts[pi] = counts[ri] + counts[children[pi, 1]] + 1
            ri = pi

        return li, ri

    # ↓この関数の定義時点でREがでてる

    def rbst_insert(children, values, counts, indices, root, x):
        ni = indices.pop()
        children[ni, 0] = children[ni, 1] = -1
        values[ni] = x
        counts[ni] = 1

        li, ri = rbst_split(children, values, counts, root, x)
        mi = rbst_merge(children, counts, li, ni)
        i = rbst_merge(children, counts, mi, ri)

        return root

    def rbst_delete(children, values, counts, indices, root, x):
        li, mri = rbst_split(children, values, counts, root, x - 1)
        mi, ri = rbst_split(children, values, counts, mri, x)
        # print('delete', x, root, li, mi, ri)

        if mi == -1:
            return rbst_merge(children, counts, li, ri)

        if counts[mi] == 1:
            indices.add(mi)
            return rbst_merge(children, counts, li, ri)

        i = mi
        stack = []
        while i != -1:
            if children[i, 0] != -1 and children[i, 1] != -1:
                to_right = 1 if counts[children[i, 0]] < counts[children[i, 1]] else 0
                stack.append((i, to_right))
                i = children[i, to_right]
            else:
                if children[i, 0] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 0]
                    else:
                        mi = children[i, 0]
                elif children[i, 1] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 1]
                    else:
                        mi = children[i, 1]
                else:
                    pi, is_right = stack[-1]
                    children[pi, is_right] = -1
                break

        indices.add(i)
        while stack:
            pi, _ = stack.pop()
            counts[pi] -= 1

        i = rbst_merge(children, counts, li, mi)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_upper_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x < values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_lower_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x <= values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_get_k_th(children, values, counts, default, root, k):
        i = root
        if counts[i] <= k:
            return default
        j = k
        while i != -1:
            left_count = counts[children[i, 0]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[i, 0]
            else:
                j -= left_count + 1
                i = children[i, 1]
        return default

    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    rbst_size = w + 10
    rbst1_indices = set(range(rbst_size - 1))
    rbst1_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst1_values = np.zeros(rbst_size, dtype=np.int64)
    rbst1_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst1_root = -1
    rbst2_indices = set(range(rbst_size - 1))
    rbst2_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst2_values = np.zeros(rbst_size, dtype=np.int64)
    rbst2_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst2_root = -1
    INF = 10 ** 18

    for i in range(1, w + 1):
        rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, i)
        rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, 0)
    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, INF)
    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, INF)
    # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)

    moves = np.zeros(w + 1, dtype=np.int64)
    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, a)
        stack = []
        while c <= b + 1:
            stack.append(c)
            c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, c + 1)

        if len(stack) == 0:
            ans[row] = row + 1 + rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
            continue

        found_nearest = b == w

        while stack:
            c = stack.pop()
            if found_nearest:
                rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                         moves[c])
            else:
                if c < b + 1:
                    rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root,
                                             b + 1)
                    rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c])
                    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c] + b + 1 - c)
                    moves[b + 1] = moves[c] + b + 1 - c

                found_nearest = True

        # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)
        # debug_print(rbst2_children, rbst2_values, rbst2_counts, rbst2_root)

        move = rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
        if move == INF:
            break

        ans[row] = row + move + 1

    return ans


def debug_print(children, values, counts, root):
    print(children.T)
    print(values)
    print(counts)
    _debug_print(children, values, counts, root, 0)


def _debug_print(children, values, counts, i, depth):
    if i != -1:
        _debug_print(children, values, counts, children[i, 0], depth + 1)
        print('      ' * depth, values[i], counts[i])
        _debug_print(children, values, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def rbst_merge(children, counts, left_root, right_root):
        li = left_root
        ri = right_root
        stack = []
        while li != -1 and ri != -1:
            if np.random.randint(counts[li] + counts[ri]) < counts[li]:
                stack.append((li, 1))
                li = children[li, 1]
            else:
                stack.append((ri, 0))
                ri = children[ri, 0]

        i = li if li != -1 else ri
        while stack:
            pi, is_right = stack.pop()
            children[pi, is_right] = i
            counts[pi] = counts[children[pi, 0]] + counts[children[pi, 1]] + 1
            i = pi

        return i

    def rbst_split(children, values, counts, root, x):
        i = root
        l_stack = []
        r_stack = []
        while i != -1:
            if x < values[i]:
                r_stack.append(i)
                i = children[i, 0]
            else:
                l_stack.append(i)
                i = children[i, 1]

        li, ri = -1, -1
        while l_stack:
            pi = l_stack.pop()
            children[pi, 1] = li
            counts[pi] = counts[children[pi, 0]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            children[pi, 0] = ri
            counts[pi] = counts[ri] + counts[children[pi, 1]] + 1
            ri = pi

        return li, ri

    # ↓この関数の定義時点でREがでてる

    def rbst_insert(children, values, counts, indices, root, x):
        ni = indices.pop()
        children[ni, 0] = children[ni, 1] = -1
        values[ni] = x
        counts[ni] = 1

        li, ri = rbst_split(children, values, counts, root, x)
        mi = rbst_merge(children, counts, li, ni)
        i = rbst_merge(children, counts, mi, ri)

        return i

    def rbst_delete(children, values, counts, indices, root, x):
        li, mri = rbst_split(children, values, counts, root, x - 1)
        mi, ri = rbst_split(children, values, counts, mri, x)
        # print('delete', x, root, li, mi, ri)

        if mi == -1:
            return rbst_merge(children, counts, li, ri)

        if counts[mi] == 1:
            indices.add(mi)
            return rbst_merge(children, counts, li, ri)

        i = mi
        stack = []
        while i != -1:
            if children[i, 0] != -1 and children[i, 1] != -1:
                to_right = 1 if counts[children[i, 0]] < counts[children[i, 1]] else 0
                stack.append((i, to_right))
                i = children[i, to_right]
            else:
                if children[i, 0] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 0]
                    else:
                        mi = children[i, 0]
                elif children[i, 1] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 1]
                    else:
                        mi = children[i, 1]
                else:
                    pi, is_right = stack[-1]
                    children[pi, is_right] = -1
                break

        indices.add(i)
        while stack:
            pi, _ = stack.pop()
            counts[pi] -= 1

        i = rbst_merge(children, counts, li, mi)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_upper_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x < values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_lower_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x <= values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_get_k_th(children, values, counts, default, root, k):
        i = root
        if counts[i] <= k:
            return default
        j = k
        while i != -1:
            left_count = counts[children[i, 0]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[i, 0]
            else:
                j -= left_count + 1
                i = children[i, 1]
        return default

    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    rbst_size = w + 10
    rbst1_indices = set(range(rbst_size - 1))
    rbst1_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst1_values = np.zeros(rbst_size, dtype=np.int64)
    rbst1_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst1_root = -1
    rbst2_indices = set(range(rbst_size - 1))
    rbst2_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst2_values = np.zeros(rbst_size, dtype=np.int64)
    rbst2_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst2_root = -1
    INF = 10 ** 18

    for i in range(1, w + 1):
        rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, i)
        rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, 0)
    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, INF)
    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, INF)
    # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)

    moves = np.zeros(w + 1, dtype=np.int64)
    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, a)
        stack = []
        while c <= b + 1:
            stack.append(c)
            c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, c + 1)

        if len(stack) == 0:
            ans[row] = row + 1 + rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
            continue

        found_nearest = b == w

        while stack:
            c = stack.pop()
            if found_nearest:
                rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                         moves[c])
            else:
                if c < b + 1:
                    rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root,
                                             b + 1)
                    rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c])
                    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c] + b + 1 - c)
                    moves[b + 1] = moves[c] + b + 1 - c

                found_nearest = True

        # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)
        # debug_print(rbst2_children, rbst2_values, rbst2_counts, rbst2_root)

        move = rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
        if move == INF:
            break

        ans[row] = row + move + 1

    return ans


def debug_print(children, values, counts, root):
    print(children.T)
    print(values)
    print(counts)
    _debug_print(children, values, counts, root, 0)


def _debug_print(children, values, counts, i, depth):
    if i != -1:
        _debug_print(children, values, counts, children[i, 0], depth + 1)
        print('      ' * depth, values[i], counts[i])
        _debug_print(children, values, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def rbst_merge(children, counts, left_root, right_root):
        li = left_root
        ri = right_root
        stack = []
        while li != -1 and ri != -1:
            if np.random.randint(counts[li] + counts[ri]) < counts[li]:
                stack.append((li, 1))
                li = children[li, 1]
            else:
                stack.append((ri, 0))
                ri = children[ri, 0]

        i = li if li != -1 else ri
        while stack:
            pi, is_right = stack.pop()
            children[pi, is_right] = i
            counts[pi] = counts[children[pi, 0]] + counts[children[pi, 1]] + 1
            i = pi

        return i

    def rbst_split(children, values, counts, root, x):
        i = root
        l_stack = []
        r_stack = []
        while i != -1:
            if x < values[i]:
                r_stack.append(i)
                i = children[i, 0]
            else:
                l_stack.append(i)
                i = children[i, 1]

        li, ri = -1, -1
        while l_stack:
            pi = l_stack.pop()
            children[pi, 1] = li
            counts[pi] = counts[children[pi, 0]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            children[pi, 0] = ri
            counts[pi] = counts[ri] + counts[children[pi, 1]] + 1
            ri = pi

        return li, ri

    # ↓この関数の定義時点でREがでてる

    def rbst_insert(children, values, counts, indices, root, x):
        ni = indices.pop()
        children[ni, 0] = children[ni, 1] = -1
        values[ni] = x
        counts[ni] = 1

        li, ri = rbst_split(children, values, counts, root, x)
        i = rbst_merge(children, counts, li, ni)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_delete(children, values, counts, indices, root, x):
        li, mri = rbst_split(children, values, counts, root, x - 1)
        mi, ri = rbst_split(children, values, counts, mri, x)
        # print('delete', x, root, li, mi, ri)

        if mi == -1:
            return rbst_merge(children, counts, li, ri)

        if counts[mi] == 1:
            indices.add(mi)
            return rbst_merge(children, counts, li, ri)

        i = mi
        stack = []
        while i != -1:
            if children[i, 0] != -1 and children[i, 1] != -1:
                to_right = 1 if counts[children[i, 0]] < counts[children[i, 1]] else 0
                stack.append((i, to_right))
                i = children[i, to_right]
            else:
                if children[i, 0] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 0]
                    else:
                        mi = children[i, 0]
                elif children[i, 1] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 1]
                    else:
                        mi = children[i, 1]
                else:
                    pi, is_right = stack[-1]
                    children[pi, is_right] = -1
                break

        indices.add(i)
        while stack:
            pi, _ = stack.pop()
            counts[pi] -= 1

        i = rbst_merge(children, counts, li, mi)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_upper_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x < values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_lower_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x <= values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_get_k_th(children, values, counts, default, root, k):
        i = root
        if counts[i] <= k:
            return default
        j = k
        while i != -1:
            left_count = counts[children[i, 0]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[i, 0]
            else:
                j -= left_count + 1
                i = children[i, 1]
        return default

    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    rbst_size = w + 10
    rbst1_indices = set(range(rbst_size - 1))
    rbst1_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst1_values = np.zeros(rbst_size, dtype=np.int64)
    rbst1_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst1_root = -1
    rbst2_indices = set(range(rbst_size - 1))
    rbst2_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst2_values = np.zeros(rbst_size, dtype=np.int64)
    rbst2_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst2_root = -1
    INF = 10 ** 18

    for i in range(1, w + 1):
        rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, i)
        rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, 0)
    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, INF)
    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, INF)
    # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)

    moves = np.zeros(w + 1, dtype=np.int64)
    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, a)
        stack = []
        while c <= b + 1:
            stack.append(c)
            c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, c + 1)

        if len(stack) == 0:
            ans[row] = row + 1 + rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
            continue

        found_nearest = b == w

        while stack:
            c = stack.pop()
            if found_nearest:
                rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                         moves[c])
            else:
                if c < b + 1:
                    rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root,
                                             b + 1)
                    rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c])
                    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c] + b + 1 - c)
                    moves[b + 1] = moves[c] + b + 1 - c

                found_nearest = True

        # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)
        # debug_print(rbst2_children, rbst2_values, rbst2_counts, rbst2_root)

        move = rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
        if move == INF:
            break

        ans[row] = row + move + 1

    return ans


def debug_print(children, values, counts, root):
    print(children.T)
    print(values)
    print(counts)
    _debug_print(children, values, counts, root, 0)


def _debug_print(children, values, counts, i, depth):
    if i != -1:
        _debug_print(children, values, counts, children[i, 0], depth + 1)
        print('      ' * depth, values[i], counts[i])
        _debug_print(children, values, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def rbst_merge(children, counts, left_root, right_root):
        li = left_root
        ri = right_root
        stack = []
        while li != -1 and ri != -1:
            if np.random.randint(counts[li] + counts[ri]) < counts[li]:
                stack.append((li, 1))
                li = children[li, 1]
            else:
                stack.append((ri, 0))
                ri = children[ri, 0]

        i = li if li != -1 else ri
        while stack:
            pi, is_right = stack.pop()
            children[pi, is_right] = i
            counts[pi] = counts[children[pi, 0]] + counts[children[pi, 1]] + 1
            i = pi

        return i

    def rbst_split(children, values, counts, root, x):
        i = root
        l_stack = []
        r_stack = []
        while i != -1:
            if x < values[i]:
                r_stack.append(i)
                i = children[i, 0]
            else:
                l_stack.append(i)
                i = children[i, 1]

        li, ri = -1, -1
        while l_stack:
            pi = l_stack.pop()
            children[pi, 1] = li
            counts[pi] = counts[children[pi, 0]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            children[pi, 0] = ri
            counts[pi] = counts[ri] + counts[children[pi, 1]] + 1
            ri = pi

        return li, ri

    # ↓この関数の定義時点でREがでてる

    def rbst_insert(children, values, counts, indices, root, x):
        ni = indices.pop()
        children[ni, 0] = children[ni, 1] = -1
        values[ni] = x
        counts[ni] = 1

        li, ri = rbst_split(children, values, counts, root, x)
        i = rbst_merge(children, counts, li, ni)
        i = rbst_merge(children, counts, i, ri)

        return i

    return inp

    def rbst_delete(children, values, counts, indices, root, x):
        li, mri = rbst_split(children, values, counts, root, x - 1)
        mi, ri = rbst_split(children, values, counts, mri, x)
        # print('delete', x, root, li, mi, ri)

        if mi == -1:
            return rbst_merge(children, counts, li, ri)

        if counts[mi] == 1:
            indices.add(mi)
            return rbst_merge(children, counts, li, ri)

        i = mi
        stack = []
        while i != -1:
            if children[i, 0] != -1 and children[i, 1] != -1:
                to_right = 1 if counts[children[i, 0]] < counts[children[i, 1]] else 0
                stack.append((i, to_right))
                i = children[i, to_right]
            else:
                if children[i, 0] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 0]
                    else:
                        mi = children[i, 0]
                elif children[i, 1] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 1]
                    else:
                        mi = children[i, 1]
                else:
                    pi, is_right = stack[-1]
                    children[pi, is_right] = -1
                break

        indices.add(i)
        while stack:
            pi, _ = stack.pop()
            counts[pi] -= 1

        i = rbst_merge(children, counts, li, mi)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_upper_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x < values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_lower_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x <= values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_get_k_th(children, values, counts, default, root, k):
        i = root
        if counts[i] <= k:
            return default
        j = k
        while i != -1:
            left_count = counts[children[i, 0]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[i, 0]
            else:
                j -= left_count + 1
                i = children[i, 1]
        return default

    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    rbst_size = w + 10
    rbst1_indices = set(range(rbst_size - 1))
    rbst1_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst1_values = np.zeros(rbst_size, dtype=np.int64)
    rbst1_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst1_root = -1
    rbst2_indices = set(range(rbst_size - 1))
    rbst2_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst2_values = np.zeros(rbst_size, dtype=np.int64)
    rbst2_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst2_root = -1
    INF = 10 ** 18

    for i in range(1, w + 1):
        rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, i)
        rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, 0)
    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, INF)
    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, INF)
    # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)

    moves = np.zeros(w + 1, dtype=np.int64)
    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, a)
        stack = []
        while c <= b + 1:
            stack.append(c)
            c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, c + 1)

        if len(stack) == 0:
            ans[row] = row + 1 + rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
            continue

        found_nearest = b == w

        while stack:
            c = stack.pop()
            if found_nearest:
                rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                         moves[c])
            else:
                if c < b + 1:
                    rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root,
                                             b + 1)
                    rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c])
                    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c] + b + 1 - c)
                    moves[b + 1] = moves[c] + b + 1 - c

                found_nearest = True

        # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)
        # debug_print(rbst2_children, rbst2_values, rbst2_counts, rbst2_root)

        move = rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
        if move == INF:
            break

        ans[row] = row + move + 1

    return ans


def debug_print(children, values, counts, root):
    print(children.T)
    print(values)
    print(counts)
    _debug_print(children, values, counts, root, 0)


def _debug_print(children, values, counts, i, depth):
    if i != -1:
        _debug_print(children, values, counts, children[i, 0], depth + 1)
        print('      ' * depth, values[i], counts[i])
        _debug_print(children, values, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def rbst_merge(children, counts, left_root, right_root):
        li = left_root
        ri = right_root
        stack = []
        while li != -1 and ri != -1:
            if np.random.randint(counts[li] + counts[ri]) < counts[li]:
                stack.append((li, 1))
                li = children[li, 1]
            else:
                stack.append((ri, 0))
                ri = children[ri, 0]

        i = li if li != -1 else ri
        while stack:
            pi, is_right = stack.pop()
            children[pi, is_right] = i
            counts[pi] = counts[children[pi, 0]] + counts[children[pi, 1]] + 1
            i = pi

        return i

    def rbst_split(children, values, counts, root, x):
        i = root
        l_stack = []
        r_stack = []
        while i != -1:
            if x < values[i]:
                r_stack.append(i)
                i = children[i, 0]
            else:
                l_stack.append(i)
                i = children[i, 1]

        li, ri = -1, -1
        while l_stack:
            pi = l_stack.pop()
            children[pi, 1] = li
            counts[pi] = counts[children[pi, 0]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            children[pi, 0] = ri
            counts[pi] = counts[ri] + counts[children[pi, 1]] + 1
            ri = pi

        return li, ri

    def rbst_delete(children, values, counts, indices, root, x):
        li, mri = rbst_split(children, values, counts, root, x - 1)
        mi, ri = rbst_split(children, values, counts, mri, x)
        # print('delete', x, root, li, mi, ri)

        if mi == -1:
            return rbst_merge(children, counts, li, ri)

        if counts[mi] == 1:
            indices.add(mi)
            return rbst_merge(children, counts, li, ri)

        i = mi
        stack = []
        while i != -1:
            if children[i, 0] != -1 and children[i, 1] != -1:
                to_right = 1 if counts[children[i, 0]] < counts[children[i, 1]] else 0
                stack.append((i, to_right))
                i = children[i, to_right]
            else:
                if children[i, 0] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 0]
                    else:
                        mi = children[i, 0]
                elif children[i, 1] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 1]
                    else:
                        mi = children[i, 1]
                else:
                    pi, is_right = stack[-1]
                    children[pi, is_right] = -1
                break

        indices.add(i)
        while stack:
            pi, _ = stack.pop()
            counts[pi] -= 1

        i = rbst_merge(children, counts, li, mi)
        i = rbst_merge(children, counts, i, ri)

        return i

    return inp

    # ↓この関数でREがでてる

    def rbst_insert(children, values, counts, indices, root, x):
        ni = indices.pop()
        children[ni, 0] = children[ni, 1] = -1
        values[ni] = x
        counts[ni] = 1

        li, ri = rbst_split(children, values, counts, root, x)
        i = rbst_merge(children, counts, li, ni)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_upper_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x < values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_lower_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x <= values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_get_k_th(children, values, counts, default, root, k):
        i = root
        if counts[i] <= k:
            return default
        j = k
        while i != -1:
            left_count = counts[children[i, 0]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[i, 0]
            else:
                j -= left_count + 1
                i = children[i, 1]
        return default

    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    rbst_size = w + 10
    rbst1_indices = set(range(rbst_size - 1))
    rbst1_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst1_values = np.zeros(rbst_size, dtype=np.int64)
    rbst1_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst1_root = -1
    rbst2_indices = set(range(rbst_size - 1))
    rbst2_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst2_values = np.zeros(rbst_size, dtype=np.int64)
    rbst2_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst2_root = -1
    INF = 10 ** 18

    for i in range(1, w + 1):
        rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, i)
        rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, 0)
    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, INF)
    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, INF)
    # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)

    moves = np.zeros(w + 1, dtype=np.int64)
    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, a)
        stack = []
        while c <= b + 1:
            stack.append(c)
            c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, c + 1)

        if len(stack) == 0:
            ans[row] = row + 1 + rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
            continue

        found_nearest = b == w

        while stack:
            c = stack.pop()
            if found_nearest:
                rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                         moves[c])
            else:
                if c < b + 1:
                    rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root,
                                             b + 1)
                    rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c])
                    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c] + b + 1 - c)
                    moves[b + 1] = moves[c] + b + 1 - c

                found_nearest = True

        # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)
        # debug_print(rbst2_children, rbst2_values, rbst2_counts, rbst2_root)

        move = rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
        if move == INF:
            break

        ans[row] = row + move + 1

    return ans


def debug_print(children, values, counts, root):
    print(children.T)
    print(values)
    print(counts)
    _debug_print(children, values, counts, root, 0)


def _debug_print(children, values, counts, i, depth):
    if i != -1:
        _debug_print(children, values, counts, children[i, 0], depth + 1)
        print('      ' * depth, values[i], counts[i])
        _debug_print(children, values, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def rbst_merge(children, counts, left_root, right_root):
        li = left_root
        ri = right_root
        stack = []
        while li != -1 and ri != -1:
            if np.random.randint(counts[li] + counts[ri]) < counts[li]:
                stack.append((li, 1))
                li = children[li, 1]
            else:
                stack.append((ri, 0))
                ri = children[ri, 0]

        i = li if li != -1 else ri
        while stack:
            pi, is_right = stack.pop()
            children[pi, is_right] = i
            counts[pi] = counts[children[pi, 0]] + counts[children[pi, 1]] + 1
            i = pi

        return i

    def rbst_split(children, values, counts, root, x):
        i = root
        l_stack = []
        r_stack = []
        while i != -1:
            if x < values[i]:
                r_stack.append(i)
                i = children[i, 0]
            else:
                l_stack.append(i)
                i = children[i, 1]

        li, ri = -1, -1
        while l_stack:
            pi = l_stack.pop()
            children[pi, 1] = li
            counts[pi] = counts[children[pi, 0]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            children[pi, 0] = ri
            counts[pi] = counts[ri] + counts[children[pi, 1]] + 1
            ri = pi

        return li, ri

    # ↓この関数でREがでてる

    def rbst_insert(children, values, counts, indices, root, x):
        if len(indices) == 0:
            print('WA')
            exit()
        ni = indices.pop()
        children[ni, 0] = children[ni, 1] = -1
        values[ni] = x
        counts[ni] = 1

        li, ri = rbst_split(children, values, counts, root, x)
        i = rbst_merge(children, counts, li, ni)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_delete(children, values, counts, indices, root, x):
        li, mri = rbst_split(children, values, counts, root, x - 1)
        mi, ri = rbst_split(children, values, counts, mri, x)
        # print('delete', x, root, li, mi, ri)

        if mi == -1:
            return rbst_merge(children, counts, li, ri)

        if counts[mi] == 1:
            indices.add(mi)
            return rbst_merge(children, counts, li, ri)

        i = mi
        stack = []
        while i != -1:
            if children[i, 0] != -1 and children[i, 1] != -1:
                to_right = 1 if counts[children[i, 0]] < counts[children[i, 1]] else 0
                stack.append((i, to_right))
                i = children[i, to_right]
            else:
                if children[i, 0] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 0]
                    else:
                        mi = children[i, 0]
                elif children[i, 1] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 1]
                    else:
                        mi = children[i, 1]
                else:
                    pi, is_right = stack[-1]
                    children[pi, is_right] = -1
                break

        indices.add(i)
        while stack:
            pi, _ = stack.pop()
            counts[pi] -= 1

        i = rbst_merge(children, counts, li, mi)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_upper_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x < values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_lower_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x <= values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_get_k_th(children, values, counts, default, root, k):
        i = root
        if counts[i] <= k:
            return default
        j = k
        while i != -1:
            left_count = counts[children[i, 0]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[i, 0]
            else:
                j -= left_count + 1
                i = children[i, 1]
        return default

    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    rbst_size = w + 10
    rbst1_indices = set(range(rbst_size - 1))
    rbst1_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst1_values = np.zeros(rbst_size, dtype=np.int64)
    rbst1_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst1_root = -1
    rbst2_indices = set(range(rbst_size - 1))
    rbst2_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst2_values = np.zeros(rbst_size, dtype=np.int64)
    rbst2_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst2_root = -1
    INF = 10 ** 18

    for i in range(1, w + 1):
        rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, i)
        rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, 0)
    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, INF)
    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, INF)
    # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)

    moves = np.zeros(w + 1, dtype=np.int64)
    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, a)
        stack = []
        while c <= b + 1:
            stack.append(c)
            c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, c + 1)

        if len(stack) == 0:
            ans[row] = row + 1 + rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
            continue

        found_nearest = b == w

        while stack:
            c = stack.pop()
            if found_nearest:
                rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                         moves[c])
            else:
                if c < b + 1:
                    rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root,
                                             b + 1)
                    rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c])
                    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c] + b + 1 - c)
                    moves[b + 1] = moves[c] + b + 1 - c

                found_nearest = True

        # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)
        # debug_print(rbst2_children, rbst2_values, rbst2_counts, rbst2_root)

        move = rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
        if move == INF:
            break

        ans[row] = row + move + 1

    return ans


def debug_print(children, values, counts, root):
    print(children.T)
    print(values)
    print(counts)
    _debug_print(children, values, counts, root, 0)


def _debug_print(children, values, counts, i, depth):
    if i != -1:
        _debug_print(children, values, counts, children[i, 0], depth + 1)
        print('      ' * depth, values[i], counts[i])
        _debug_print(children, values, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def rbst_merge(children, counts, left_root, right_root):
        li = left_root
        ri = right_root
        stack = []
        while li != -1 and ri != -1:
            if np.random.randint(counts[li] + counts[ri]) < counts[li]:
                stack.append((li, 1))
                li = children[li, 1]
            else:
                stack.append((ri, 0))
                ri = children[ri, 0]

        i = li if li != -1 else ri
        while stack:
            pi, is_right = stack.pop()
            children[pi, is_right] = i
            counts[pi] = counts[children[pi, 0]] + counts[children[pi, 1]] + 1
            i = pi

        return i

    def rbst_split(children, values, counts, root, x):
        i = root
        l_stack = []
        r_stack = []
        while i != -1:
            if x < values[i]:
                r_stack.append(i)
                i = children[i, 0]
            else:
                l_stack.append(i)
                i = children[i, 1]

        li, ri = -1, -1
        while l_stack:
            pi = l_stack.pop()
            children[pi, 1] = li
            counts[pi] = counts[children[pi, 0]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            children[pi, 0] = ri
            counts[pi] = counts[ri] + counts[children[pi, 1]] + 1
            ri = pi

        return li, ri

    def rbst_insert(children, values, counts, indices, root, x):
        ni = indices.pop()
        children[ni, 0] = children[ni, 1] = -1
        values[ni] = x
        counts[ni] = 1
        # print('insert', x, root, ni)

        li, ri = rbst_split(children, values, counts, root, x)
        i = rbst_merge(children, counts, li, ni)
        i = rbst_merge(children, counts, i, ri)

        return i
   
    return inp

    def rbst_delete(children, values, counts, indices, root, x):
        li, mri = rbst_split(children, values, counts, root, x - 1)
        mi, ri = rbst_split(children, values, counts, mri, x)
        # print('delete', x, root, li, mi, ri)

        if mi == -1:
            return rbst_merge(children, counts, li, ri)

        if counts[mi] == 1:
            indices.add(mi)
            return rbst_merge(children, counts, li, ri)

        i = mi
        stack = []
        while i != -1:
            if children[i, 0] != -1 and children[i, 1] != -1:
                to_right = 1 if counts[children[i, 0]] < counts[children[i, 1]] else 0
                stack.append((i, to_right))
                i = children[i, to_right]
            else:
                if children[i, 0] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 0]
                    else:
                        mi = children[i, 0]
                elif children[i, 1] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 1]
                    else:
                        mi = children[i, 1]
                else:
                    pi, is_right = stack[-1]
                    children[pi, is_right] = -1
                break

        indices.add(i)
        while stack:
            pi, _ = stack.pop()
            counts[pi] -= 1

        i = rbst_merge(children, counts, li, mi)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_upper_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x < values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_lower_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x <= values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_get_k_th(children, values, counts, default, root, k):
        i = root
        if counts[i] <= k:
            return default
        j = k
        while i != -1:
            left_count = counts[children[i, 0]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[i, 0]
            else:
                j -= left_count + 1
                i = children[i, 1]
        return default

    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    rbst_size = w + 10
    rbst1_indices = set(range(rbst_size - 1))
    rbst1_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst1_values = np.zeros(rbst_size, dtype=np.int64)
    rbst1_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst1_root = -1
    rbst2_indices = set(range(rbst_size - 1))
    rbst2_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst2_values = np.zeros(rbst_size, dtype=np.int64)
    rbst2_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst2_root = -1
    INF = 10 ** 18

    for i in range(1, w + 1):
        rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, i)
        rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, 0)
    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, INF)
    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, INF)
    # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)

    moves = np.zeros(w + 1, dtype=np.int64)
    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, a)
        stack = []
        while c <= b + 1:
            stack.append(c)
            c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, c + 1)

        if len(stack) == 0:
            ans[row] = row + 1 + rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
            continue

        found_nearest = b == w

        while stack:
            c = stack.pop()
            if found_nearest:
                rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                         moves[c])
            else:
                if c < b + 1:
                    rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root,
                                             b + 1)
                    rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c])
                    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c] + b + 1 - c)
                    moves[b + 1] = moves[c] + b + 1 - c

                found_nearest = True

        # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)
        # debug_print(rbst2_children, rbst2_values, rbst2_counts, rbst2_root)

        move = rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
        if move == INF:
            break

        ans[row] = row + move + 1

    return ans


def debug_print(children, values, counts, root):
    print(children.T)
    print(values)
    print(counts)
    _debug_print(children, values, counts, root, 0)


def _debug_print(children, values, counts, i, depth):
    if i != -1:
        _debug_print(children, values, counts, children[i, 0], depth + 1)
        print('      ' * depth, values[i], counts[i])
        _debug_print(children, values, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def rbst_merge(children, counts, left_root, right_root):
        li = left_root
        ri = right_root
        stack = []
        while li != -1 and ri != -1:
            if np.random.randint(counts[li] + counts[ri]) < counts[li]:
                stack.append((li, 1))
                li = children[li, 1]
            else:
                stack.append((ri, 0))
                ri = children[ri, 0]

        i = li if li != -1 else ri
        while stack:
            pi, is_right = stack.pop()
            children[pi, is_right] = i
            counts[pi] = counts[children[pi, 0]] + counts[children[pi, 1]] + 1
            i = pi

        return i

    def rbst_split(children, values, counts, root, x):
        i = root
        l_stack = []
        r_stack = []
        while i != -1:
            if x < values[i]:
                r_stack.append(i)
                i = children[i, 0]
            else:
                l_stack.append(i)
                i = children[i, 1]

        li, ri = -1, -1
        while l_stack:
            pi = l_stack.pop()
            children[pi, 1] = li
            counts[pi] = counts[children[pi, 0]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            children[pi, 0] = ri
            counts[pi] = counts[ri] + counts[children[pi, 1]] + 1
            ri = pi

        return li, ri

    def rbst_insert(children, values, counts, indices, root, x):
        ni = indices.pop()
        children[ni, 0] = children[ni, 1] = -1
        values[ni] = x
        counts[ni] = 1
        # print('insert', x, root, ni)

        li, ri = rbst_split(children, values, counts, root, x)
        i = rbst_merge(children, counts, li, ni)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_delete(children, values, counts, indices, root, x):
        li, mri = rbst_split(children, values, counts, root, x - 1)
        mi, ri = rbst_split(children, values, counts, mri, x)
        # print('delete', x, root, li, mi, ri)

        if mi == -1:
            return rbst_merge(children, counts, li, ri)

        if counts[mi] == 1:
            indices.add(mi)
            return rbst_merge(children, counts, li, ri)

        i = mi
        stack = []
        while i != -1:
            if children[i, 0] != -1 and children[i, 1] != -1:
                to_right = 1 if counts[children[i, 0]] < counts[children[i, 1]] else 0
                stack.append((i, to_right))
                i = children[i, to_right]
            else:
                if children[i, 0] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 0]
                    else:
                        mi = children[i, 0]
                elif children[i, 1] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 1]
                    else:
                        mi = children[i, 1]
                else:
                    pi, is_right = stack[-1]
                    children[pi, is_right] = -1
                break

        indices.add(i)
        while stack:
            pi, _ = stack.pop()
            counts[pi] -= 1

        i = rbst_merge(children, counts, li, mi)
        i = rbst_merge(children, counts, i, ri)

        return i
    
    return inp

    def rbst_upper_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x < values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_lower_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x <= values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_get_k_th(children, values, counts, default, root, k):
        i = root
        if counts[i] <= k:
            return default
        j = k
        while i != -1:
            left_count = counts[children[i, 0]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[i, 0]
            else:
                j -= left_count + 1
                i = children[i, 1]
        return default

    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    rbst_size = w + 10
    rbst1_indices = set(range(rbst_size - 1))
    rbst1_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst1_values = np.zeros(rbst_size, dtype=np.int64)
    rbst1_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst1_root = -1
    rbst2_indices = set(range(rbst_size - 1))
    rbst2_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst2_values = np.zeros(rbst_size, dtype=np.int64)
    rbst2_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst2_root = -1
    INF = 10 ** 18

    for i in range(1, w + 1):
        rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, i)
        rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, 0)
    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, INF)
    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, INF)
    # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)

    moves = np.zeros(w + 1, dtype=np.int64)
    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, a)
        stack = []
        while c <= b + 1:
            stack.append(c)
            c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, c + 1)

        if len(stack) == 0:
            ans[row] = row + 1 + rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
            continue

        found_nearest = b == w

        while stack:
            c = stack.pop()
            if found_nearest:
                rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                         moves[c])
            else:
                if c < b + 1:
                    rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root,
                                             b + 1)
                    rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c])
                    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c] + b + 1 - c)
                    moves[b + 1] = moves[c] + b + 1 - c

                found_nearest = True

        # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)
        # debug_print(rbst2_children, rbst2_values, rbst2_counts, rbst2_root)

        move = rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
        if move == INF:
            break

        ans[row] = row + move + 1

    return ans


def debug_print(children, values, counts, root):
    print(children.T)
    print(values)
    print(counts)
    _debug_print(children, values, counts, root, 0)


def _debug_print(children, values, counts, i, depth):
    if i != -1:
        _debug_print(children, values, counts, children[i, 0], depth + 1)
        print('      ' * depth, values[i], counts[i])
        _debug_print(children, values, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def rbst_merge(children, counts, left_root, right_root):
        li = left_root
        ri = right_root
        stack = []
        while li != -1 and ri != -1:
            if np.random.randint(counts[li] + counts[ri]) < counts[li]:
                stack.append((li, 1))
                li = children[li, 1]
            else:
                stack.append((ri, 0))
                ri = children[ri, 0]

        i = li if li != -1 else ri
        while stack:
            pi, is_right = stack.pop()
            children[pi, is_right] = i
            counts[pi] = counts[children[pi, 0]] + counts[children[pi, 1]] + 1
            i = pi

        return i

    def rbst_split(children, values, counts, root, x):
        i = root
        l_stack = []
        r_stack = []
        while i != -1:
            if x < values[i]:
                r_stack.append(i)
                i = children[i, 0]
            else:
                l_stack.append(i)
                i = children[i, 1]

        li, ri = -1, -1
        while l_stack:
            pi = l_stack.pop()
            children[pi, 1] = li
            counts[pi] = counts[children[pi, 0]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            children[pi, 0] = ri
            counts[pi] = counts[ri] + counts[children[pi, 1]] + 1
            ri = pi

        return li, ri

    def rbst_insert(children, values, counts, indices, root, x):
        ni = indices.pop()
        children[ni, 0] = children[ni, 1] = -1
        values[ni] = x
        counts[ni] = 1
        # print('insert', x, root, ni)

        li, ri = rbst_split(children, values, counts, root, x)
        i = rbst_merge(children, counts, li, ni)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_delete(children, values, counts, indices, root, x):
        li, mri = rbst_split(children, values, counts, root, x - 1)
        mi, ri = rbst_split(children, values, counts, mri, x)
        # print('delete', x, root, li, mi, ri)

        if mi == -1:
            return rbst_merge(children, counts, li, ri)

        if counts[mi] == 1:
            indices.add(mi)
            return rbst_merge(children, counts, li, ri)

        i = mi
        stack = []
        while i != -1:
            if children[i, 0] != -1 and children[i, 1] != -1:
                to_right = 1 if counts[children[i, 0]] < counts[children[i, 1]] else 0
                stack.append((i, to_right))
                i = children[i, to_right]
            else:
                if children[i, 0] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 0]
                    else:
                        mi = children[i, 0]
                elif children[i, 1] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 1]
                    else:
                        mi = children[i, 1]
                else:
                    pi, is_right = stack[-1]
                    children[pi, is_right] = -1
                break

        indices.add(i)
        while stack:
            pi, _ = stack.pop()
            counts[pi] -= 1

        i = rbst_merge(children, counts, li, mi)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_upper_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x < values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_lower_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x <= values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_get_k_th(children, values, counts, default, root, k):
        i = root
        if counts[i] <= k:
            return default
        j = k
        while i != -1:
            left_count = counts[children[i, 0]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[i, 0]
            else:
                j -= left_count + 1
                i = children[i, 1]
        return default

    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    return aaa

    rbst_size = w + 10
    rbst1_indices = set(range(rbst_size - 1))
    rbst1_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst1_values = np.zeros(rbst_size, dtype=np.int64)
    rbst1_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst1_root = -1
    rbst2_indices = set(range(rbst_size - 1))
    rbst2_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst2_values = np.zeros(rbst_size, dtype=np.int64)
    rbst2_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst2_root = -1
    INF = 10 ** 18

    for i in range(1, w + 1):
        rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, i)
        rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, 0)
    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, INF)
    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, INF)
    # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)

    moves = np.zeros(w + 1, dtype=np.int64)
    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, a)
        stack = []
        while c <= b + 1:
            stack.append(c)
            c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, c + 1)

        if len(stack) == 0:
            ans[row] = row + 1 + rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
            continue

        found_nearest = b == w

        while stack:
            c = stack.pop()
            if found_nearest:
                rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                         moves[c])
            else:
                if c < b + 1:
                    rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root,
                                             b + 1)
                    rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c])
                    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c] + b + 1 - c)
                    moves[b + 1] = moves[c] + b + 1 - c

                found_nearest = True

        # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)
        # debug_print(rbst2_children, rbst2_values, rbst2_counts, rbst2_root)

        move = rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
        if move == INF:
            break

        ans[row] = row + move + 1

    return ans


def debug_print(children, values, counts, root):
    print(children.T)
    print(values)
    print(counts)
    _debug_print(children, values, counts, root, 0)


def _debug_print(children, values, counts, i, depth):
    if i != -1:
        _debug_print(children, values, counts, children[i, 0], depth + 1)
        print('      ' * depth, values[i], counts[i])
        _debug_print(children, values, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def rbst_merge(children, counts, left_root, right_root):
        li = left_root
        ri = right_root
        stack = []
        while li != -1 and ri != -1:
            if np.random.randint(counts[li] + counts[ri]) < counts[li]:
                stack.append((li, 1))
                li = children[li, 1]
            else:
                stack.append((ri, 0))
                ri = children[ri, 0]

        i = li if li != -1 else ri
        while stack:
            pi, is_right = stack.pop()
            children[pi, is_right] = i
            counts[pi] = counts[children[pi, 0]] + counts[children[pi, 1]] + 1
            i = pi

        return i

    def rbst_split(children, values, counts, root, x):
        i = root
        l_stack = []
        r_stack = []
        while i != -1:
            if x < values[i]:
                r_stack.append(i)
                i = children[i, 0]
            else:
                l_stack.append(i)
                i = children[i, 1]

        li, ri = -1, -1
        while l_stack:
            pi = l_stack.pop()
            children[pi, 1] = li
            counts[pi] = counts[children[pi, 0]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            children[pi, 0] = ri
            counts[pi] = counts[ri] + counts[children[pi, 1]] + 1
            ri = pi

        return li, ri

    def rbst_insert(children, values, counts, indices, root, x):
        ni = indices.pop()
        children[ni, 0] = children[ni, 1] = -1
        values[ni] = x
        counts[ni] = 1
        # print('insert', x, root, ni)

        li, ri = rbst_split(children, values, counts, root, x)
        i = rbst_merge(children, counts, li, ni)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_delete(children, values, counts, indices, root, x):
        li, mri = rbst_split(children, values, counts, root, x - 1)
        mi, ri = rbst_split(children, values, counts, mri, x)
        # print('delete', x, root, li, mi, ri)

        if mi == -1:
            return rbst_merge(children, counts, li, ri)

        if counts[mi] == 1:
            indices.add(mi)
            return rbst_merge(children, counts, li, ri)

        i = mi
        stack = []
        while i != -1:
            if children[i, 0] != -1 and children[i, 1] != -1:
                to_right = 1 if counts[children[i, 0]] < counts[children[i, 1]] else 0
                stack.append((i, to_right))
                i = children[i, to_right]
            else:
                if children[i, 0] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 0]
                    else:
                        mi = children[i, 0]
                elif children[i, 1] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 1]
                    else:
                        mi = children[i, 1]
                else:
                    pi, is_right = stack[-1]
                    children[pi, is_right] = -1
                break

        indices.add(i)
        while stack:
            pi, _ = stack.pop()
            counts[pi] -= 1

        i = rbst_merge(children, counts, li, mi)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_upper_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x < values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_lower_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x <= values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_get_k_th(children, values, counts, default, root, k):
        i = root
        if counts[i] <= k:
            return default
        j = k
        while i != -1:
            left_count = counts[children[i, 0]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[i, 0]
            else:
                j -= left_count + 1
                i = children[i, 1]
        return default

    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    rbst_size = w + 10
    rbst1_indices = set(range(rbst_size - 1))
    rbst1_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst1_values = np.zeros(rbst_size, dtype=np.int64)
    rbst1_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst1_root = -1
    rbst2_indices = set(range(rbst_size - 1))
    rbst2_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst2_values = np.zeros(rbst_size, dtype=np.int64)
    rbst2_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst2_root = -1
    INF = 10 ** 18

    return 0

    for i in range(1, w + 1):
        rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, i)
        rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, 0)
    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, INF)
    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, INF)
    # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)

    moves = np.zeros(w + 1, dtype=np.int64)
    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, a)
        stack = []
        while c <= b + 1:
            stack.append(c)
            c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, c + 1)

        if len(stack) == 0:
            ans[row] = row + 1 + rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
            continue

        found_nearest = b == w

        while stack:
            c = stack.pop()
            if found_nearest:
                rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                         moves[c])
            else:
                if c < b + 1:
                    rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root,
                                             b + 1)
                    rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c])
                    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c] + b + 1 - c)
                    moves[b + 1] = moves[c] + b + 1 - c

                found_nearest = True

        # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)
        # debug_print(rbst2_children, rbst2_values, rbst2_counts, rbst2_root)

        move = rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
        if move == INF:
            break

        ans[row] = row + move + 1

    return ans


def debug_print(children, values, counts, root):
    print(children.T)
    print(values)
    print(counts)
    _debug_print(children, values, counts, root, 0)


def _debug_print(children, values, counts, i, depth):
    if i != -1:
        _debug_print(children, values, counts, children[i, 0], depth + 1)
        print('      ' * depth, values[i], counts[i])
        _debug_print(children, values, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def rbst_merge(children, counts, left_root, right_root):
        li = left_root
        ri = right_root
        stack = []
        while li != -1 and ri != -1:
            if np.random.randint(counts[li] + counts[ri]) < counts[li]:
                stack.append((li, 1))
                li = children[li, 1]
            else:
                stack.append((ri, 0))
                ri = children[ri, 0]

        i = li if li != -1 else ri
        while stack:
            pi, is_right = stack.pop()
            children[pi, is_right] = i
            counts[pi] = counts[children[pi, 0]] + counts[children[pi, 1]] + 1
            i = pi

        return i

    def rbst_split(children, values, counts, root, x):
        i = root
        l_stack = []
        r_stack = []
        while i != -1:
            if x < values[i]:
                r_stack.append(i)
                i = children[i, 0]
            else:
                l_stack.append(i)
                i = children[i, 1]

        li, ri = -1, -1
        while l_stack:
            pi = l_stack.pop()
            children[pi, 1] = li
            counts[pi] = counts[children[pi, 0]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            children[pi, 0] = ri
            counts[pi] = counts[ri] + counts[children[pi, 1]] + 1
            ri = pi

        return li, ri

    def rbst_insert(children, values, counts, indices, root, x):
        ni = indices.pop()
        children[ni, 0] = children[ni, 1] = -1
        values[ni] = x
        counts[ni] = 1
        # print('insert', x, root, ni)

        li, ri = rbst_split(children, values, counts, root, x)
        i = rbst_merge(children, counts, li, ni)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_delete(children, values, counts, indices, root, x):
        li, mri = rbst_split(children, values, counts, root, x - 1)
        mi, ri = rbst_split(children, values, counts, mri, x)
        # print('delete', x, root, li, mi, ri)

        if mi == -1:
            return rbst_merge(children, counts, li, ri)

        if counts[mi] == 1:
            indices.add(mi)
            return rbst_merge(children, counts, li, ri)

        i = mi
        stack = []
        while i != -1:
            if children[i, 0] != -1 and children[i, 1] != -1:
                to_right = 1 if counts[children[i, 0]] < counts[children[i, 1]] else 0
                stack.append((i, to_right))
                i = children[i, to_right]
            else:
                if children[i, 0] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 0]
                    else:
                        mi = children[i, 0]
                elif children[i, 1] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 1]
                    else:
                        mi = children[i, 1]
                else:
                    pi, is_right = stack[-1]
                    children[pi, is_right] = -1
                break

        indices.add(i)
        while stack:
            pi, _ = stack.pop()
            counts[pi] -= 1

        i = rbst_merge(children, counts, li, mi)
        i = rbst_merge(children, counts, i, ri)

        return i

    # def rbst_upper_bound(children, values, counts, default, root, x):
    #     i = root
    #     y = default
    #     c = counts[i]
    #     j = 0
    #     while i != -1:
    #         if x < values[i]:
    #             y = values[i]
    #             c = j + counts[children[i, 0]]
    #             i = children[i, 0]
    #         else:
    #             j += counts[children[i, 0]] + 1
    #             i = children[i, 1]
    #     return y, c

    def rbst_lower_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x <= values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_get_k_th(children, values, counts, default, root, k):
        i = root
        if counts[i] <= k:
            return default
        j = k
        while i != -1:
            left_count = counts[children[i, 0]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[i, 0]
            else:
                j -= left_count + 1
                i = children[i, 1]
        return default

    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    rbst_size = w + 10
    rbst1_indices = set(range(rbst_size - 1))
    rbst1_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst1_values = np.zeros(rbst_size, dtype=np.int64)
    rbst1_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst1_root = -1
    rbst2_indices = set(range(rbst_size - 1))
    rbst2_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst2_values = np.zeros(rbst_size, dtype=np.int64)
    rbst2_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst2_root = -1
    INF = 10 ** 18

    for i in range(1, w + 1):
        rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, i)
        rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, 0)
    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, INF)
    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, INF)
    # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)

    moves = np.zeros(w + 1, dtype=np.int64)
    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, a)
        stack = []
        while c <= b + 1:
            stack.append(c)
            c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, c + 1)

        if len(stack) == 0:
            ans[row] = row + 1 + rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
            continue

        found_nearest = b == w

        while stack:
            c = stack.pop()
            if found_nearest:
                rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                         moves[c])
            else:
                if c < b + 1:
                    rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root,
                                             b + 1)
                    rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c])
                    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c] + b + 1 - c)
                    moves[b + 1] = moves[c] + b + 1 - c

                found_nearest = True

        # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)
        # debug_print(rbst2_children, rbst2_values, rbst2_counts, rbst2_root)

        move = rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
        if move == INF:
            break

        ans[row] = row + move + 1

    return ans


def debug_print(children, values, counts, root):
    print(children.T)
    print(values)
    print(counts)
    _debug_print(children, values, counts, root, 0)


def _debug_print(children, values, counts, i, depth):
    if i != -1:
        _debug_print(children, values, counts, children[i, 0], depth + 1)
        print('      ' * depth, values[i], counts[i])
        _debug_print(children, values, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def rbst_merge(children, counts, left_root, right_root):
        li = left_root
        ri = right_root
        stack = []
        while li != -1 and ri != -1:
            if np.random.randint(counts[li] + counts[ri]) < counts[li]:
                stack.append((li, 1))
                li = children[li, 1]
            else:
                stack.append((ri, 0))
                ri = children[ri, 0]

        i = li if li != -1 else ri
        while stack:
            pi, is_right = stack.pop()
            children[pi, is_right] = i
            counts[pi] = counts[children[pi, 0]] + counts[children[pi, 1]] + 1
            i = pi

        return i

    def rbst_split(children, values, counts, root, x):
        i = root
        l_stack = []
        r_stack = []
        while i != -1:
            if x < values[i]:
                r_stack.append(i)
                i = children[i, 0]
            else:
                l_stack.append(i)
                i = children[i, 1]

        li, ri = -1, -1
        while l_stack:
            pi = l_stack.pop()
            children[pi, 1] = li
            counts[pi] = counts[children[pi, 0]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            children[pi, 0] = ri
            counts[pi] = counts[ri] + counts[children[pi, 1]] + 1
            ri = pi

        return li, ri

    def rbst_insert(children, values, counts, indices, root, x):
        ni = indices.pop()
        children[ni, 0] = children[ni, 1] = -1
        values[ni] = x
        counts[ni] = 1
        # print('insert', x, root, ni)

        li, ri = rbst_split(children, values, counts, root, x)
        i = rbst_merge(children, counts, li, ni)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_delete(children, values, counts, indices, root, x):
        li, mri = rbst_split(children, values, counts, root, x - 1)
        mi, ri = rbst_split(children, values, counts, mri, x)
        # print('delete', x, root, li, mi, ri)

        if mi == -1:
            return rbst_merge(children, counts, li, ri)

        if counts[mi] == 1:
            indices.add(mi)
            return rbst_merge(children, counts, li, ri)

        i = mi
        stack = []
        while i != -1:
            if children[i, 0] != -1 and children[i, 1] != -1:
                to_right = 1 if counts[children[i, 0]] < counts[children[i, 1]] else 0
                stack.append((i, to_right))
                i = children[i, to_right]
            else:
                if children[i, 0] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 0]
                    else:
                        mi = children[i, 0]
                elif children[i, 1] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[pi, is_right] = children[i, 1]
                    else:
                        mi = children[i, 1]
                else:
                    pi, is_right = stack[-1]
                    children[pi, is_right] = -1
                break

        indices.add(i)
        while stack:
            pi, _ = stack.pop()
            counts[pi] -= 1

        i = rbst_merge(children, counts, li, mi)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_upper_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x < values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_lower_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x <= values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_get_k_th(children, values, counts, default, root, k):
        i = root
        if counts[i] <= k:
            return default
        j = k
        while i != -1:
            left_count = counts[children[i, 0]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[i, 0]
            else:
                j -= left_count + 1
                i = children[i, 1]
        return default

    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    rbst_size = w + 10
    rbst1_indices = set(range(rbst_size - 1))
    rbst1_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst1_values = np.zeros(rbst_size, dtype=np.int64)
    rbst1_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst1_root = -1
    rbst2_indices = set(range(rbst_size - 1))
    rbst2_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst2_values = np.zeros(rbst_size, dtype=np.int64)
    rbst2_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst2_root = -1
    INF = 10 ** 18

    for i in range(1, w + 1):
        rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, i)
        rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, 0)
    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, INF)
    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, INF)
    # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)

    moves = np.zeros(w + 1, dtype=np.int64)
    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, a)
        stack = []
        while c <= b + 1:
            stack.append(c)
            c, _ = rbst_lower_bound(rbst1_children, rbst1_values, rbst1_counts, INF, rbst1_root, c + 1)

        if len(stack) == 0:
            ans[row] = row + 1 + rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
            continue

        found_nearest = b == w

        while stack:
            c = stack.pop()
            if found_nearest:
                rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                         moves[c])
                # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)
            else:
                if c < b + 1:
                    rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root,
                                             b + 1)
                    rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c])
                    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c] + b + 1 - c)
                    moves[b + 1] = moves[c] + b + 1 - c

                found_nearest = True

        # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)
        # debug_print(rbst2_children, rbst2_values, rbst2_counts, rbst2_root)

        move = rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
        if move == INF:
            break

        ans[row] = row + move + 1

    return ans


def debug_print(children, values, counts, root):
    print(children.T)
    print(values)
    print(counts)
    _debug_print(children, values, counts, root, 0)


def _debug_print(children, values, counts, i, depth):
    if i != -1:
        _debug_print(children, values, counts, children[i, 0], depth + 1)
        print('      ' * depth, values[i], counts[i])
        _debug_print(children, values, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))