//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 k = 0; k < i; k++) {
// System.out.print(" ");
// }
// for (int j = n; j > i; j--) {
// System.out.print("*");
// }
// System.out.println();
// }
//
// }
//} //1355 : 삼각형 출력하기 3
//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 = 1; i <= (n/2)+1; i++) {
// for(int p = 0; p < (n / 2)+1 - i; p++) {
// System.out.print(" ");
// }
// for(int k = 0; k < i * 2 - 1; k++) {
// System.out.print("*");
// }
// System.out.println();
// }
// }
//} //1358 : 삼각형 출력하기 5
//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 = 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((i + j -1)%k == 0) {
// System.out.print("*");
// } else System.out.print(" ");
// }
// System.out.println();
// }
// }
//} //1369 : 빗금 친 사각형 출력하기
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
// int sum = 0;
//
// for(int i = 1; i <= n; i++) {
// for(int j = 1; j <= i; j++) {
// sum+=j;
// }
// }
// System.out.println(sum);
// }
//} //1378 : 수열의 합
//1차원 배열(array)
/*
* 배열 array
* 같은 자료형의 변수를 여러 개 만들 때
*
* 기본 자료형 배열 int float char ...
* 클래스 배열 String
*/
//import java.util.*;
//
//class Main{
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
// //정수 배열 (int)
// int n = t.nextInt();
// int[] arr = new int[n];
// // arr[0] ~ arr[49] 총 50칸
// for(int i=0;i<50;i++)
// arr[i] = t.nextInt();
//
// int[] arr1 = new int[51];
// // arr1[0] ~ arr1[50]
//
// double[] arr2 = new double[30];
// }
//}
//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 < arr.length; i++) {
// arr[i] = t.nextInt();
// }
//
// for(int i = 0; i < arr.length; i++) {
// for(int j = i; j < n; j++) {
// System.out.print(arr[j] + " ");
// }
// for(int j = 0; j < i; j++) {
// System.out.print(arr[j] + " ");
// }
// System.out.println();
// }
// }
//} //1405 : 숫자 로테이션
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int a[] = new int[10];
//
// for(int i = 0; i < a.length; i++) {
// a[i] = t.nextInt();
// }
// int b = t.nextInt();
// System.out.println(a[b - 1]);
// }
//} //1409 : 기억력 테스트 1
//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[100];
// int i = 0;
//
// if(n == 0) {
// System.out.println("0");
// }
// while(n > 0) {
// a[i] = n % 2;
// n /= 2;
// i++;
// }
// for(int j = i - 1; j >= 0; j--) {
// System.out.print(a[j]);
// }
// }
//} //1416 : 2진수 변환
//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 i = 0;
//
// for(i=0;i<n;i++) {
// a[i] = t.nextInt();
// }
//
//
// for (i = 0; i < a.length; i++) {
// System.out.print(i + 1 + ": ");
// for (int j = 0; j < a.length; j++) {
// if (i == j) {
// continue;
// }
// if (a[i] == a[j]) {
// System.out.print("= ");
// } else if (a[i] < a[j]) {
// System.out.print("< ");
// } else if (a[i] > a[j]) {
// System.out.print("> ");
// }
// }
// System.out.println();
// }
// }
//} //1440 : 비교