Problem 753

uses
    SysUtils, Math;

const
    bad:int64=-round(1e12); // -INFINITY

var
    i,n,q,qq,tt,x,y,tp,k,kk,cc,l,r:longint;
    a,b:array[0..400010] of int64;

function maxI(x,y:longint):longint; // получает индексы элементов, возвращает индекс максимального элемента
begin
if b[x]>b[y] then result:=x else result:=y;
end;

function build(n:longint):longint; // производит предподсчет

var
    k,i,j:longint;

begin
k:=1;
while k<=n do k:=k shl 1;
kk:=k;
k:=k shl 1;
b[0]:=bad;
for i:=n+1 to kk do
    b[i]:=bad;
j:=1;
for i:=kk to k do begin
    a[i]:=j;
    inc(j);
end;
for i:=kk-1 downto 1 do
    a[i]:=maxI(a[i*2],a[i*2+1]);
result:=k;
end;

function rmq(l,r:longint):longint; // получает индексы элементов, возвращает индекс максимального на отрезке
var
    kk:longint;
begin
kk:=k shr 1;
inc(l,kk-1);
inc(r,kk-1);
result:=maxI(a[l],a[r]);
while r-l>1 do begin
    if l mod 2=0 then result:=maxI(result,a[l+1]);  // если левый сын
    if r mod 2=1 then result:=maxI(result,a[r-1]);  // если правый сын
    l:=l div 2;
    r:=r div 2;
end;
end;

procedure update(v:longint); // пересчитывает дерево после изменения элемента
begin
v:=v div 2;
while v>=1 do begin
    a[v]:=maxI(a[2*v],a[2*v+1]);
    v:=v div 2;
end;
end;

begin  // B - массив с числами; А - дерево, в котором мы храним индексы
reset(input,'input.txt');
rewrite(output,'output.txt');
fillchar(a,sizeof(a),0);    // обнуляем массивы
fillchar(b,sizeof(b),0);
read(n,q);
k:=build(n);               // строим первичное дерево (особого смысла нет, только получаем максимальный размер)
cc:=0;                     // счетчик максимального количества групп
for qq:=1 to q do begin
    read(tp);
    if tp=1 then begin
        read(x,y);
        tt:=rmq(x,y);           // находим максимум на отрезке
        if b[tt]=0 then begin   // если он равен 0, то ни один элемент не входит ни в одну группу
            inc(cc);              // увеличиваем счетчик
            for i:=x to y do begin  // изменяем все элементы отрезка
                b[i]:=cc;
                update(i);
            end;
            writeln(1);             // пишем, что ОК
        end else writeln(0);      // иначе пишем, что нельзя объединить
    end else
    if tp=2 then begin
        read(x);
        tt:=b[x];
        b[x]:=0;
        if tt>0 then begin        // если элемент принадлежит какой-нибудь группе
            l:=x-1;
            r:=x+1;
            while (b[r]=tt) and (r<=n) do begin // находим правую границу, попутно обнуляя элементы
                b[r]:=0;
                update(r);
                inc(r);
            end;
            while (b[l]=tt) and (l>0) do begin  // находим левую границу, попутно обнуляя элементы
                b[l]:=0;
                update(l);
                dec(l);
            end;
            writeln(l+1,' ',r-1);               // выводим границы
        end else writeln('0 0');              // если элемент не относится ни к одной из групп - выводим дво нуля
    end;
end;

end.