/*
import java.util.*; //#include stdio.h
// 자동완성 : ctrl + space
//compile : ctrl+ F11
public class Main {
public static void main(String[] args) {
//자료형
int a=5;
long a1; //long long int
float b;
double c;
char d='a';
String e="안녕"; //문자열
System.out.println("hello world");
System.out.println("a 변수의 값은 "+a+"입니다.");
System.out.println("그리고 e의 값은 "+e+"입니다.");
//syso + ctrl + space
/////////////////////////////////////
Scanner sc = new Scanner(System.in); //스캐너 생성
int x;
x = sc.nextInt();
int y = sc.nextInt();
float z = sc.nextFloat();
String str= sc.next(); // 한 단어
String str1 = sc.nextLine(); //한 줄
System.out.println(y);
//////////////////////////////////
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String e= sc.next();
System.out.println(e);
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
System.out.println(a + " " + b);
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[]args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
System.out.println(a + " " + a + " " + a);
if(a==1){
int cnt=0;
}
else if(a==3)
{
}
for(int i=0;i<5;i++) {
System.out.println(i);
}
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[]args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
if(a<=10)
{
System.out.println("정상");
}
else if(a<=20)
{
System.out.println("과체중");
}
else if(a>20)
{
System.out.println("비만");
}
}
}
*/
/*
--------------------------------------------------------------------------------
import java.util.*;
public class Main {
public static void main(String[]args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
if(a>=11&&a<=20)
{
System.out.println(a + "th");
}
else if(a==1||(a-1)%10==0)
{
System.out.println(a + "st");
}
else if(a==2||(a-2)%10==0)
{
System.out.println(a + "nd");
}
else if(a==3||(a-3)%10==0)
{
System.out.println(a + "rd");
}
else
{
System.out.println(a + "th");
}
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[]args) {
Scanner sc = new Scanner(System.in);
int a= sc.nextInt();
int b= sc.nextInt();
int i ;
int y=1;
for(i=1; i<=100; i++)
{
if(a*i==b)
{
System.out.println(a + "*" + i + "=" + b);
y--;
}
else if(b*i==a)
{
System.out.println(b + "*" + i + "=" + a);
y--;
}
else if(i==100&&y==1)
{
System.out.println("none");
}
}
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[]args) {
Scanner sc = new Scanner(System.in);
int x=0;
int a = sc.nextInt();
x=a;
int b = sc.nextInt();
x=x+b;
int c = sc.nextInt();
x=x+c;
int d = sc.nextInt();
x=x+d;
if(x==1)
{
System.out.println("도");
}
else if(x==2)
{
System.out.println("개");
}
else if(x==3)
{
System.out.println("걸");
}
else if(x==4)
{
System.out.println("윷");
}
else if(x==0)
{
System.out.println("모");
}
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
if (c < a + b) {
if (a == b && b == c)
System.out.println("정삼각형");
else if (a == b || b == c || c == a)
System.out.println("이등변삼각형");
else if (a * a + b * b == c * c)
System.out.println("직각삼각형");
else
System.out.println("삼각형");
} else
System.out.println("삼각형아님");
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
if(a==0)
{
System.out.println("0");
}
else if(a>0)
{
System.out.println("양수");
}
else
{
System.out.println("음수");
}
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
int x=0;
x=a+b+c;
if(x>1000)
{
if((x/100-10)%2==1)
{
System.out.println("그럭저럭");
}
else
{
System.out.println("대박");
}
}
else
{
if((x/100)%2==1)
{
System.out.println("그럭저럭");
}
else
{
System.out.println("대박");
}
}
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr1[] = new int[n]; //int n개 배열 생성
//위 코드는 c에서 int arr1[n];과 같습니다!
int [] arr = new int[50];
//int arr[50]; (x)
int map[][] = new int[50][50]; //이차원배열도 마찬가지!
//////////////////////////////////////////////////////
int array[] = {5,1,4,8,7};
// 배열의 길이 알아내기 가능!!array.length
for(int i=0;i<array.length;i++)
{
System.out.println(array[i]);
}
for(int k:array)
{
System.out.println(k);
}
//문자열
//str[0] (x)-> str.charAt(0)
String str;
str=sc.next(); //한 단어
str=sc.nextLine(); // 한 줄 입력받기
System.out.println(str.charAt(0));
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String a= sc.next();
int i, x=0, y=0;
for(i=0; i<a.length(); i++)
{
if(a.charAt(i)=='(')
{
x++;
}
else if(a.charAt(i)==')')
{
y++;
}
}
System.out.println(x + " " + y);
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String a = sc.nextLine();
int i, x=0;
for(i=0; i<a.length();i++)
{
if(a.charAt(i)=='l'&&a.charAt(i+1)=='o'&&a.charAt(i+2)=='v'&a.charAt(i+3)=='e')
{
x++;
}
}
System.out.println(x);
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String a = sc.nextLine();
// if (a.charAt(0) == 'I' && a.charAt(1) == 'O' && a.charAt(2) == 'I') {
if (a.equals("IOI")) {
System.out.println("IOI is the International Olympiad in Informatics.");
} else
{
System.out.println("I don't care.");
}
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String a = sc.nextLine();
//System.out.println("welcome!" + " " + a);
System.out.printf("%c",a.charAt(0)+2);
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String a = sc.nextLine();
int i;
for(i=0; i<a.length(); i++)
{
System.out.printf("%c",a.charAt(i)+2);
}
System.out.println("\n");
for(i=0; i<a.length(); i++)
{
System.out.printf("%c",a.charAt(i)*7%80+48);
}
}
}
*/