//import java.util.*;
//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=0; j<=i; j++) {
// System.out.print("*");
// }
// System.out.println();
// }
// for (int i=1; i<n; i++) {
// for (int j=i; j<n;j++) {
// 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();
//
// for(int i=0; i<(n+1)/2; i++) {
// for(int j=i; j<(n/2); j++) {
// System.out.print(" ");
// }
// for(int j=0; j<=i*2; j++) {
// System.out.print("*");
// }
//
// System.out.println();
// }
//
//// for (int i=0; i<n; i++) {
//// for (int j=2; j<3; i--) {
//// System.out.print(" ");
//// }
//// for (int j=4; j>3; i++) {
//// System.out.print(" ");
//// }
//// for (int j=3; j<=3; j--) {
//// System.out.print("*");
//// }
//// for(int j=4; j>4; j++) {
//// 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();
//
//
//
// for(int i=0; i<n; i++) {
//
// for(int j=0; j<n; j++) {
// System.out.printf("(%d %d)\t", i, j);
//
// }
//
// 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 k = t.nextInt();
//
// for (int i=0; i<n;i++) {
// for (int j=0; j<n; j++) {
// if (i==0||i==n-1||j==0||j==n-1|| (i+j+1)%k==0 ) {
// 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);
//
// String s = t.next();
// System.out.println(s);
//
// for(int i=0; i<s.length(); i++) {
// System.out.println(s.charAt(i));
// }
// int n = t.nextInt();
// int a[] = new int[n];
// // a[0] ~ a[n-1]
//
// for(int i=0; i<n; i++) {
// a[i] = t.nextInt();
// }
//
// for(int i=0; i<n; i++) {
// System.out.println(a[i]);
// }
//
// }
//}
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
// int n = t.nextInt();
// int a[] = new int[n];
//
// for (int i=0; i<n; i ++) {
// a[i] = t.nextInt();
// }
// for (int i=n-1; i>=0; i--) {
// System.out.print(a[i]+" ");
// }
//
//
// }
//}
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
//
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
// int a[] = new int [n];
//
// for (int i=0; i<n; i++) {
// a[i] = t.nextInt();
// }
// for (int i=0; i<n; i++) {
// System.out.println(a[i]);
// }
// for (int i=0; i<n; i++) {
// System.out.println(a[i]);
// }
// }
//}
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
//
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
// int a[] = new int [n];
// int sum = 0;
//
// for (int i=0 ;i<n-1; i++) {
// a[i] = t.nextInt();
// sum += a[i];
// }
// for (int i=0; i<1; i++) {
// System.out.println((((n+1)*n)/2)-sum);
// }
// }
//}
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
//
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
// int a[] = new int [n];
//
//
// for (int i=0; i<n; i++) {
// a[i] = t.nextInt();
// }
// for (int i=0; i<n; i++) {
// for(int k=0; k<n;k++) {
// System.out.print(a[ (i+k)%n ]+" ");
// }
// 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 a[] = new int [n];
//
// for (int i=0; i<n; i++) {
// a[i] = t.nextInt();
// }
// for (int i=0; i<n; i++) {
// System.out.print(i+1+": ");
// for (int k=0; k<n; k++) {
// if(i!=k) {
// if (a[i] < a[k]) {
// System.out.print("< ");
// }
// else if (a[i]>a[k]) {
// System.out.print("> ");
// }
// else if (a[i]==a[k]) {
// System.out.print("= ");
// }
// }
// }
// System.out.println();
// }
// }
//}