记录编号	33389	评测结果	AAAAAAAAAA
题目名称	韩国明星	最终得分	100
用户昵称	lizhe	是否通过	通过
代码语言	Pascal	运行时间	1.053 s
提交时间	2011-11-10 15:11:03	内存使用	24.91 MiB

program star;
var
  i,j,n,k,l,r,mid,x:longint;
  p:string;
  s:array[1..100000]of string;
  w:array[1..100000]of longint;
procedure swap(var a,b:string);
var
  c:string;
begin
  c:=a;
  a:=b;
  b:=c
end;

procedure swap2(var a,b:longint);
var
  c:longint;
begin
  c:=a;
  a:=b;
  b:=c
end;

procedure sort(l,r:longint);
var
  i,j:longint;
  x:string;
begin
  i:=l;
  j:=r;
  x:=s[(l+r) div 2];
  repeat
    while s[i]<x do inc(i);
    while x<s[j] do dec(j);
    if i<=j then
    begin
      swap(s[i],s[j]);
      inc(i);
      dec(j);
    end;
  until i>j;
  if l<j then sort(l,j);
  if i<r then sort(i,r);
end;

procedure sort2(l,r:longint);
var
  i,j,x:longint;
begin
  i:=l;
  j:=r;
  x:=w[(l+r) div 2];
  repeat
    while w[i]>x do inc(i);
    while x>w[j] do dec(j);
    if i<=j then
    begin
      swap2(w[i],w[j]);
      swap(s[i],s[j]);
      inc(i);
      dec(j);
    end;
  until i>j;
  if l<j then sort2(l,j);
  if i<r then sort2(i,r);
end;

procedure erfen;
begin
  l:=1; r:=n;
  while l<r do
  begin
    mid:=(l+r) shr 1;
    if s[mid]>=p then r:=mid
    else l:=mid+1
  end;
  w[l]:=w[l]+x
end;

begin
  assign(input,'star.in');
  reset(input);
  assign(output,'star.out');
  rewrite(output);
  readln(n);
  for i:=1 to n do
    readln(s[i]);
  sort(1,n);
  readln(k);
  for i:=1 to k do
  begin
    readln(p);
    readln(x);
    erfen
  end;
  sort2(1,n);
  i:=1; j:=1;
  while j<=n do
  begin
    if w[i]=w[j] then
    begin
      if j=n then
        sort(i,j);
      inc(j)
    end
    else
    begin
      if i<>j-1 then
        sort(i,j-1);
      i:=j
    end
  end;
  for i:=1 to n do
  begin
    writeln(s[i]);
    writeln(w[i])
  end;
  close(input);
  close(output)
end.