记录编号	33442	评测结果	AAAAAAAAAA
题目名称	韩国明星	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.661 s
提交时间	2011-11-10 17:13:28	内存使用	10.66 MiB

//对于100%的数据，保证N<=100000　-8888<=Change<=8888　K<=100000.
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
using namespace std;

int len[100001]={0},sco[100001]={0};
char nam[100001][101]={{0}};

void swapint(int& a,int& b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}

void swapallchar(int posa,int posb)
{
	int i;
	char temp;
	if (len[posa]>len[posb])
	{
		for (i=0;i<=len[posb];i++)
		{
			temp=nam[posa][i];
			nam[posa][i]=nam[posb][i];
			nam[posb][i]=temp;
		}
		for (i=len[posb]+1;i<=len[posa];i++)
			nam[posb][i]=nam[posa][i];
	}
	else
	{
		for (i=0;i<=len[posa];i++)
		{
			temp=nam[posa][i];
			nam[posa][i]=nam[posb][i];
			nam[posb][i]=temp;
		}
		for (i=len[posa]+1;i<=len[posb];i++)
			nam[posa][i]=nam[posb][i];
	}
}

void qqsort1(int l,int r)
{
	int i,ll,rr,temp;
	char ch[101]={0};
	ll=l;
	rr=r;
	temp=rand()%(r-l+1)+l;
	for (i=0;i<=len[temp];i++)
		ch[i]=nam[temp][i];
	while (ll<=rr)
	{
		while (strcmp(nam[ll],ch)<0)
			ll++;
		while (strcmp(ch,nam[rr])<0)
			rr--;
		if (ll<=rr)
		{
			swapallchar(ll,rr);
			swapint(len[ll],len[rr]);
			ll++;
			rr--;
		}
	}
	if (l<rr)
		qqsort1(l,rr);
	if (ll<r)
		qqsort1(ll,r);
}
/*
void check(int aimlen,int& l,int& r)
{
	int mid;
	mid=(l+r)/2;
	while (l<r)
	{
		if (len[mid]==aimlen)
			break;
		else if (len[mid]<aimlen)
			l=mid+1;
		else if (len[mid]>aimlen)
			r=mid-1;
		mid=(l+r)/2;
	}
	l=mid;
	r=mid;
	while (len[l]==len[mid])
		l--;
	while (len[r]==len[mid])
		r++;
	l++;
	r--;
}
*/
void find(char aim[],int change,int l,int r)
{
	int mid;
	mid=(l+r)>>1;
	while (l<r)
	{
		if (strcmp(aim,nam[mid])==0)
			break;
		else if (strcmp(aim,nam[mid])>0)
			l=mid+1;
		else// if (strcmp(aim,nam[mid])<0)
			r=mid-1;
		mid=(l+r)>>1;
	}
	sco[mid]+=change;
}

void qqsort2(int l,int r)
{
	int ll,rr,temp;
	ll=l;
	rr=r;
	temp=sco[rand()%(r-l+1)+l];
	while (ll<=rr)
	{
		while (sco[ll]>temp)
			ll++;
		while (temp>sco[rr])
			rr--;
		if (ll<=rr)
		{
			swapallchar(ll,rr);
			swapint(sco[ll],sco[rr]);
			ll++;
			rr--;
		}
	}
	if (l<rr)
		qqsort2(l,rr);
	if (ll<r)
		qqsort2(ll,r);
}

int main(void)
{
	freopen("star.in","r",stdin);
	freopen("star.out","w",stdout);
	int i/*,j*/,n,k/*,l,r*/,change/*,aimlen*/;
	char aim[101];
	scanf("%d\n",&n);
	for (i=1;i<=n;i++)
	{
		scanf("%[^\n]\n",&nam[i]);
		len[i]=strlen(nam[i]);
	}
	qqsort1(1,n);
	scanf("%d\n",&k);
	for (i=1;i<=k;i++)
	{
		scanf("%[^\n]\n%d\n",&aim,&change);
		find(aim,change,1,n);
//		aimlen=strlen(aim);
//		l=1;
//		r=n;
//		check(aimlen,l,r);
//		for (j=l;j<=r;j++)
//			if (strcmp(aim,nam[j])==0)
//			{
//				sco[j]+=change;
//				break;
//			}
	}
	qqsort2(1,n);
	for (i=1;i<=n;i++)
		printf("%s\n%d\n",nam[i],sco[i]);
	fclose(stdin);
	fclose(stdout);
	return(0);
}