/*
#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i, n, k, c = 0;
scanf("%d",&n);
for (i=0; i<n; i++)
{
scanf("%d",&k);
if (k%2==0)
c++;
}
printf("%d",c);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a, b, c, n, i;
scanf("%d %d %d %d",&a,&b,&c,&n);
for (i=1; i<=n-1; i++)
{
a = a*b+c;
}
printf("%d",a);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i, n, k, d, max = 0;
scanf("%d",&n);
for (i=0; i<n; i++){
scanf("%d",&k);
if (max<k){
max = k;}
}
printf("%d",max);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i, n;
scanf("%d",&n);
for (i=1; i<=n; i++){
if (n%i==0){
printf("%d ",i);
}
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i,n,c = 0;
scanf("%d",&n);
for(i=2; i<=n; i++)//1234567 n=7..
{
if(n%i==0){
c++;
}
}
if(c==1){
printf("prime");
}
else {
printf("not prime");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i, n, k, a = 1;
scanf("%d %d",&n,&k);
for(i=0; i<k; i++)//123456789
{
a = a*n;
}
printf("%d",a);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i, n, a = 1;
scanf("%d",&n);
for (i=n; i>=1; i--)//5! = 5 4 3 2 1
{
a = a*i;
}
printf("%d",a);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i, a, b, c, d, e, max = -1000000, min = 1000000, k;
for (i=0; i<5; i++){
scanf("%d",&k);
if(max < k){
max = k;
}
if(min > k){
min = k;
}
}
printf("%d \n%d",max,min);
}
*/
/*
#include <stdio.h>
int main()
{
int k, h,sum = 0;
scanf("%d %d",&k,&h);
if(k%2==0)
{
sum+=k*5;
}
if(h%2==0)
{
sum+=h*5;
}
if(k%2==1)
{
sum+=(k+1)/2;
}
if(h%2==1)
{
sum+=(h+1)/2;
}
printf("%d",sum);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i, n, k;
scanf("%d",&n);
for (i=1; i<=n; i++)
{
scanf("%d",&k);
if(i == 1)
{
printf("%d ",k);
}
if(i==n/2+1)
{
printf("%d ",k);
}
if(i == n)
{
printf("%d ",k);
}
}return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i, n, cnt=1;
scanf("%d",&n);
for (i=1; i<=13; i++){
n/=10;
if(n>0) cnt++;
else break;
}
printf("%d",cnt);
}
*/
/*
#include <stdio.h>
int main()
{
int i,j,n;
scanf("%d",&n);
for(i=1; i<=n; i++){
for(j=1; j<=n; j++){
printf("*");
}
printf("\n");
}
return 0;
}
*/