/*
#include <stdio.h>
#include <stdlib.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);
}
*/
/*
#include <stdio.h>
int main()
{
int n, k, i, b=0;
scanf("%d", &n);
for(i=0 ; i<n ; i++)
{
scanf("%d", &k);
if(k>b)
{
b=k;
}
}
printf("%d", b);
}
*/
/*
#include <stdio.h>
int main()
{
int k, h, km, hm;
scanf("%d %d", &k, &h);
if(k%2==0)
{
km = (k/2)*10 ;
}
else
{
km = (k/2)+1 ;
}
if(h%2==0)
{
hm = (h/2)*10 ;
}
else
{
hm = (h/2)+1 ;
}
printf("%d", km+hm);
}
*/
/*
#include <stdio.h>
int main()
{
int n, k, i, sum=1;
scanf("%d %d", &n, &k);
for(i=0 ; i<k ; i++)
{
sum *= n;
}
printf("%d", sum);
}
*/
/*
#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("(%d,%d)\t", i, j);
}
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");
}
}
*/
/*
#include <stdio.h>
int main()
{
int n, i, j;
scanf("%d", &n);
for(i=0 ; i<n ; i++)
{
for(j=0 ; j<n ; j++)
{
if(i==0||i==n-1)
{
printf("*");
}
else
{
if(j==0||j==n-1)
{
printf("*");
}
else
{
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++)
{
if(i==0||i==n-1||j==0||j==n-1||i==j||n-1-i==j)
{
printf("*");
}
else
{
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++)
{
if(i==0||i==n-1||j==0||j==n-1||i==j||n-1-i==j||n/2==j||n/2==i)
{
printf("*");
}
else
{
printf(" ");
}
}
printf("\n");
}
}
*/
//#include <stdio.h>
//
//int main()
//{
// int n, k, i, j;
//
// scanf("%d %d", &n, &k);
//
// for(i=0 ; i<n ; i++)
// {
// for(j=0 ; j<n ; j++)
// {
// if(i==0 || i==n-1 || j==0 || j==n-1 || (j+i+1)%k==0 )
// {
// printf("*");
// }
// else
// {
// printf(" ");
// }
// }
// printf("\n");
// }
//}
/*
#include<stdio.h>
int main() {
int i, j, n;
scanf("%d", &n);
for(i=0; i<n; i++) {
for(j=0; j<=i; j++){
printf("*");
}
printf("\n");
}
}
*/
/*
#include <stdio.h>
int main()
{
int i, j, n;
scanf("%d", &n);
for(i=0 ; i<n ; i++)
{
for(j=0 ; j<n-i ; j++)
{
printf("*");
}
printf("\n");
}
}
*/
/*
#include <stdio.h>
int main()
{
int i, j, n;
scanf("%d", &n);
for(i=0 ; i<n ; i++)
{
for(j=0 ; j<i ; j++)
{
printf(" ");
}
for(j=0 ; j<n-i ; j++)
{
printf("*");
}
printf("\n");
}
}
*/
/*
#include <stdio.h>
int main()
{
int i, j, n;
scanf("%d", &n);
for(i=1 ; i<n+n ; i++)
{
if(i<=n)
{
for(j=0 ; j<i ; j++)
{
printf("*");
}
}
else
{
for(j=0 ; j<n-(i-n) ; j++)
{
printf("*");
}
}
printf("\n");
}
}
*/
//#include <stdio.h>
//
//int main()
//{
// int i, j, k, n;
//
// scanf("%d", &n);
//
// for(i=0 ; i<=n/2 ; i++)
// {
// for(j=0 ; j<(n/2)-i ; j++)
// {
// printf(" ");
// }
// for(k=0 ; k<=i*2 ; k++)
// {
// printf("*");
// }
//
// printf("\n");
// }
//}
/*
#include<stdio.h>
int main() {
int i, n, k, j;
scanf("%d", &n);
for(i=0; i<=n/2; i++) {
for(j=n/2; j>i; j--) {
printf(" ");
}
for(j=0; j<=i*2; j++) {
printf("*");
}
printf("\n");
}
}
*/