其实这个“反病毒软件”（Anti-Virus SOFTware），是相关部门应对H9N7人流感研发的。

相关部门的监控范围里只有N个城市，从1到N编号。初始时，这些城市都没有任何病例出现。由于在某一个城市出现过多的病例不太好，相关部门需要随时知道，从X到Y（含X和Y）这些城市当中，病例最多的城市与病例第二多的城市的病例数之差为多少。

一共会有Q个事件发生，具体见【输入】。

第一行为两个整数N，Q，以空格隔开。

接下来Q行，每行代表一个事件。第i+1行代表第i个事件，这一行有三个整数Ci，Xi，Yi，其中Ci为1或2。如果Ci为1，表示在城市Xi又新发现了Yi个病例；如果Ci为2，表示询问从Xi到Yi，病例最多的城市与病例第二多的城市的病例数之差为多少。

对于输入中的每一个Ci=2的事件，输出一行，即询问的结果。

4

2 1 4

1 2 3

2 2 4

1 3 2

2 1 3

1 2 2

2 1 4

0

3

1

3

【样例说明】

初始时各个城市的病例数为{0，0，0，0}。

从1到4最多的病例数为0，第二多的病例数为0，差值为0，输出0。

城市2发现了3个新病例，病例数变为{0，3，0，0}。

从2到4最多的病例数为3，第二多的病例数为0，差值为3，输出3。

城市3发现了2个新病例，病例数变为{0，3，2，0}。

从1到3最多的病例数为3，第二多的病例数为2，差值为1，输出1。

城市2发现了2个新病例，病例数变为{0，5，2，0}。

从1到4最多的病例数为5，第二多的病例数为2，差值为3，输出3。

【数据规模与约定】

对于40%的数据，N，Q≤1000。

对于100%的数据，2≤N，Q≤100000，且对于每一个Ci=2，满足Xi＜Yi。

 1 type vet=record 2                 a1,a0:longint; 3       end; 4 var 5    i,j,k,l,m,n:longint; 6    a2:vet; 7    a:array[0..500050] of vet; 8    d:array[0..500050] of longint; 9    c:array[0..10] of longint;10 procedure swap(var x,y:longint);inline;11           var z:longint;12           begin13                z:=x;x:=y;y:=z;14           end;15 function max(x,y:longint):longint;inline;16          begin17               if x>y then max:=x else max:=y;18          end;19 function min(x,y:longint):longint;inline;20          begin21               if x<y then min:=x else min:=y;22          end;23 24 function merge(a2,a3:vet):vet;inline;25           var i,j,k,l:longint;a4:vet;26           begin27                c[1]:=a2.a0;c[2]:=a2.a1;28                c[3]:=a3.a0;c[4]:=a3.a1;29                a4.a0:=0;a4.a1:=0;30                for i:=1 to 4 do31                    begin32                         if c[i]>=a4.a0 then33                            begin34                                 a4.a1:=a4.a0;35                                 a4.a0:=c[i];36                            end37                         else 38                             begin39                                 if (c[i]>a4.a1) and (c[i]<a4.a0) then a4.a1:=c[i];40                             end;41                    end;42                exit(a4);43           end;44 procedure built(z,x,y:longint);inline;45           begin46                if x=y then47                   d[x]:=z48                else49                    begin50                         built(z*2,x,(x+y) div 2);51                         built(z*2+1,(x+y) div 2+1,y);52                    end;53                a[z].a0:=0;a[z].a1:=0;54           end;55 procedure doit(x,y:longint);56           begin57                x:=d[x];58                a[x].a0:=a[x].a0+y;a[x].a1:=0;59                while x>1 do60                      begin61                           a[x div 2]:=merge(a[x],a[x+1-2*(x mod 2)]);62                           x:=x div 2;63                      end;64           end;65 function cal(z,x,y,l,r:longint):vet;66          var a3,a2:vet;67          begin68               if l>r then69                  begin70                       a2.a0:=0;71                       a2.a1:=0;72                       exit(a2);73                  end;74               if (x=l) and (y=r) then exit(a[z]);75               exit(merge(cal(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2)),cal(z*2+1,(x+y) div 2+1,y,max(l,(x+y) div 2+1),r)));76          end;77 begin78      readln(n);79      built(1,1,n);80      while not(eof) do81          begin82               readln(j,k,l);83               case j of84                    1:doit(k,l);85                    2:begin86                           a2:=cal(1,1,n,k,l);87                           writeln(a2.a0-a2.a1);88                    end;89               end;90          end;91      readln;92 end.