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: Wrong Answer

Solution code:
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)
    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 = max(1, fenwick_sum(arr, a))
        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)
        if len(stack) == 0:
            continue

        survive = stack.pop()
        if survive < w1:
            horizontal[survive] = b + 1 - survive
            heappush(q, (horizontal[survive], survive))

        for c in stack:
            fenwick_add(arr, w1, c, -1)
            horizontal[c] = -1

        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)))