//import java.util.Scanner;
//public class Main
//{
// public static void main(String[] args)
// {
// Scanner t = new Scanner(System.in);
// int n = t.nextInt();
//
// for(int i=0; i<n; i++)
// {
// for(int j=1; j<=n; j++)
// if(i == 0 || i == n-1 || i!=0 && j==1 || i!=0 && j==n)
// {
// System.out.print("*");
// }
// else
// {
// System.out.print(" ");
// }
// System.out.println();
// }
// }
//}
//import java.util.Scanner;
//
//public class Main
//{
// public static void main(String[] args)
// {
// Scanner t = new Scanner(System.in);
// int n = t.nextInt();
// for (int i = 0; i <= n; i++)
// {
// if(i % 2 != 0 )
// {
// for (int j = 0; j < i; j++)
// {
// System.out.print("*");
// }
// System.out.println();
// }
// else
// {
// for (int j = i+2; j <= n; j+=2)
// {
// System.out.print(" ");
// }
// }
// }
// }
//}
//import java.util.Scanner;
//public class Main
//{
// public static void main(String[] args)
// {
// Scanner t = new Scanner(System.in);
// int n = t.nextInt();
// int min = 1;
// int max = n;
// for(int i=0; i<n; i++)
// {
// for(int j=1; j<=n; j++)
// if(i == 0 || i == n-1 || i!=0 && j==1 || i!=0 && j==n)
// {
// System.out.print("*");
// }
// else if (j==min || j==max || j==min && min==max)
// {
// System.out.print("*");
// }
// else
// {
// System.out.print(" ");
// }
// min++;
// max--;
// System.out.println();
// }
// }
//}
//import java.util.Scanner;
//
//public class Main
//{
// public static void main(String[] args)
// {
// Scanner t = new Scanner(System.in);
// int n= t.nextInt();
// int k = t.nextInt();
//
// for (int i = 1; i <= n; i++)
// {
// for (int j = 1; j <= n; j++)
// {
// if(i==1||i==n||j==1||j==n)
// {
// System.out.print("*");
// }
// else if(k == 1)
// {
// System.out.print("*");
// }
// else if((i+j) % k == 1)
// {
// System.out.print("*");
// }
// else
// {
// System.out.print(" ");
// }
// }
// System.out.println();
// }
// }
//}
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
// int arr[] = new int[n];
//
// for(int i=0; i<n; i++) {
// arr[i] = t.nextInt();
// }
// }
//}
import java.util.*;
//public class Main
//{
// public static void main(String[] args)
// {
// Scanner t =new Scanner(System.in);
//
//
// int n = t.nextInt();
// int arr[] = new int[n];
// for(int i=0; i<n; i++)
// {
// arr[i] = t.nextInt();
// }
//
// for(int i=n-1; i>=0; i--)
// {
// System.out.print(arr[i]+" ");
// }
//
// }
//
//}
//import java.util.*;
//
//public class Main
//{
// public static void main(String[] args)
// {
// Scanner t =new Scanner(System.in);
//
//
// int n = t.nextInt();
// int arr[] = new int[n];
// for(int i=0; i<n; i++)
// {
// arr[i] = t.nextInt();
// }
//
// for(int i=n-1; i>=0; i--)
// {
// System.out.print(arr[i]+" ");
// }
//
// }
//
//}
//import java.util.*;
//
//public class Main
//{
// public static void main(String[] args)
// {
// Scanner t = new Scanner(System.in);
// int arr[] = new int[10];
// for(int i=0; i<10; i++)
// {
// arr[i] = t.nextInt();
// }
// int n = t.nextInt();
//
// System.out.println(arr[n-1]);
// }
//}