#include<stdio.h>
#include<malloc.h>
#define HUN 10000
typedef struct node
{
int data;
struct node *next;
}NODE;   //定義鏈表結構

NODE *insert(u,num)//在u節點之后插入一個新的NODE，其值為NUM
NODE *u;
int num;
{
	NODE *v;
	v=(NODE*)malloc(sizeof(NODE));//分配內存
	v->data=num;      //賦值
	u->next=v;        //在u后面加入一個NODE
	return(v);
}

NODE *addint(p,q)   //完成加法操作返回指向*p+*q結果的指針
NODE *p,*q;
{
	NODE *pp,*qq,*r,*s,*t;
	int total,number,carry;
	pp=p->next;qq=q->next;
	s=(NODE*)malloc(sizeof(NODE));//建立存放和的鏈表表頭
	s->data=-1;
	t=s;
	carry=0;                 //進位變量
	while(pp->data!=-1&&qq->data!=-1)//都不是表頭
	{
		total=pp->data+qq->data+carry;//對應位和上次進位數求和
		number=total%HUN;      //記錄可以存入鏈表的數
		carry=total/HUN;       //多出的為進位數
		t=insert(t,number);    //把可存入的數插入鏈表
		pp=pp->next;      //取后面的數
		qq=qq->next;      //
	}
	r=(pp->data!=-1)?pp:qq;//兩數大小不一取尚未處理的指針
	while(r->data!=-1)     //判斷另一個是否到頭
	{
		total=r->data+carry;//與進位數相加
		number=total%HUN;   //記錄可存入的數
		carry=total/HUN;    //記錄進位數
		t=insert(t,number); //插入鏈表
		r=r->next;
	}
	if(carry)     //如果還有進位數
		t=insert(t,1);//最后一次處理
	t->next=s;   //完成鏈表
	return(s);   //返回求和指針
}

NODE *inputint(void) //輸入超大正整數
{
	NODE *s,*ps,*qs;
	struct number    //定義臨時中間結構
	{
		int num;
		struct number *np;
	}*p,*q;

	int i,j,k;
	long sum;
	char c;
	p=NULL;     //鏈首為個位，鏈尾為高位
	while((c=getchar())!='\n')  //按字符接受數字
		if(c>='0'&&c<='9')      //若為數字就存入
		{
			q=(struct number *)malloc(sizeof(struct number));
			q->num=c-'0';       //存入一位整數
			q->np=p;
			p=q;
		}
	s=(NODE*)malloc(sizeof(NODE));//建立正式鏈表的表頭
	s->data=-1;                 //表頭
	ps=s;
	while(p!=NULL)      //臨時鏈表不為空是
	{
		sum=0;i=0;k=1;
			while(i<4&&p!=NULL) //按四位合并臨時鏈表
			{
				sum=sum+k*(p->num);
				i++;p=p->np;k=k*10;
			}
			qs=(NODE*)malloc(sizeof(NODE));//正式鏈表的主體
			qs->data=sum;
			ps->next=qs;
			ps=qs;
	}
	ps->next=s;    //完成鏈表

	return(s);
}

printint(s)
NODE *s;
{
	if(s->next->data!=-1)
	{
		printint(s->next);
		if(s->next->next->data==-1)
			printf("%d",s->next->data);
		else{
			int i,k=HUN;
			for(i=1;i<=4;i++,k/=10)
				putchar('0'+s->next->data%(k)/(k/10));
		}
	}
}

main()
{
	NODE *s1,*s2,*s;
	NODE *inputint(),*addint(),*insert_after();
	s1=inputint();
	s2=inputint();
	printf("S1=");
	printint(s1);
	printf("\n");
	printf("S2=");
	printint(s2);
	printf("\n");
	s=addint(s1,s2);
	printf("S1+S2=");printint(s);printf("\n");
}