/*
#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int n,k,t;
scanf("%d", &n);
for(k=0; k*k<=n; k++)
{
}
printf("%d %d", n-(k-1)*(k-1), k-1);
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int i,j ;
for(i=0; i<3; i++) {
for(j=0; j<3; j++) {
printf("(%d,%d)\t", i,j);
}
printf("\n");
}
}
*/
/*
#include<stdio.h>
int main()
{
int a,b,c,d,e;
scanf("%d %d", &a, &b);
for(c=a; c<=b; c++)
{
for(e=1; e<=9; e++)
{
printf("%d*%d=%d\n", c, e, e*c);
}
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int a,b,n;
scanf("%d", &n);
for(a=1; a<=n; a++)
{
for(b=1; b<=n; b++)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int a,b,n;
scanf("%d", &n);
for(a=1; a<=n; a++)
{
for(b=1; b<=n; b++)
{
if((a==1 || a==n)||(b==1 || b==n))
{
printf("*");
}
else
{
printf(" ");
}
}
printf("\n");
}
}
*/
/*
#include<stdio.h>
int main()
{
int a,b,n;
scanf("%d", &n);
for(a=1; a<=n; a++)
{
for(b=1; b<=a; b++)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int n,a,b,sum=0;
scanf("%d", &n);
for(a=1; a<=n; a++)
{
for(b=1; b<=a; b++)
{
sum+=b;
}
}
printf("%d", sum);
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int a,b,n;
scanf("%d", &n);
for(a=1; a<=n; a++)
{
for(b=1; b<=n; b++)
{
if((a==1||a==n)||(b==1||b==n)||(b==a||a+b==n+1))
{
printf("*");
}
else
{
printf(" ");
}
}
printf("\n");
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int a,b,n;
scanf("%d", &n);
for(a=1; a<=n; a++)
{
for(b=1; b<=n; b++)
{
if((a==1||a==n)||(b==1||b==n)||(a==b||a+b==n+1)||(n/2+1==b||(n/2+1==a)))
{
printf("*");
}
else
{
printf(" ");
}
}
printf("\n");
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int a,b,k,n;
scanf("%d %d", &n, &k);
for(a=1; a<=n; a++)
{
for(b=1; b<=n; b++)
{
if((a==1||a==n)||(b==1||b==n)||((a+b-1)%k==0))
{
printf("*");
}
else
{
printf(" ");
}
}
printf("\n");
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int a,b,k;
scanf("%d", &k);
for(a=1; a<=6; a++)
{
for(b=1; b<=6; b++)
{
if(a+b==k)
{
printf("%d %d\n", a,b);
}
}
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int a,b,c,n;
scanf("%d", &n);
for(a=n; a>=0; a--)
{
for(c=a; c<n; c++)
{
printf(" ");
}
for(b=a-1; b>=0; b--)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int a,b,c,d,n;
scanf("%d", &n);
for(a=1; a<=n/2+1; a++)
{
for(c=a; c<n/2+1; c++)
{
printf(" ");
}
for(b=0; b<a*2-1; b++)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
#include<stdio.h>
int main() {
int arr[10] = {0};
int i, n, k;
scanf("%d", &n);
for(i=0; i<n; i++) {
scanf("%d", &arr[i]);
}
for(i=0; i<n; i++){
printf("%d ", arr[i]);
}
}
*/
/*
#include<stdio.h>
int main()
{
int a[1005]={0},n,c,b,d;
scanf("%d", &n);
for(c=0; c<n; c++)
{
scanf("%d", &a[c]);
}
for(c=n-1; c>=0; c--)
{
printf("%d ", a[c]);
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int k,a[105]={0},b;
scanf("%d", &k);
for(b=0; b<k; b++)
{
scanf("%d", &a[b]);
}
for(b=0; b<k; b++)
{
printf("%d\n", a[b]);
}
for(b=0; b<k; b++)
{
printf("%d\n", a[b]);
}
return 0;
}
*/