class BlockArray
A,B = 30,60
def initialize
@x = [1.0/0]
@nx = [0]
@pv = [0]
@v = [[0]]
@vx = [@x[-1]]
@r = 0
@h = 0
end
def to_a
a,x = [],0
a<<@x[x=@nx[x]] until @nx[x]==0
return a
end
def inspect
to_a.inspect
end
def around x
nx = ub x
pv = @pv[nx]
return @x[pv],@x[nx]
end
def up_k x,k
up = []
nx = @nx[ub x-1]
while 0<nx && 0!=k
up<<@x[nx]
k -= 1
nx = @nx[nx]
end
return up
end
def dn_k x,k
dn = []
pv = @pv[ub x]
while 0<pv && 0!=k
dn<<@x[pv]
k -= 1
pv = @pv[pv]
end
return dn
end
def insert x
v = insert_v x,@r,@h
return if ! v
@r = new_v @vx,[v,@r]
@h += 1
end
private
def ub x
v,h = @r,@h
v = @v[v].bsearch{|v| x<@vx[v] } while 0<=h -= 1
i = @v[v].bsearch{|i| x<@x[i] }
return i
end
def insert_v x,v,d
return insert_x x,v if d<1
a = @v[v]
j = a.bsearch_index{x<@vx[_1]}
v = insert_v x,a[j],d-1
a.insert j,v if v
return new_v @vx,a.shift(A) if B<a.size
end
def insert_x x,v
a = @v[v]
j = a.bsearch_index{x<@x[_1]}
nx = a[j]
xx = @x.size
pv = @pv[nx]
@x<<x
@nx[pv],@pv[xx],@nx[xx],@pv[nx] = xx,pv,nx,xx
a.insert j,xx
return new_v @x,a.shift(A) if B<a.size
end
def new_v xs,a
v = @v.size
@v<<a
@vx[v] = xs[a[-1]]
return v
end
end
(L,Q),*CX = $<.map{|ln| ln.split.map(&:to_i) }
B = BlockArray.new
B.insert 0
B.insert L
CX.each{|c,x|
if c<2
B.insert x
else
w,y = B.around x
puts y-w
end
}