/*
#include <stdio.h>
int main
{
int n;
scanf ("%d",&n);
}
*/
/*
include <stdio.h>
int main ()
{
int n,i,j;
scanf("%d",&n);
for(i=0; i<n; i++)
{
for(j=n-1; j>i; j--)
{
printf(" ");
}
for(j=0;j<n;j++)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main ()
{
int h,k,i,j;
char d;
scanf ("%d %d %c",&h,&k,&d);
for(i=0; i<h; i++)
{
if(d=='R')
{
for(j=h-1; j>i; j--)
{
printf(" ");
}
for(j=0; j<k; j++)
{
printf("*");
}
}
else
{
for(j=0; j<i; j++)
{
printf(" ");
}
for(j=0; j<k; j++)
{
printf("*");
}
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n,i,j,S=0,s=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
s=0;
for(j=1;j<=i;j++)
{
s+=j;
}
S+=s;
}
printf("%d",S);
return 0;
}
*/
/*
#include <stdio.h>
int main ()
{
int i,j,n,m;
scanf ("%d %d",&n,&m);
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(i==1&&j==1||i==1&&j==n||i==m&&j==1||i==m&&j==n)
{
printf("+");
}
else if(i==1&&j!=1||i==1&&j!=n||i==m&&j!=1&&i==m&&j!=n)
{
printf("-");
}
else if(i!=1&&j==1||i!=1&&j==n||i!=m&&j==1&&i!=m&&j==n)
{
printf("|");
}
else
{
printf(" ");
}
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
double s,e,i,sum=0;
for(i=1;i<=5;i++)
{
scanf("%lf %lf",&s,&e);
if(e-s>1 && e-s<5) {
sum += e-s-1;
}
else if(e-s>=5)
{
sum+=4;
}
}
if(sum>=15)
{
printf("%d",(int)(0.95*sum*10000));
}
else if(sum<=5)
{
printf("%d",(int)(1.05*sum*10000));
}
else
{
printf("%d",(int)(sum*10000));
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n,i,t,k;
scanf("%d",&n);
for(i=1; ;i++)
{
if(n<i*i)
{
break;
}
}
t=i-1;
k=n-t*t;
printf("%d %d",k,t);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int N,i,a,sum=0,c=1;
scanf ("%d",&N);
for(i=1;i<=N;i++)
{
scanf("%d",&a);
if(a==1)
{
sum=sum+c;
c++;
}
else
{
c=1;
}
}
printf("%d",sum);
return 0;
}
*/
//배열 : array
/*
#include <stdio.h>
int main()
{
//int arr[5]={0};
//int arr1[5]={1,2,3,4,5};
int arr[5],i;
for(i=0;i<5;i++)
{
scanf("%d",&arr[i]);
}
for(i=0;i<3;i++)
{
printf("%d ",arr[i]);
}
}
*/
/*
#include <stdio.h>
int main()
{
int arr[1000]={},n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
for(i=n-1;i>=0;i--)
{
printf("%d ",arr[i]);
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int arr[100]={},i,k;
scanf("%d",&k);
for(i=0;i<k;i++)
{
scanf("%d",&arr[i]);
}
for(i=0;i<k;i++)
{
printf("%d\n",arr[i]);
}
for(i=0;i<k;i++)
{
printf("%d\n",arr[i]);
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int N,arr[50]={},sum=0,a,i;
scanf ("%d",&N);
a=N*(1+N)/2;
for(i=0;i<N-1;i++)
{
scanf("%d",&arr[i]);
sum+=arr[i];
}
printf("%d",a-sum);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n,arr[1000]={},i,j;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
for(i=0;i<n;i++)
{
printf("%d: ",i+1);
for(j=0;j<n;j++)
{
if(i!=j)
{
if(arr[i]>arr[j])
{
printf("> ");
}
else if(arr[i]<arr[j])
{
printf("< ");
}
else
{
printf("= ");
}
}
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main ()
{
int arr[11]={},i,k;
for(i=1;i<=10;i++)
{
scanf("%d",&arr[i]);
}
scanf("%d",&k);
printf("%d",arr[k]);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int arr[1001],i,n,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
}
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j++)
{
printf("%d ",arr[j]);
}
for(j=1;j<i;j++)
{
printf("%d ",arr[j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n,arr[35]={},i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("%d",arr[i]%2);
}
return 0;
}
*/