/*
#include <stdio.h>
int main()
{
long long int a;
int m,d,n,i;
scanf("%lld %d %d %d", &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 i, j, a;
scanf("%d", &a);
for(i = 0; i<a; i++)
{
for (j = 0; j<a ; j++)
{
printf("*");
}
printf("\n");
}
}
*/
/*
int main()
{
int n,i,j,a;
scanf("%d",&a);
for(i = 0; i<a; i++)
{
for(j = 0; j<a ; j++)
{
if(i==0 || i==a-1 || j==0 || j==a-1)
{
printf("*");
}
else
{
printf(" ");
}
}
printf("\n");
}
}
*/
/*
int main()
{
int n,i,j,a;
scanf("%d", &a);
for(i=0; i<a; i++)
{
for(j=0; j<a; j++)
{
if(i==0 || i==a-1 || j==0 || j==a-1 || i==j || i+j==a-1)
printf("*");
else
{
printf(" ");
}
}
printf("\n");
}
return 0;
}
*/
/*
int main()
{
int n,i,j,a;
scanf("%d",&a);
for(i=0; i<a; i++)
{
for(j=0; j<a; j++)
{
if(i==0 || i==a-1 || j==0 || j==a-1 || i==a/2 || i==j || i+j==a-1 || j==a/2)
printf("*");
else
{
printf(" ");
}
}
printf("\n");
}
return 0;
}
*/
/*
int main()
{
int a,i,j;
scanf("%d",&a);
for(i=0; i<a; i++)
{
for(j=0; j<=i; j++)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
int main()
{
int a,j,i;
scanf("%d", &a);
for(i=a-1; i>=0; i--)
{
for(j=0; j<=i; j++)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
int main()
{
int a,j,i;
scanf("%d", &a);
for(i=0; i<a; i++)
{
for(j=0; j<i; j++)
{
printf(" ");
}
for(j=i; j<a; j++)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
int main()
{
int a,j,i;
scanf("%d", &a);
for(i=0; i<a-1; i++)
{
for(j=0; j<=i; j++)
{
printf("*");
}
printf("\n");
}
for(i=a-1; i>=0; i--)
{
for(j=0; j<=i; j++)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/