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.

Solution (Python):
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)
        

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

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush

sys.setrecursionlimit(10**7)
import math








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

class segtree:
    '''init_val : i-indexed (init_val[0] = self.bin[1])'''
    def __init__(self, n, init = 0, init_val=None):
        self.n = n
        self.init = init
        self.k = math.ceil(math.log2(n))
        self.add_val = 1 << self.k

        try:
            init_val[0]
        except:
            raise ValueError('init_val should be list')

        self.bins = [self.init] * (1 << (self.k + 1))
        if init_val != None:
            self.update_set(init_val)
        self.caliculate()

    def __getitem__(self, idx):  
        return self.bins[idx + self.add_val]

    def update_set(self, vals):
        for idx, i in enumerate(range(self.add_val, self.add_val * 2)):
            if len(vals) > idx:
                self.bins[i] = vals[idx]
            else:continue

    def compare(self, l, r):
        return min(l ,r)

    def caliculate(self):
        k = self.k
        while k:
            for i in range(1<<k, 1<<(k+1)):
                if not i%2:
                    self.bins[i//2] = self.compare(self.bins[i], self.bins[i+1])
                else:continue
            k -= 1

    def update(self, idx, val, by=True):
        '''idx : 0-started index'''
        k = (1<<self.k) + idx
        if by:
            self.bins[k] += val
        else:
            self.bins[k] = val
        while k>1:
            self.bins[k // 2] = self.compare(self.bins[k // 2 * 2], self.bins[k // 2 * 2 + 1])
            k = k//2


    def eval(self, l, r):
        ret = self.init
        l = (1 << self.k) + l
        r = (1 << self.k) + r
        
        while True:
            
            if r - l == 1:
                ret = self.compare(ret, self.bins[l])
                ret = self.compare(ret, self.bins[r])
                break
            elif l == r:
                ret = self.compare(ret, self.bins[l])
                break
            else:
                done = False
                if l % 2:
                    ret = self.compare(ret, self.bins[l])
                    l += 1
                    done = True
                if not r % 2:
                    ret = self.compare(ret, self.bins[r])
                    r -= 1
                    done = True
                if not done:
                    l = l // 2
                    r = r // 2
        
        return ret

class BIT:
    
    def __init__(self, n, init=0, init_val=None):
        '''
        n : length of vals
        init : init_val in each bins
        init_val : if specified, update is performed
        ** applioed seqs -> seq[0] -> bins[1]
        '''
        self.n = n
        self.init = init
        self.k = n.bit_length()
        self.bins = [init] * (n+1)
        self.l2 = 2 ** self.k

        if init_val !=None:
            self.update_set(init_val)

    def update_set(self, vals):
        if len(vals) > self.n:
            raise ValueError('Length is too long!')
        for i, val in enumerate(vals):
            bi = i+1
            if bi & 1:
                self.bins[bi] = val
            else:
                ret = self.init
                most_sig = (bi & -bi)
                n_bit = bi - 1
                while n_bit:
                    v = n_bit & -n_bit
                    if most_sig  >= v:break
                    ret = self.compare(ret, self.bins[n_bit])
                    n_bit -= v
                self.bins[bi] = ret

    def compare(self, l, r):
        '''comparison-criteria'''
        return l+ r

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

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

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

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

    def lower_bound(self, SUM):
        '''return idx sum of which is less or equal to SUM'''
        if SUM <= 0:
            return 0
        l = 0
        r = self.l2
        while r > 0:
            if l+r <= self.n and self.bins[l+r] < SUM:
                SUM -= self.bins[l + r]
                l += r
            r >>= 1
        return l + 1

    def upper_bound(self, SUM):
        '''return idx sum of which is more than SUM'''
        l = 0
        r = self.l2
        
        while r > 0:
            if l + r <= self.n and self.bins[l + r] <= SUM:
                SUM -= self.bins[l + r]
                l += r
            r >>= 1
        return l + 1

class std_map:
    '''
    std_map function with restricted value range.
    n : max val permitted for map
    init : val if key is not specified
    '''

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

    def __contains__(self, key):  
        return key in self.keys

    def __getitem__(self, key):  
        return self.dic[key]

    def __setitem__(self, key, value):  
        if not key in self.keys:
            self.bit.update(key, 1)
            self.keys.add(key)
        self.dic[key] = value

    def remove(self, key):  
        self.keys.remove(key)
        self.bit.update(key, -1)

    def lower_bound(self, k):  
        return self.bit.lower_bound(self.bit.get_sum(k))

    def upper_bound(self, k):  
        return self.bit.upper_bound(self.bit.get_sum(k))

    def kth_key(self, k):  
        return self.bit.lower_bound(k)

    def kth_value(self, k):  
        return self.dic[self.kth_key(k)]

    def prev_k(self, k):  
        idx = self.bit.get_sum(k)
        if idx == 0:
            return -1
        return self.bit.lower_bound(idx - 1)

def run():
    H,W = map(int, sysread().split())
    tree = std_map(W, 0)
    for i in range(1, W+1):
        
        tree[i] = 0
    
    arr = [0] * (W+1)
    arr[0] = INF
    moves = segtree(W+1, init=INF, init_val=arr)

    for i in range(1, H+1):
        a, b = map(int, sysread().split())
        k = tree.upper_bound(a-1)
        min_val = INF
        while k <= b:
            min_val = min(b + 1 - k + moves[k], min_val)
            moves.update(k, INF, by=False)
            tree.remove(k)
            k = tree.upper_bound(a-1)
        if b+1 <= W and min_val < moves[b+1]:
            moves.update(b + 1, min_val, by=False)
            tree[b+1] = 1

        if moves.bins[1] == INF:
            print(-1)
        else:
            print(moves.bins[1] + i)




if __name__ == "__main__":
    run()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





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






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


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


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


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


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


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


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


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






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

class BIT:
  def __init__(self, logn):
    self.n = 1<<logn
    self.data = [0]*(self.n+1)
    self.el = [0]*(self.n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def bisect(self, x):
    w = i = 0
    k = self.n
    while k:
      if i+k <= self.n and w + self.data[i+k] < x:
        w += self.data[i+k]
        i += k
      k >>= 1
    return i+1


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

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


B = BIT(int_log(W,2)+1)

for i in range(W):
  B.add(i+1,1)
  

def calc_prev_valid(x):
  s = B.sum(x-1)
  if s == 0:
    return 0
  else:
    return B.bisect(s)
    



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


for i in range(H):
  

  a,b = data[i]
  now = b
  while now >= a:
    if B.el[now]:
      
      count_score[now-dic[now]] -= members[now]
      if not B.el[b+1]:
        dic[b+1] = dic[now]
        B.add(b+1,1)
      if b+1 < W+1:
        
        count_score[(b+1)-dic[b+1]] += members[now]
      B.add(now,-1)
      members[b+1] += members[now]
      members[now] = 0

    now = calc_prev_valid(now)

  
  
  
  
  while True:
    if count_score[score]:
      print(score+i+1)
      break
    else:
      score += 1
    if score == W:
      for _ in range(H-i):
        print(-1)
      exit()

Solution (Python):
import sys
input = sys.stdin.readline

from collections import defaultdict

def DD(arg): return defaultdict(arg)

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

H,W = list(map(int,input().split()))
data = [list(map(int, input().split())) for _ in range(H)]

class BIT:
  def __init__(self, logn):
    self.n = 1<<logn
    self.data = [0]*(self.n+1)
    self.el = [0]*(self.n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def bisect(self, x):
    w = i = 0
    k = self.n
    while k:
      if i+k <= self.n and w + self.data[i+k] < x:
        w += self.data[i+k]
        i += k
      k >>= 1
    return i+1

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

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

B = BIT(int_log(W,2)+1)
for i in range(W):
  B.add(i+1,1)

def calc_prev_valid(x):
  s = B.sum(x-1)
  if s == 0:
    return 0
  else:
    return B.bisect(s)

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

for i in range(H):
  a,b = data[i]
  now = b

  while now >= a:
    if B.el[now]:
      count_score[now-dic[now]] -= members[now]
      if not B.el[b+1]:
        dic[b+1] = dic[now]
        B.add(b+1,1)
      if b+1 < W+1:
        count_score[(b+1)-dic[b+1]] += members[now]
      B.add(now,-1)
      members[b+1] += members[now]
      members[now] = 0
    now = calc_prev_valid(now)

  while True:
    if count_score[score]:
      print(score+i+1)
      break
    else:
      score += 1
    if score == W:
      for _ in range(H-i):
        print(-1)
      exit()

Solution (Python):
import sys
input = sys.stdin.readline

from collections import defaultdict

def DD(arg): return defaultdict(arg)

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

H,W = list(map(int,input().split()))
data = [list(map(int, input().split())) for _ in range(H)]

class BIT:
  def __init__(self, logn):
    self.n = 1<<logn
    self.data = [0]*(self.n+1)
    self.el = [0]*(self.n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def bisect(self, x):
    w = i = 0
    k = self.n
    while k:
      if i+k <= self.n and w + self.data[i+k] < x:
        w += self.data[i+k]
        i += k
      k >>= 1
    return i+1

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

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

B = BIT(int_log(W,2)+1)
for i in range(W):
  B.add(i+1,1)

def calc_prev_valid(x):
  s = B.sum(x-1)
  if s == 0:
    return 0
  else:
    return B.bisect(s)

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

for i in range(H):
  a,b = data[i]
  now = b

  while now >= a:
    if B.el[now]:
      count_score[now-dic[now]] -= members[now]
      if not B.el[b+1]:
        dic[b+1] = dic[now]
        B.add(b+1,1)
      if b+1 < W+1:
        count_score[(b+1)-dic[b+1]] += members[now]
      B.add(now,-1)
      members[b+1] += members[now]
      members[now] = 0
    now = calc_prev_valid(now)

  while True:
    if count_score[score]:
      print(score+i+1)
      break
    else:
      score += 1
    if score == W:
      for _ in range(H-i):
        print(-1)
      exit()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





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






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


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


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


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


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


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


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


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






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

class BIT:
  def __init__(self, logn):
    self.n = 1<<logn
    self.data = [0]*(self.n+1)
    self.el = [0]*(self.n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def bisect(self, x):
    w = i = 0
    k = self.n
    while k:
      if i+k <= self.n and w + self.data[i+k] < x:
        w += self.data[i+k]
        i += k
      k >>= 1
    return i+1


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

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


B = BIT(int_log(W,2)+1)

for i in range(W):
  B.add(i+1,1)
  

def calc_prev_valid(x):
  s = B.sum(x-1)
  if s == 0:
    return -1
  else:
    return B.bisect(s)
    



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


for i in range(H):
  

  a,b = data[i]
  now = b
  while now >= a:
    if B.el[now]:
      
      count_score[now-dic[now]] -= members[now]
      if not B.el[b+1]:
        dic[b+1] = dic[now]
        B.add(b+1,1)
      if b+1 < W+1:
        
        count_score[(b+1)-dic[b+1]] += members[now]
      B.add(now,-1)
      members[b+1] += members[now]
      members[now] = 0

    now = calc_prev_valid(now)

  
  
  
  
  while True:
    if count_score[score]:
      print(score+i+1)
      break
    else:
      score += 1
    if score == W:
      for _ in range(H-i):
        print(-1)
      exit()

Solution (Python):
import sys 
input = sys.stdin.readline
from heapq import heappop,heappush

class BIT:
    def __init__(self, n):
        self.tree = [1]*(n+1)
        self.size = len(self.tree)
        self.tree[0] = 0
 
    def build(self):
        for i in range(self.size):
            j = i + (i & (-i))
            if j < self.size:
                self.tree[j] += self.tree[i]
    def sum(self, i):
        
        s = 0
        while i:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        while i < self.size:
            self.tree[i] += x
            i += i & -i

    
    def bsearch(self,x):
        le = 0
        ri = 1<<(self.size.bit_length()-1)
        while ri > 0:
            if le+ri < self.size and self.tree[le+ri]<x:
                x -= self.tree[le+ri]
                le += ri
            ri >>= 1
        return le+1

h,w = map(int,input().split())
bit = BIT(w+3)
bit.build()

q = [0]*(w)
dp = [0]*(w+3)
dp[0] = -1
rm_q = []

for i in range(h):
    a,b = map(int,input().split())
    for x in [a-1,b+1]:
        if x == 0 or x == w+1:
            continue
        if dp[x] != -1:
            continue
        k = bit.sum(x)
        if k >= 1:
            xl = bit.bsearch(k)
            dp[x] = dp[xl]+(x-xl)
            bit.add(x,1)
            heappush(q,dp[x])
    k = bit.sum(a-1)+1
    while True:
        x = bit.bsearch(k)
        if x > b:
            break
        bit.add(x,-1)
        heappush(rm_q, dp[x])
        dp[x] = -1
    while rm_q and rm_q[0] == q[0]:
        heappop(rm_q)
        heappop(q)
    if q == []:
        print(-1)
    else:
        print(q[0]+i+1)

Solution (Python):
import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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



seg_el=1<<((W+3).bit_length()) 
SEG=[1<<30]*(2*seg_el) 
LAZY=[0]*(2*seg_el) 

SEG2=[0]*(2*seg_el) 
LAZY2=[0]*(2*seg_el) 

def indexes(L,R):
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST
        

def updates(l,r,x): 
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=None:
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=SEG[ind<<1]=SEG[1+(ind<<1)]=LAZY[ind]
            LAZY[ind]=None
    
    while L!=R:
        if L > R:
            SEG[L]=x
            LAZY[L]=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG[R]=x
            LAZY[R]=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind]=max(SEG[ind<<1],SEG[1+(ind<<1)])

def updates2(l,r,x): 
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY2[ind]!=None:
            LAZY2[ind<<1]=LAZY2[1+(ind<<1)]=SEG2[ind<<1]=SEG2[1+(ind<<1)]=LAZY2[ind]
            LAZY2[ind]=None
    
    while L!=R:
        if L > R:
            SEG2[L]=x
            LAZY2[L]=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG2[R]=x
            LAZY2[R]=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG2[ind]=min(SEG2[ind<<1],SEG2[1+(ind<<1)]) 
        
def getvalues(l,r): 

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=None:
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=SEG[ind<<1]=SEG[1+(ind<<1)]=LAZY[ind]
            LAZY[ind]=None
            
    ANS=-1<<30

    while L!=R:
        if L > R:
            ANS=max(ANS , SEG[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS=max(ANS , SEG[R])
            R//=(R & (-R))

    return ANS

def getvalues2(l,r): 

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY2[ind]!=None:
            LAZY2[ind<<1]=LAZY2[1+(ind<<1)]=SEG2[ind<<1]=SEG2[1+(ind<<1)]=LAZY2[ind]
            LAZY2[ind]=None
            
    ANS=1<<31

    while L!=R:
        if L > R:
            ANS=min(ANS , SEG2[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS=min(ANS , SEG2[R])
            R//=(R & (-R))

    return ANS

for i in range(W+1):
    updates(i,i+1,i)

for i in range(H):
    x,y = map(int,input().split())
    if x==1:
        updates(x,y+1,-(1<<30))
    else:
        MAX=getvalues(1,x)
        updates(x,y+1,MAX)

    updates2(x,y+1,1<<30)
    updates2(y+1,y+2,y+1-getvalues(y+1,y+2))

    ANS=getvalues2(1,W+1)+i+1
    if ANS>1<<28:
        sys.stdout.write(str(-1)+"\n")
    else:
        sys.stdout.write(str(ANS)+"\n")