学步园

祖玛大家都玩过吧，没有玩过也没有关系，这里讲解下：

你面前有一排带色彩的球，都是纯色的，然后你手上有若干个球，每个球带一个色彩，你需要把这个球砸向那排球中间得某个位置，如果砸上去后，整个球排出现了3个或者3个以上相同颜色的球，那么这块就消去，这块的左右两端连接上,然后继续删除块，只到不能删除了为止，然后砸入下一个……你有K此砸球的机会。

现在的问题就是，已知目前这排球的颜色情况，颜色用一个数字表示，相同颜色数字相同。已知你要依次砸向Si位置一个颜色为Ai的球，想知道K次砸球后得球排队列情况……

（注意：初始状态的时候不必先删除块，先砸。）

输入

第一行包含一个整数T，表示有T组数据

以下每组数据，第一行包含2个整数N（<=1000），K（<=50）分别代表原始状态有N个球，你有K次砸球的机会。

接下来一行是按照顺序给出N个球的颜色。

接下来K行，每行包含2个数字Si和Ai，分别表示第i次砸球的位置和球的颜色。

保证数据合法。

输出

如描述所要求，希望得到一个最终序列，输出最终包含的M个球的颜色状态，每个颜色间用一个空格，结尾换行。

如果没有球了输出-1。

样例输入

210 31 1 2 1 1 3 2 2 3 38 23 23 210 31 1 2 1 1 3 2 2 3 38 23 21 1

样例输出

-12 2 1 1

#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
	int data;
	struct Node* next;
	struct Node* prio;
}LNode, *LinkList;

LinkList createList(LinkList L, int n)
{
	L=(LinkList)malloc(sizeof(LNode));
	L->next=NULL;
	L->prio=NULL;
	LinkList head= L;
	LinkList s;
	int i;
	for(i=0; i<n; i++)
	{
		s=(LinkList)malloc(sizeof(LNode));
		scanf("%d", &s->data);
		s->next=NULL;
		s->prio=L;
		L->next=s;
		L=s;
	}
	return head;
}

LinkList ListInsert(LinkList L, int p, int c)
{
	LinkList head=L;
	int i;
	for(i=0; i<p-1; i++)
	{
		L=L->next;
	}
	LinkList s=(LinkList)malloc(sizeof(LNode));
	s->data=c;
	s->next=L->next;
	s->prio=L;
	L->next->prio=s;
	L->next=s;
	return head;
}

LinkList check(LinkList L)
{
	LinkList head=L;
	LinkList a, b, temp;
	int res=0;
	a=L->next;
	if(a)
	{
		b=a->next;

		while(b)
		{
			int j;
			if(a->data==b->data)
			{
				L=a;
				j=0;
				while(a->data==b->data)
				{
					a=a->next;
					b=b->next;
					j++;
					if(b==NULL)
						break;
				}
				if(j>=2)
				{

					L->prio->next=b;
					if(b!=NULL)
					{
						b->prio=L->prio;
					}
					for(; j>=0; j--)
					{
						temp=L->next;
						free(L);
						L=temp;
					}
					res=1;
					break;
				}
			}
			else
			{
				a=a->next;
				b=b->next;
			}
		}
		if(res==1)
			check(head);
	}
	return head;
}


LinkList displayList(LinkList L)
{
	LinkList head=L;
	L=L->next;
	if(!L)
		printf("-1\n");
	else
	{
		while(L)
		{
			printf("%d ", L->data);
			L=L->next;
		}
		printf("\n");
	}
	return head;
}

LinkList zuma(LinkList L, int k)
{
	int i;
	int p, c;
	LinkList head=L;
	for(i=0; i<k; i++)
	{
		scanf("%d %d", &p, &c);
		L=ListInsert(L, p, c);
		L=check(L);

	}
	displayList(L);
	return head;
}


void freeList(LinkList L)
{
	LinkList TL;
	while(L)
	{
		TL=L->next;
		free(L);
		L=TL;
	}
}

int main()
{
	int t;
	scanf("%d", &t);
	int i;
	int n, k;
	for(i=0; i<t; i++)
	{
		scanf("%d", &n);
		scanf("%d", &k);
		LinkList L=createList(L, n);
		zuma(L, k);

		freeList(L);
	}
	return 0;
}