记录编号	39113	评测结果	AAAAAAAAAA
题目名称	椰子	最终得分	100
用户昵称	isabella	是否通过	通过
代码语言	Pascal	运行时间	0.168 s
提交时间	2012-07-04 20:31:04	内存使用	11.66 MiB

var
 x,y,p,w:array[1..1001]of longint;
 h:array[-1001..2002,0..1001]of longint;
 i,j,n,t,k,l:longint;

 procedure deal(k:longint);
  var
   h1,h2,h0,yy:longint;
  begin
   if y[k]=1 then exit;
   h1:=h[x[k]-1,0];
   h2:=h[x[k]+1,0];
   h0:=y[k]-1;
   if (h1>=h0)and(h2>=h0) then exit;

   yy:=h[x[k],h0];
   if h1>=h0 then begin
      if w[k]>w[yy]then begin
        x[yy]:=x[k]+1;
        inc(h[x[yy],0]);
        y[yy]:=h[x[yy],0];
        h[x[yy],y[yy]]:=yy;
        deal(yy);

        dec(h[x[k],0]);
        y[k]:=h[x[k],0];
        h[x[k],y[k]]:=k;
        deal(k);
      end else begin
        dec(h[x[k],0]);
        x[k]:=x[k]+1;
        inc(h[x[k],0]);
        y[k]:=h[x[k],0];
        h[x[k],y[k]]:=k;
        deal(k);
      end;
   end else if h2>=h0 then begin
      if w[k]>w[yy]then begin
        x[yy]:=x[k]-1;
        inc(h[x[yy],0]);
        y[yy]:=h[x[yy],0];
        h[x[yy],y[yy]]:=yy;
        deal(yy);

        dec(h[x[k],0]);
        y[k]:=h[x[k],0];
        h[x[k],y[k]]:=k;
        deal(k);
      end else begin
        dec(h[x[k],0]);
        x[k]:=x[k]-1;
        inc(h[x[k],0]);
        y[k]:=h[x[k],0];
        h[x[k],y[k]]:=k;
        deal(k);
      end;
   end else begin
      if w[k]>w[yy] then begin
        x[yy]:=x[k]+1;
        inc(h[x[yy],0]);
        y[yy]:=h[x[yy],0];
        h[x[yy],y[yy]]:=yy;
        deal(yy);

        dec(h[x[k],0]);
        y[k]:=h[x[k],0];
        h[x[k],y[k]]:=k;
        deal(k);
      end else begin
        dec(h[x[k],0]);
        x[k]:=x[k]-1;
        inc(h[x[k],0]);
        y[k]:=h[x[k],0];
        h[x[k],y[k]]:=k;
        deal(k);
      end;
   end;

  end;

begin
assign(input,'coconuts.in');reset(input);
assign(output,'coconuts.out');rewrite(output);
 readln(t);
 for l:=1 to t do
  begin
   fillchar(h,sizeof(h),0);
   readln(n);
   for i:=1 to n do read(p[i],w[i]);

   for i:=1 to n do
    begin
     x[i]:=p[i];
     inc(h[x[i],0]);y[i]:=h[x[i],0];h[x[i],y[i]]:=i;
     deal(i);
    end;

   for i:=1 to n do writeln(y[i],' ',x[i]);
   writeln;
  end;
close(input);close(output);
end.