/*
#include <stdio.h>
#include <string.h>
char stack1[101]={},stack2[101]={};
int stack3[102]={};
int top1=-1,top2=-1,top3=-1;
void push(int data)
{
stack3[++top3]=data;
}
char pop1()
{
return stack1[top1--];
}
char pop2()
{
return stack2[top2--];
}
int pop3()
{
return stack3[top3--];
}
int main()
{
char str1[101],str2[101];
int i,num=0,c=0;
int a,b,p,q;
scanf("%s %s",str1,str2);
a=strlen(str1);
b=strlen(str2);
for(i=0; i<a; i++)
{
stack1[++top1]=str1[i];
}
for(i=0; i<b; i++)
{
stack2[++top2]=str2[i];
}
while(top1!=-1||top2!=-1)
{
num=c;
if(top1!=-1) num+=pop1()-48;
if(top2!=-1) num+=pop2()-48;
push(num%10);
c=num/10;
}
if(c!=0) push(c);
while(top3!=-1)
{
printf("%d",pop3());
}
return 0;
}
*/
/*
#include <stdio.h>
int stack[201];
int top=-1;
void push(int data)
{
stack[++top]=data;
}
int pop()
{
return stack[top--];
}
int main()
{
char str[201]= {};
int i,a=0,b=0,c=0;
gets(str);
for(i=0; str[i]!=NULL; i++)
{
if(str[i]>=48&&str[i]<=57)
{
if(str[i+1]==32)
{
c+=str[i]-48;
push(c);
c=0;
}
else
{
c=c*10+(str[i]-48)*10;
}
}
else if(str[i]>=33&&str[i]<=47)
{
if(str[i]=='*')
{
push(pop()*pop());
}
if(str[i]=='+')
{
push(pop()+pop());
}
if(str[i]=='-')
{
a=pop();
b=pop();
push(b-a);
}
}
}
printf("%d",pop());
return 0;
}
*/
/*
#include <stdio.h>
int stack[201];
int top=-1;
void push(int data)
{
stack[++top]=data;
}
int pop()
{
if(top==-1) return 0;
return stack[top--];
}
int main()
{
int n,i,j=0,sum=0,c=0;
char str[50];
scanf("%d ",&n);
for(i=0; i<n; i++)
{
gets(str);
if(str[1]=='u')
{
for(j=6;str[j]!=' ';j++)
{
c=c*10+str[j]-48;
}
push(c);
c=0;
}
else if(str[0]=='t')
{
if(top==-1) printf("-1\n");
else printf("%d\n",stack[top]);
}
else if(str[0]=='p')
{
pop();
}
else if(str[0]=='s')
{
printf("%d\n",top+1);
}
else if(str[0]=='e')
{
if(top==-1)
{
printf("true\n");
}
else
{
printf("false\n");
}
}
}
return 0;
}
*/
/*
#include <stdio.h>
void f(int n)
{
if(n==0) return ;
f((n-1)/26);
printf("%c",(n-1)%26+65);
}
int main()
{
int n;
scanf("%d",&n);
f(n);
return 0;
}
*/
/*
#include <stdio.h>
int a[10001];
int n, i, j, temp;
int main() {
scanf("%d", &n);
for (i=1; i<=n; i++)
scanf("%d", &a[i]);
for(i=1; i<n; i++)
{
for(j=1; j<=n-i; j++)
{
if (a[j] > a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
for (i = 1; i <= n; i++)
printf("%d\n", a[i]);
return 0;
}
*/
/*
#include <stdio.h>
int a[10001];
int n, i, j, temp, min;
int main()
{
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (i=1; i<n; i++)
{
min=i;
for (j=i+1; j<=n; j++)
{
if(a[min]>a[j])
{
min=j;
}
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
for (i=1; i<=n; i++)
printf("%d\n", a[i]);
return 0;
}
*/
/*
#include <stdio.h>
int a[10001];
int n, i, j, temp, key;
int main() {
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (i=2; i<=n; i++)
{
key=a[i];
for(j=i-1;j>0&&key<a[j];j--)
{
a[j+1]=a[j];
}
a[j+1]=key;
}
for (i=1; i<=n; i++)
printf("%d\n", a[i]);
return 0;
}
*/
/*
#include <stdio.h>
int a[101];
int n,i,j,max=0,temp=0;
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(i=n;i>=2;i--)
{
max=i;
for(j=i-1;j>=1;j--)
{
if(a[max]>a[j])
{
max=j;
}
}
temp=a[i];
a[i]=a[max];
a[max]=temp;
}
for(i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
return 0;
}
*/