/*
#include <stdio.h>
int main()
{
int i;
for(i = 1; i <= 100; i++)
{
printf("%d ", i);
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n, i;
scanf("%d", &n);
for(i = 1; i <= n; i++)
{
printf("%d ", i);
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a, b, t, i;
scanf("%d %d", &a, &b);
if(a > b)
{
t = a;
a = b;
b = t;
}
for(i = a; i <= b; i++)
{
printf("%d ", i);
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
char a, b, i;
scanf("%c %c", &a, &b);
for(i = a; i <= b; i++)
{
printf("%c ", i);
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
double a, b, t, i;
scanf("%lf %lf", &a, &b);
if(a > b)
{
t = a;
a = b;
b = t;
}
for(i = a; i <= b; i+=0.01)
{
printf("%.2lf ", i);
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n, i;
scanf("%d", &n);
for(i = 0; i < n; i++)
{
printf("*");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a, b, i;
scanf("%d %d", &a, &b);
for(i = a; i <= b; i++)
{
if(i % 2 != 0)
{
printf("%d ", i);
}
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n, sum, i;
scanf("%d", &n);
sum = 0;
for(i = 1; i <= n; i++)
{
sum = sum + i;
}
printf("%d", sum);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n, sum, i;
scanf("%d", &n);
sum = 0;
for(i = 1; i <= n; i++)
{
if(i % 2 == 0)
{
sum = sum + i;
}
}
printf("%d", sum);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a, b, sum, i;
scanf("%d %d", &a, &b);
sum = 0;
for(i = a; i <= b; i++)
{
if(i % 3 == 0)
{
sum = sum + i;
}
}
printf("%d", sum);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n, sum, i, k;
scanf("%d", &n);
sum = 0;
for(i = 0; i < n; i++)
{
scanf("%d", &k);
sum = sum + k;
}
printf("%d", sum);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n, sum, i, k;
scanf("%d", &n);
sum = 0;
for(i = 0; i < n; i++)
{
scanf("%d", &k);
if(k % 5 ==0)
{
sum = sum + k;
}
}
printf("%d", sum);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n, count, i, k;
scanf("%d", &n);
count = 0;
for(i = 0; i < n; i++)
{
scanf("%d", &k);
if(k % 2 == 0)
{
count = count + 1;
}
}
printf("%d", count);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n, i;
scanf("%d", &n);
for(i = 1; i <= 9; i++)
{
printf("%d*%d=%d\n", n, i, n*i);
}
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; i++)
{
a = a * b + c;
}
printf("%d", a);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n, count, i;
scanf("%d", &n);
count = 0;
for(i = 1; i <= n; i++)
{
if(i % 10 == 1)
{
count = count + 1;
}
}
printf("%d", count);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a, d, n, i;
scanf("%d %d %d", &a, &d, &n);
for(i = 1; i < n; i++)
{
a = a + d;
}
printf("%d", a);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
long long int a, r, n, i;
scanf("%lld %lld %lld", &a, &r, &n);
for(i = 1; i < n; i++)
{
a = a * r;
}
printf("%lld", a);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
long long int a, m, d, n, i;
scanf("%lld %lld %lld %lld", &a, &m, &d, &n);
for(i = 1; i < n; i++)
{
a = a * m + d;
}
printf("%lld", a);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a, b, result, i;
result = 0;
scanf("%d %d", &a, &b);
for(i = a; i <= b; i++)
{
if(i % 2 == 0)
{
printf("-%d", i);
result = result - i;
}
else
{
printf("+%d", i);
result = result + i;
}
}
printf("=%d", result);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a, b, result, i;
scanf("%d %d", &a, &b);
result = 0;
for(i = a; i <= b - 1; i++)
{
if(i % 2 == 0)
{
printf("-%d+", i);
result = result - i;
}
else
{
printf("%d", i);
result = result + i;
}
}
if(i % 2 == 0)
{
printf("-%d", i);
result = result - i;
}
else
{
printf("%d", i);
result = result + i;
}
printf("=%d", result);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n, t, k;
scanf("%d", &n);
for(t = 0; t * t <= n; t++)
{
k = n - t * t;
}
printf("%d %d", k, t - 1);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n;
int i, j;
scanf("%d", &n);
for(i=0; i<n; i++)
{
for(j=0; j<=i; j++)
{
printf("*");
}
printf("\n");
}
}
*/
/*
#include <stdio.h>
int main()
{
int n, i, j;
scanf("%d", &n);
for(i = 0; i < n ; i++)
{
for(j = 0; j < n; j++)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n, i, j;
scanf("%d", &n);
for(i = 0; i < n; i++)
{
printf("*");
}
printf("\n");
for(i = 0; i < n - 2; i++)
{
printf("*");
for(j = 0; j < n - 2; j++)
{
printf(" ");
}
printf("*\n");
}
for(i = 0; i < n; i++)
{
printf("*");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n, i, j;
scanf("%d", &n);
for(i = 0; i < n; i++)
{
printf("*");
}
printf("\n");
for(i = 0; i < n - 2 ; i++)
{
printf("*");
for(j = 0; j < n - 2; j++)
{
if(j == i || j == n - 3 - i)
{
printf("*");
}
else
{
printf(" ");
}
}
printf("*\n");
}
for(i = 0; i < n; i++)
{
printf("*");
}
return 0;
}
*/