#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct node
{
	char ch;
	struct node *next;
	struct node *prior;
}sjd;
//======================================================
//初始
void init(sjd **jd)
{
	if(((*jd)=(sjd*)malloc(sizeof(sjd)))==NULL)
	{
		printf("磁盤不足!\n");
		exit(1);
	}
	(*jd)->ch='0';
	(*jd)->next=NULL;
	(*jd)->prior=NULL;
}
//======================================================
//插入(帶頭鏈表)(在鏈h中第pos的位置插入數據ch)
int insert(sjd *h,char ch,int pos)
{
	int i;
	sjd *p,*q,*cr;
	init(&p);
	p->ch=ch;
	for(i=1,cr=h,q=h->next;q!=NULL && i<pos;i++,q=q->next,cr=cr->next);
	if(i!=pos)
	{
		printf("輸入參數有誤!\n");
		return 0;
	}
	if(q==NULL)   //說明是尾
	{
		p->next=cr->next;
		cr->next=p;
		p->prior=cr;
		return 1;
	}
	p->next=q;
	p->prior=cr;
	cr->next=p;
	q->prior=p;
	return 1;
}
//======================================================
//數據修改(在鏈h中修改第pos的數據,改為ch)
void mend(sjd *h,int pos,char ch)
{
	sjd *p;
	int i;
	for(p=h->next,i=1;p!=NULL && i<pos;p=p->next,i++);
	if(p==NULL || i!=pos)
	{
		printf("輸入參數有誤!\n修改失敗!\n");
		return;
	}
	p->ch=ch;
}
//======================================================
//數據查找(在鏈h中查找第pos位置的數據,并返回該數據)
char searchc(sjd *h,int pos)
{
	sjd *p;
	int i;
	for(p=h->next,i=1;p!=NULL && i<pos;p=p->next,i++);  //查找p
	if(p==NULL || i!=pos)
		return '\0';                         //說明不存在這個位置
	return p->ch;        //說明該結點中有數據
}
//======================================================
//數據顯示(顯示鏈h中的所有數據)
void display(sjd *h)
{
	sjd *p=h->next;
	if(p==NULL || h==NULL || h->ch!='0')
	{
		printf("無數據!\n");
		return;
	}
	for(;p->next!=NULL;p=p->next)
		printf("%c",p->ch);
	printf("%c\n",p->ch);
}
//======================================================
//求串長(求鏈h的數據個數,即串長,不包括頭結點)
int lengthlist(sjd *h)
{
	sjd *p;
	int i;
	if(h->ch!='0' || h==NULL)
	{
		printf("無數據!\n");
		return 0;
	}
	for(p=h->next,i=0;p!=NULL;p=p->next,i++);
	return i;
}
//======================================================
//復制數據 (將鏈x的數據復制到新創的鏈中并返回該鏈y)
sjd *fzsj(sjd *x)
{
	sjd *y,*p=x->next,*q,*t;
	if(x==NULL || x->next==NULL)
	{
		printf("無數據!\n");
		return NULL;
	}
	init(&y);
	t=y;
	while(p!=NULL)
	{
		init(&q);
		q->ch=p->ch;
  		q->next=t->next;
		q->prior=t;
		t->next=q;
		p=p->next;
		t=t->next;
	}
	return y;
}
//======================================================
//刪除數據(刪除第pos個位置的數據)
void del(sjd *h,int pos)
{
	sjd *p,*q;
	int i;
	for(p=h->next,i=1;p!=NULL && i<pos;p=p->next,i++);  //查找第pos個位置的數據
	if(p==NULL || i!=pos)
	{
		printf("輸入參數有誤!\n刪除失敗!\n");
		return;                       //說明不存在這個位置 
	}
	q=p->prior;
	q->next=p->next;
	if(p->next!=NULL)
		p->next->prior=q;
	free(p);
}
//======================================================
//撤消數據鏈(將鏈h撤消)
void freesjd(sjd *h)
{
	if(h==NULL)
	{
		printf("無數據,撤消失敗!\n");
		return;
	}
	sjd *p=h->next,*q=h;
	while(p!=NULL)
	{
		free(q);
		q=p;
		p=p->next;
	}
	free(p);
}
//====================================================== 
//取長為固定s的子串(在鏈x中的第begin個位置取長為length的鏈串)
sjd *qzc(sjd *x,int begin,int length)
{ 
	sjd *y;
	int i,j=0;
	init(&y);
	for(i=begin;i<begin+length;i++)       //(記數原始) 
	{
		if(!searchc(x,i))
			break;
		insert(y,searchc(x,i),++j);
	}
	return y;
}
//======================================================
//判斷串的大小(比較串x與串y的大小)
int pdcdx(sjd *x,sjd *y)
{
	sjd *p,*q;
	if(lengthlist(x)>lengthlist(y))
		return 1;
	else if(lengthlist(x)<lengthlist(y))
		return -1;
	else
	{
		for(p=x->next,q=y->next;p!=NULL;p=p->next,q=q->next)
		{
			if(p->ch>q->ch)
				return 1;
			else if(p->ch<q->ch)
				return -1;
			else
				continue;
		}
		return 0;
	}
}
//======================================================
//鏈表初始 (初試一數據為0的鏈)
sjd *initsjdlist(void)
{
	sjd *x;
	init(&x);
	insert(x,'0',1);
	return x;
}
//======================================================
//鏈表數據初始
sjd *initsjd(void)
{
	sjd *x,*p;
	int i,j;
	char *cx;
	cx=(char *)malloc(sizeof(cx));
	init(&x);
	scanf("%s",cx);
	for(i=0,j=0,p=x;cx[i]!='\0';++i)
	{
		if(cx[i]>='0' && cx[i]<='9')
		{
			insert(x,cx[i],++j);
			p=p->next;
		}
		else
			continue;
	}
	return x;
}
//======================================================
//數據倒立(將鏈h中的數據倒立過來)
void sjdl(sjd *h)
{
	sjd *p,*q;
	char t;
	if(h->ch!='0')
	{
		printf("鏈中無數據!\n");
		return;
	}
	for(q=h;q->next!=NULL;q=q->next);  //初始q
	p=h->next;            //初始p
	if(p==NULL)
	{
		printf("無數據!\n");
		return;
	}
	while(p!=q && p->next!=q && p->prior!=q)
	{
		t=p->ch;
		p->ch=q->ch;
		q->ch=t;
		p=p->next;
		q=q->prior;
	}	
	t=p->ch;
	p->ch=q->ch;
	q->ch=t;
}
//========================================================
//在鏈表尾部插入數據
void insertlast(sjd *h,char ch)
{
	sjd *p,*q;
	init(&p);
	p->ch=ch;
	for(q=h;q->next!=NULL;q=q->next);
	p->next=q->next;
	p->prior=q;
	q->next=p;
}
//========================================================
//整理數據
void dowith(sjd *h)
{
	sjd *p=h->next,*q;
	if(p==NULL)
	{
		printf("無數據!\n");
		return;
	}
	if(p->ch=='0' && p->next==NULL)
		return;
	while(1)
	{
		if(p->next!=NULL && p->ch=='0')
		{
			q=p->next;
			del(h,1);
			p=q;
		}
		if(p->ch!='0')
			break;
	}
}
//======================================================
//乘法(將數據鏈x乘以數據鏈y并返回乘后的結果數據鏈z)
sjd *by(sjd *x,sjd *y)
{
	sjd *z;
	int i,j,m,n,jg=0,s=0,g=0;
	char ch;
	sjdl(x);sjdl(y);
	if(lengthlist(x)==1 && x->next->ch=='0' || lengthlist(y)==1 && y->next->ch=='0')
	{
		z=initsjdlist();
		return z;
	}
	init(&z);
	i=1;										//以下是計算階段
	while(1)
	{
		j=1;
		if(searchc(y,i)=='\0')
			break;
		m=searchc(y,i)-48;
		while(1)
		{
			if(searchc(x,j)=='\0')
				break;
			n=searchc(x,j)-48;
			if(searchc(z,i+j-1)=='\0')
				jg=m*n+s;
			else
				jg=m*n+s+searchc(z,i+j-1)-48;
			s=jg/10;
			g=jg%10;
			ch=g+48;
			if(searchc(z,i+j-1)!='\0')
				mend(z,i+j-1,ch);
			else
				insert(z,ch,i+j-1);
			j++;
		}
		insert(z,s+48,i+j-1);
		s=0;
		i++;
	}
	sjdl(x);sjdl(y);sjdl(z);
	dowith(z);
	return z;
}
//========================================================
//加法(將數據鏈x加上數據鏈y并返回加后的結果數據鏈z)
sjd *and(sjd *x,sjd *y)
{
	sjd *z;
	int i=1,j=0,m,n,jg=0,s=0,g=0;
	char ch;
	init(&z);sjdl(x);sjdl(y);
	while(searchc(x,i)!='\0' || searchc(y,i)!='\0')
	{
		if(searchc(x,i)=='\0')
			m=0;
		else
			m=searchc(x,i)-48;
		if(searchc(y,i)=='\0')
			n=0;
		else
			n=searchc(y,i)-48;
		jg=m+n+s;
		g=jg%10;
		s=jg/10;
		ch=g+48;
		insert(z,ch,++j);
		i++;
	}
	insert(z,s+48,++j);
	sjdl(x);sjdl(y);sjdl(z);
	dowith(z);
	return z;
}
//========================================================
//減法(將數據鏈x減去數據鏈y并返回減后的結果數據鏈z)
sjd *jf(sjd *x,sjd *y)
{
	sjd *z,*t,*p,*q;
	int i=1,j=0,m,n,jg=0;
	char ch;
	p=fzsj(x);
	q=fzsj(y);
	if(pdcdx(x,y)<0)
	{t=x;x=y;y=t;}
	init(&z);
	if(pdcdx(x,y)==0)
	{
		freesjd(p);	freesjd(q);
		insertlast(z,'0');
		return z;
	}
	sjdl(x);sjdl(y);
	while(searchc(x,i)!='\0' || searchc(y,i)!='\0')
	{
		if(searchc(x,i)=='\0')
			m=0;
		else
			m=searchc(x,i)-48;
		if(searchc(y,i)=='\0')
			n=0;
		else
			n=searchc(y,i)-48;
		if(m<n)
		{
			m+=10;
			jg=m-n;
			ch=searchc(x,i+1);
			ch-=1;
			mend(x,i+1,ch);
		}
		else
			jg=m-n;
		ch=jg+48;
		insert(z,ch,++j);
		i++;
	}
	if(pdcdx(p,q)<0)
	{
		for(i=1,t=q->next;t!=NULL;t=t->next,i++)           //復原
			mend(x,i,t->ch);
		for(i=1,t=p->next;t!=NULL;t=t->next,i++)           //復原
			mend(y,i,t->ch);
	}
	else
	{
		for(i=1,t=p->next;t!=NULL;t=t->next,i++)           //復原
			mend(x,i,t->ch);
		for(i=1,t=q->next;t!=NULL;t=t->next,i++)           //復原
			mend(y,i,t->ch);
	}
	if(pdcdx(p,q)<0)
	{t=x;x=y;y=t;}
	if(pdcdx(x,y)<0)
		insertlast(z,'-');
	freesjd(p);	freesjd(q);
	sjdl(z);
	dowith(z);
	return z;
}
//========================================================
//除法(將數據鏈x除去數據鏈y并返回除后的結果數據鏈z)
sjd *cf(sjd *x,sjd *y)
{
	sjd *z,*p;
	int j=0,m=0,n,length=0;
	char ch;
	init(&z);
	if(lengthlist(y)==1 && y->next->ch=='0')
	{
		printf("除數不能為零!\n");
		return NULL;
	}
	if(pdcdx(x,y)<0)
	{
		insert(z,'0',1);
		return z;
	}
	else
	{
		length=lengthlist(y);
		p=qzc(x,1,length);
        n=length;
		while(1)
		{
			if(pdcdx(p,y)<0)
				goto recom;
			while(pdcdx(p,y)>=0)
			{
				p=jf(p,y);
				++m;
			}
recom:
			ch=m+48;
			insertlast(z,ch);
			if(++n==lengthlist(x)+1)
				break;
			ch=searchc(x,n);
			insertlast(p,ch);
			m=0;
		}
	}
	dowith(z);
	return z;	
}
//========================================================
//求模
sjd *modc(sjd *x,sjd *y)
{
	sjd *p;
	int m=0,n,length=0;
	char ch;
	if(pdcdx(x,y)<0)
	{
		p=fzsj(x);
		return p;
	}
	else
	{
		length=lengthlist(y);
		p=qzc(x,1,length);
        n=length;
		while(1)
		{
			if(pdcdx(p,y)<0)
				goto recom;
			while(pdcdx(p,y)>=0)
			{
				p=jf(p,y);
				++m;
			}
recom:
			ch=m+48;
			if(++n==lengthlist(x)+1)
				break;
			ch=searchc(x,n);
			insertlast(p,ch);
			dowith(p);
			m=0;
		}
	}
	dowith(p);
	return p;
}
//========================================================
//求冪
sjd *powc(sjd *x,sjd *y)
{
	sjd *z,*tp,*p;
	init(&z);
	z=fzsj(x);
	init(&tp);
	insertlast(tp,'1');
	p=fzsj(y);
	p=jf(p,tp);
	for(;p->next->ch!='0';)
	{
		z=by(z,x);
		p=jf(p,tp);
	}
	return z;
}