Problem:


Score : 600 points

Problem Statement

There is a grid of squares with H+1 horizontal rows and W vertical columns.

You will start at one of the squares in the top row and repeat moving one square right or down. However, for each integer i from 1 through H, you cannot move down from the A_i-th, (A_i + 1)-th, \ldots, B_i-th squares from the left in the i-th row from the top.

For each integer k from 1 through H, find the minimum number of moves needed to reach one of the squares in the (k+1)-th row from the top. (The starting square can be chosen individually for each case.) If, starting from any square in the top row, none of the squares in the (k+1)-th row can be reached, print -1 instead.

Constraints

1 \leq H,W \leq 2\times 10^5

1 \leq A_i \leq B_i \leq W

Input

Input is given from Standard Input in the following format:

H W
A_1 B_1
A_2 B_2
:
A_H B_H

Output

Print H lines. The i-th line should contain the answer for the case k=i.

Sample Input 1

4 4
2 4
1 1
2 3
2 4

Sample Output 1

1
3
6
-1

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

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

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

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

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



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


Sample output:
1
3
6
-1

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline

class SegTreeFlag():
    def segFunc(self, x, y):
        return x+y
    def searchIndexFunc(self, val):
        return val > 0
    def __init__(self, ide, init_val):
        n = len(init_val)
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segFunc(self.seg[2*i+1],self.seg[2*i+2])
    def update(self, idx, val):
        idx += self.num-1
        self.seg[idx] = val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def addition(self, idx, val):
        idx += self.num-1
        self.seg[idx] += val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def multiplication(self, idx, val):
        idx += self.num-1
        self.seg[idx] *= val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def query(self, begin, end):
        if end <= begin:
            return self.ide_ele
        begin += self.num-1
        end += self.num-2
        res = self.ide_ele
        while begin + 1 < end:
            if begin&1 == 0:
                res = self.segFunc(res, self.seg[begin])
            if end&1 == 1:
                res = self.segFunc(res, self.seg[end])
                end -= 1
            begin = begin//2
            end = (end-1)//2
        if begin == end:
            res = self.segFunc(res, self.seg[begin])
        else:
            res = self.segFunc(self.segFunc(res, self.seg[begin]), self.seg[end])
        return res
    def getLargestIndex(self, begin, end):
        L, R = begin, end
        if not self.searchIndexFunc(self.query(begin, end)):
            return None
        while L+1 < R:
            P = (L+R)//2
            if self.searchIndexFunc(self.query(P, R)):
                L = P
            else:
                R = P
        return L
    def getSmallestIndex(self, begin, end):
        L, R = begin, end
        if not self.searchIndexFunc(self.query(begin, end)):
            return None
        while L+1 < R:
            P = (L+R+1)//2
            if self.searchIndexFunc(self.query(L, P)):
                R = P
            else:
                L = P
        return L

class SegTreeMin():
    def segFunc(self, x, y):
        if x < y:
            return x
        else:
            return y
    def searchIndexFunc(self, val):
        return True
    def __init__(self, ide, init_val):
        n = len(init_val)
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segFunc(self.seg[2*i+1],self.seg[2*i+2])
    def update(self, idx, val):
        idx += self.num-1
        self.seg[idx] = val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def addition(self, idx, val):
        idx += self.num-1
        self.seg[idx] += val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def multiplication(self, idx, val):
        idx += self.num-1
        self.seg[idx] *= val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def query(self, begin, end):
        if end <= begin:
            return self.ide_ele
        begin += self.num-1
        end += self.num-2
        res = self.ide_ele
        while begin + 1 < end:
            if begin&1 == 0:
                res = self.segFunc(res, self.seg[begin])
            if end&1 == 1:
                res = self.segFunc(res, self.seg[end])
                end -= 1
            begin = begin//2
            end = (end-1)//2
        if begin == end:
            res = self.segFunc(res, self.seg[begin])
        else:
            res = self.segFunc(self.segFunc(res, self.seg[begin]), self.seg[end])
        return res
    def getLargestIndex(self, begin, end):
        L, R = begin, end
        if not self.searchIndexFunc(self.query(begin, end)):
            return None
        while L+1 < R:
            P = (L+R)//2
            if self.searchIndexFunc(self.query(P, R)):
                L = P
            else:
                R = P
        return L
    def getSmallestIndex(self, begin, end):
        L, R = begin, end
        if not self.searchIndexFunc(self.query(begin, end)):
            return None
        while L+1 < R:
            P = (L+R+1)//2
            if self.searchIndexFunc(self.query(L, P)):
                R = P
            else:
                L = P
        return L


def main():
    h, w = map(int, input().split())
    ans = [-1]*h
    segflag = SegTreeFlag(0, [1]*(w+2))
    tmp = [0]*(w+2)
    tmp[0] = float("inf")
    segmin = SegTreeMin(float("inf"), tmp)
    wall = [list(map(int, input().split())) for _ in range(h)]
    for i in range(h):
        a, b = wall[i][0], wall[i][1]
        idx = segflag.getLargestIndex(0, b+2)
        segflag.update(b+1, 1)
        segmin.update(b+1, segmin.query(idx, idx+1)+(b+1-idx))
        idx = segflag.getLargestIndex(a, b+1)
        while idx is not None:
            segflag.update(idx, 0)
            segmin.update(idx, float("inf"))
            idx = segflag.getLargestIndex(a, idx+1)
        tmp = segmin.query(0, w+1)
        if tmp != float("inf"):
            ans[i] = tmp + i + 1
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

class SegTreeFlag():
    def segFunc(self, x, y):
        return x+y
    def searchIndexFunc(self, val):
        return val > 0
    def __init__(self, ide, init_val):
        n = len(init_val)
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segFunc(self.seg[2*i+1],self.seg[2*i+2])
    def update(self, idx, val):
        idx += self.num-1
        self.seg[idx] = val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def addition(self, idx, val):
        idx += self.num-1
        self.seg[idx] += val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def multiplication(self, idx, val):
        idx += self.num-1
        self.seg[idx] *= val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def query(self, begin, end):
        if end <= begin:
            return self.ide_ele
        begin += self.num-1
        end += self.num-2
        res = self.ide_ele
        while begin + 1 < end:
            if begin&1 == 0:
                res = self.segFunc(res, self.seg[begin])
            if end&1 == 1:
                res = self.segFunc(res, self.seg[end])
                end -= 1
            begin = begin//2
            end = (end-1)//2
        if begin == end:
            res = self.segFunc(res, self.seg[begin])
        else:
            res = self.segFunc(self.segFunc(res, self.seg[begin]), self.seg[end])
        return res
    def getLargestIndex(self, begin, end):
        L, R = begin, end
        if not self.searchIndexFunc(self.query(begin, end)):
            return None
        while L+1 < R:
            P = (L+R)//2
            if self.searchIndexFunc(self.query(P, R)):
                L = P
            else:
                R = P
        return L
    def getSmallestIndex(self, begin, end):
        L, R = begin, end
        if not self.searchIndexFunc(self.query(begin, end)):
            return None
        while L+1 < R:
            P = (L+R+1)//2
            if self.searchIndexFunc(self.query(L, P)):
                R = P
            else:
                L = P
        return L

class SegTreeMin():
    def segFunc(self, x, y):
        if x < y:
            return x
        else:
            return y
    def searchIndexFunc(self, val):
        return True
    def __init__(self, ide, init_val):
        n = len(init_val)
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segFunc(self.seg[2*i+1],self.seg[2*i+2])
    def update(self, idx, val):
        idx += self.num-1
        self.seg[idx] = val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def addition(self, idx, val):
        idx += self.num-1
        self.seg[idx] += val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def multiplication(self, idx, val):
        idx += self.num-1
        self.seg[idx] *= val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def query(self, begin, end):
        if end <= begin:
            return self.ide_ele
        begin += self.num-1
        end += self.num-2
        res = self.ide_ele
        while begin + 1 < end:
            if begin&1 == 0:
                res = self.segFunc(res, self.seg[begin])
            if end&1 == 1:
                res = self.segFunc(res, self.seg[end])
                end -= 1
            begin = begin//2
            end = (end-1)//2
        if begin == end:
            res = self.segFunc(res, self.seg[begin])
        else:
            res = self.segFunc(self.segFunc(res, self.seg[begin]), self.seg[end])
        return res
    def getLargestIndex(self, begin, end):
        L, R = begin, end
        if not self.searchIndexFunc(self.query(begin, end)):
            return None
        while L+1 < R:
            P = (L+R)//2
            if self.searchIndexFunc(self.query(P, R)):
                L = P
            else:
                R = P
        return L
    def getSmallestIndex(self, begin, end):
        L, R = begin, end
        if not self.searchIndexFunc(self.query(begin, end)):
            return None
        while L+1 < R:
            P = (L+R+1)//2
            if self.searchIndexFunc(self.query(L, P)):
                R = P
            else:
                L = P
        return L


def main():
    h, w = map(int, input().split())
    ans = [-1]*h
    segflag = SegTreeFlag(0, [1]*(w+2))
    tmp = [0]*(w+2)
    tmp[0] = float("inf")
    segmin = SegTreeMin(float("inf"), tmp)
    wall = [list(map(int, input().split())) for _ in range(h)]
    for i in range(h):
        a, b = wall[i][0], wall[i][1]
        idx = segflag.getLargestIndex(0, b+2)
        segflag.update(b+1, 1)
        segmin.update(b+1, segmin.query(idx, idx+1)+(b+1-idx))
        idx = segflag.getLargestIndex(a, b+1)
        while idx is not None:
            segflag.update(idx, 0)
            segmin.update(idx, float("inf"))
            idx = segflag.getLargestIndex(a, b+1)
        tmp = segmin.query(0, w+1)
        if tmp != float("inf"):
            ans[i] = tmp + i + 1
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import random


class RandomizedBinarySearchTree:
    def __init__(self, n):
        n += 10
        self.n = n
        self.children = [[0] * n, [0] * n]
        self.values = [0] * n
        self.counts = [0] * n
        self.indices = list(range(n - 2, -1, -1))
        self.root = -1

    def merge(self, left_root, right_root):
        children = self.children
        counts = self.counts
        li = left_root
        ri = right_root
        stack = []
        while li != -1 and ri != -1:
            if random.randrange(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 != -1 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 split(self, root, x):
        i = root
        children = self.children
        values = self.values
        counts = self.counts
        l_stack = []
        r_stack = []
        while i != -1:
            if x < values[i]:
                r_stack.append(i)
                i = children[0][i]
            else:
                l_stack.append(i)
                i = children[1][i]

        li, ri = -1, -1
        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 insert(self, x):
        children = self.children
        values = self.values
        counts = self.counts

        ni = self.indices.pop()
        children[0][ni] = children[1][ni] = -1
        values[ni] = x
        counts[ni] = 1

        li, ri = self.split(self.root, x)
        self.root = self.merge(self.merge(li, ni), ri)

    def delete(self, x):
        children = self.children
        counts = self.counts
        li, mri = self.split(self.root, x - 1)
        mi, ri = self.split(mri, x)

        if mi == -1:
            self.root = self.merge(li, ri)
            return

        if counts[mi] == 1:
            self.indices.append(mi)
            self.root = self.merge(li, ri)
            return

        i = mi
        stack = []
        while i != -1:
            if children[0][i] != -1 and children[1][i] != -1:
                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] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[is_right][pi] = children[0][i]
                    else:
                        mi = children[0][i]
                elif children[1][i] != -1:
                    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] = -1
                break

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

        self.root = self.merge(self.merge(li, mi), ri)

    def upper_bound(self, x, default=-1):
        i = self.root
        children = self.children
        values = self.values
        counts = self.counts
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            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 lower_bound(self, x, default=-1):
        i = self.root
        children = self.children
        values = self.values
        counts = self.counts
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            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 get_k_th(self, k, default=-1):
        i = self.root
        children = self.children
        values = self.values
        counts = self.counts
        if counts[i] <= k:
            return default
        j = k
        while i != -1:
            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

    def debug_print(self):
        print('Lefts ', self.children[0])
        print('Rights', self.children[1])
        print('Values', self.values)
        print('Counts', self.counts)
        self._debug_print(self.root, 0)

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


h, w = map(int, sys.stdin.buffer.readline().split())
INF = 10 ** 18
rbst1 = RandomizedBinarySearchTree(w)
rbst2 = RandomizedBinarySearchTree(w)
rbst1.insert(INF)
rbst2.insert(INF)
for i in range(1, w + 1):
    rbst1.insert(i)
    rbst2.insert(0)
moves = [0] * (w + 1)
ans = [-1] * h

mp = map(int, sys.stdin.buffer.read().split())
for row, (a, b) in enumerate(zip(mp, mp)):
    c, _ = rbst1.lower_bound(a)
    stack = []
    while c <= b + 1:
        stack.append(c)
        c, _ = rbst1.lower_bound(c + 1)

    if len(stack) == 0:
        ans[row] = row + 1 + rbst2.get_k_th(0)
        continue

    found_nearest = b == w

    while stack:
        c = stack.pop()
        if found_nearest:
            rbst1.delete(c)
            rbst2.delete(moves[c])
        else:
            if c < b + 1:
                rbst1.delete(c)
                rbst1.insert(b + 1)
                rbst2.delete(moves[c])
                rbst2.insert(moves[c] + b + 1 - c)
                moves[b + 1] = moves[c] + b + 1 - c

            found_nearest = True

    move = rbst2.get_k_th(0, -1)
    if move == INF:
        break

    ans[row] = row + move + 1

print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

import numpy as np
import numba as nb


@nb.njit('i8(i8[:,:],i8[:],i8,i8)', cache=True)
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


@nb.njit('UniTuple(i8,2)(i8[:,:],i8[:],i8[:],i8,i8)', cache=True)
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


nb_list_i8 = nb.types.List(nb.int64)


@nb.njit((nb.int64[:, :], nb.int64[:], nb.int64[:], nb_list_i8, nb.int64, nb.int64), cache=True)
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)


@nb.njit((nb.types.int64[:, :], nb.int64[:], nb.int64[:], nb_list_i8, nb.int64, nb.int64), cache=True)
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.append(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.append(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


@nb.njit('(i8[:,:],i8[:],i8[:],i8,i8,i8)', cache=True)
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


@nb.njit('(i8[:,:],i8[:],i8[:],i8,i8,i8)', cache=True)
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


@nb.njit('(i8[:,:],i8[:],i8[:],i8,i8,i8)', cache=True)
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


@nb.njit('(i8[:],)', cache=True)
def solve(inp):
    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    rbst_size = w + 10
    rbst1_indices = list(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 = list(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)


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