//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
// int num[] = new int[n];
// int count = 0;
// int res = 0;
//
// for(int i = 0; i < num.length; i++) {
// num[i] = t.nextInt();
// }
// for(int i = 0; i < num.length; i++) {
// if(num[i] == 1) {
// count++;
// }
// else {
// count = 0;
// }
// res += count;
// }
// System.out.println(res);
// }
//} //4626 : 점수 계산
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int c = t.nextInt();
// int stu[] = new int[23];
// int num = 0;
//
// for(int i = 0; i < c; i++) {
// num = t.nextInt();
// stu[num-1] += 1;
// }
// for(int i = 0; i < stu.length; i++) {
// System.out.print(stu[i] + " ");
// }
// }
//} //[기초-1차원배열] 이상한 출석 번호 부르기1
//문자열 String
// char str[50] 문자의 일차원배열 != 문자열
// String을 char arr[]로 변경해서 사용
//문자열끼리 비교할때는 ==대신 equals 사용해야한다!
//import java.util.*;
//public class Main{
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
// //String str = t.next();
// //char arr[] = str.toCharArray();
// //arr[5] (o)
//
// //str[5] (x)
// //str.charAt(5)
// //for(int i=0;i<str.length();i++)
// String s1 = "hello";
// String s2 = "hello";
//// if(s1==s2) { //같은 주소냐?
//// }
// // if(s1.equals(s2))
//
// //if(s1.equals(s2)) System.out.println("same");
// //System.out.print((int)s1.charAt(0));
//
// //System.out.println(s1.);
//
// String str = "hello world hi my name is ... ";
// String arr[] = str.split(" ");
// str.replace('h', 't');
// //str.replace("h", "t");
// //System.out.println(str);
// }
//}
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// String a = t.next();
// int length = a.length();
//
// for(int i = 0; i < length; i++) {
// System.out.printf("\'%c\'\n",a.charAt(i));
// }
// }
//} //[기초-입출력] 단어 1개 입력받아 나누어 출력하기(설명)
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int cnt1 = 0;
// int cnt2 = 0;
// String a = t.nextLine();
//
// for(int i = 0; i < a.length(); i++) {
// if(a.charAt(i) == '(')cnt1++;
// else if(a.charAt(i) == ')')cnt2++;
// }
// System.out.println(cnt1 + " " + cnt2);
// }
//} //1410 : 올바른 괄호 1 (괄호 개수 세기)
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// String a = t.nextLine();
// char b[] = a.toCharArray();
//
// for(int i = 0; i < b.length; i++) {
// if((int)b[i] > 96 && (int)b[i] < 123)b[i] -= 32;
// else if((int)b[i] > 64 && (int)b[i] < 91)b[i] +=32;
// }
// for(int i = 0; i <b.length; i++) {
// System.out.print(b[i]);
// }
// }
//} //1295 : 알파벳 대소문자 변환
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
//
// String input = t.nextLine();
//
// System.out.print(input);
// }
//} //1133 : 공백이 있는 문자열 입출력
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// String a = t.next();
// String b = t.next();
//
// if(a.length() < b.length())System.out.println(a + " " + b);
// else if(a.length() > b.length()) System.out.println(b + " " + a);
// else {
// System.out.println(a + " "+ b); //여기 code
// }
// }
//} //1754 : 큰 수 비교