#include<bits/stdc++.h>
using namespace std;
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	clock_t start,end;
        
//	start=clock();
        
//	end=clock();
//	cout<<endl<<double(end-start)/CLK_TCK;
    return 0;
}

int read(){
	int k=0,x=0;
	char s=getchar();
	while(s<'0'||s>'9'){
		k|=s=='-';
		s=getchar();
	}
	while(s>='0'&&s<='9'){
		x=(x<<3)+(x<<1)+(s^48);
		s=getchar();
	}return k?-x:x;
}

void write(int x) {
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10^'0');
}

string gaojia(string a,string b){
	int la=a.size(),lb=b.size();
	if(la<lb)swap(a,b),swap(la,lb);
	la--,lb--;
	int G=0;
	while(lb>=0){
		int S=a[la]-'0'+b[lb]-'0'+G;
		G=S/10;
		S=S%10;
		a[la]=S+'0';
		la--,lb--;
	}
	while(la>=0){
		int S=a[la]-'0'+G;
		G=S/10;S=S%10;
		a[la]=S+'0';
		la--,lb--;
	}
	if(G!=0)a='1'+a;
	return a;
}

string gaojian(string a1,string b1){
	int lena=a1.length(),lenb=b1.length(),lenc;
	int a[2005],b[2005],c[2005];
	for(int i=0;i<lena;i++)a[lena-i]=a1[i]-'0';
	for(int i=0;i<lenb;i++)b[lenb-i]=b1[i]-'0';
	int i=1;
	while(i<=lena||i<=lenb){
		if(a[i]<b[i]){
			a[i]+=10;
			a[i+1]--;
		}c[i]=a[i]-b[i];
		i++;
	}lenc=i;
	while(c[lenc]==0&&lenc>1)lenc--;
	string k="";
	for(i=lenc;i>0;i--)k+=c[i]+'0';
	return k;
}

string gaocheng(string x,string y){
	int a[1005]={0},b[1005]={0},c[1005]={0};
	int lena=x.size();
	int lenb=y.size();
	for(int i=0;i<lena;i++)a[lena-i]=x[i]-'0';
	for(int i=0;i<lenb;i++)b[lenb-i]=y[i]-'0';
	for(int i=1;i<=lenb;i++){
		int k=0;
		for(int j=1;j<=lena;j++){
			c[i+j-1]=c[i+j-1]+a[j]*b[i]+k;
			k=c[i+j-1]/10;	
			c[i+j-1]%=10;
		}c[i+lena]=k;
	}int lenc=lena+lenb;
	while(c[lenc]==0&&lenc>1)lenc--;
	string l;
	for(int i=lenc;i>0;i--){
		l+=c[i]+'0';
	}return l;
}