import java.util.Scanner;
import java.util.StringTokenizer;
//import java.util.Scanner;
//interface ShapeInterface {
// void enter();
// void delete();
// void view();
// void shutdown();
// default void printLine() {
// System.out.println("enter(1), delete(2), view(3), shutdown(4)>>");
// }
//}
//
//class Shape{
// public void draw() {
// System.out.println("Shape");
// }
//}
//class Line extends Shape {
// public void draw() {
// System.out.println("Line");
// }
//}
//class Rect extends Shape {
// public void draw() {
// System.out.println("Rect");
// }
//}
//class Circle extends Shape{
// public void draw() {
// System.out.println("Circle");
// }
//}
//
//class Graphic extends Shape implements ShapeInterface {
//Scanner t = new Scanner(System.in);
//
// @Override
// public void enter() {
// // TODO Auto-generated method stub
// System.out.println("Shape Type Line(1), Rect(2), Circle(3)>>");
// int enter = t.nextInt();
// }
//
// @Override
// public void delete() {
// // TODO Auto-generated method stub
// System.out.println("location of the shape>>");
// int delete = t.nextInt();
// }
//
// @Override
// public void view() {
// // TODO Auto-generated method stub
//
// }
//
// @Override
// public void shutdown() {
// // TODO Auto-generated method stub
// System.out.println("System shutting down...");
// }
//}
//
//public class Main {
// static void paint(Shape p) {
// p.draw();
// }
// public static void main(String[] args) {
// Graphic graphic = new Graphic();
// for(::) {
// }
// }
//}
//abstract class Calculator {
// public abstract int add(int a, int b);
// public abstract int subtract(int a,int b);
// public abstract double average(int[] a);
//}
//
//public class Main extends Calculator {
//
// @Override
// public int add(int a, int b) {
// // TODO Auto-generated method stub
// return a+b;
// }
//
// @Override
// public int subtract(int a, int b) {
// // TODO Auto-generated method stub
// return a-b;
// }
//
// @Override
// public double average(int[] a) {
// // TODO Auto-generated method stub
// double sum = 0;
// for (int i =0; i<a.length; i++)
// sum+=a[i];
// return sum/a.length;
// }
// public static void main(String[] args) {
// Calculator c = new Main();
// System.out.println(c.add(2, 3));
// System.out.println(c.subtract(2, 3));
// System.out.println(c.average(new int [] {2,3,4}));
// }
//}
//class Point {
// private int x,y;
// public Point(int x, int y) {
// this.x = x;
// this.y = y;
// }
//}
//public class Main {
// public static void main(String[] args) {
// Point p = new Point (2,3);
// System.out.println(p.getClass().getName());
// System.out.println(p.hashCode());
// System.out.println(p.toString());
// }
//}
//class Point {
// private int x,y;
// public Point (int x, int y) {
// this.x = x;
// this.y = y;
// }
// public String toString() {
// return "Point(" + x + "," + y + ")";
// }
//}
//public class Main {
// public static void main(String[] args) {
// Point a = new Point (2,3);
// System.out.println(a.toString());
// System.out.println(a);
// }
//}
//class Point {
// private int x,y;
// public Point(int x, int y) {
// this.x = x;
// this.y = y;
// }
// public boolean equals(Object obj) {
// Point p = (Point)obj;
// if (x==p.x&&y==p.y)
// return true;
// else
// return false;
// }
//}
//public class Main {
// public static void main(String[] args) {
// Point a = new Point (2,3);
// Point b = new Point (2,3);
// Point c = new Point (3,4);
// if (a==b)
// System.out.println("a==b");
// if (a.equals(b))
// System.out.println("a is equal to b");
// if (a.equals(c))
// System.out.println("a is equal to c");
// }
//}
//class Rect {
// private int w,h;
// public Rect(int w,int h) {
// this.w = w;
// this.h = h;
// }
// public boolean equals(Object obj) {
// Rect p = (Rect)obj;
// if (w*h == p.w*p.h)
// return true;
// else
// return false;
// }
//}
//public class Main {
// public static void main(String[] args) {
// Rect a = new Rect(2,3);
// Rect b = new Rect(3,2);
// Rect c = new Rect(3,4);
// if(a.equals(b))
// System.out.println("a is equal to b");
// if(a.equals(c))
// System.out.println("a is equal to c");
// if(b.equals(c))
// System.out.println("b is equal to c");
// }
//}
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// String number = "10";
// System.out.println(Integer.parseInt(number));
//
// }
//}
//public class Main {
// public static void main(String[] args) {
// System.out.println(Character.toLowerCase('A'));
// char c1='4', c2='F';
// if(Character.isDigit(c1))
// System.out.println(c1 + " is a number");
// if(Character.isAlphabetic(c2))
// System.out.println(c2 + " is English");
//
// System.out.println(Integer.parseInt("28"));
// System.out.println(Integer.toString(28));
// System.out.println(Integer.toBinaryString(28));
// System.out.println(Integer.bitCount(28));
//
// Integer i = Integer.valueOf(28);
// System.out.println(i.doubleValue());
//
// Double d = Double.valueOf(28);
// System.out.println(d.toString());
// System.out.println(Double.parseDouble("3.14"));
//
// boolean b = (4>3);
// System.out.println(Boolean.toString(b));
// System.out.println(Boolean.parseBoolean("false"));
// }
//}
//public class Main {
// public static void main(String[] args) {
// String a = new String (" C#");
// String b = new String (",C++ ");
//
// System.out.println(a + "의 길이는 " + a.length());
// System.out.println(a.contains("#"));
//
// a = a.concat(b);
// System.out.println(a);
//
// a = a.trim();
// System.out.println(a);
//
// a = a.replace("C#", "Java");
// System.out.println(a);
//
// String s[] = a.split(",");
// for (int i=0; i<s.length; i++)
// System.out.println("분리된 문자열" + i + ": " +s[i]);
//
// a = a.substring(5);
// System.out.println(a);
//
// char c = a.charAt(2);
// System.out.println(c);
// }
//}
//import java.util.StringTokenizer;
//public class Main {
// public static void main(String[] args) {
// String query = "name=kitae&addrseoul&age=21";
// StringTokenizer st = new StringTokenizer(query, "&");
//
// int n = st.countTokens();
// System.out.println("토큰개수 = " + n);
// while (st.hasMoreTokens()) {
// String token = st.nextToken();
// System.out.println(token);
// }
// }
//}
//public class Main{
// public static void main(String[] args) {
// System.out.println(Math.abs(-3.14));
// System.out.println(Math.sqrt(9.0));
// System.out.println(Math.exp(2));
// System.out.println(Math.round(3.14));
//
// System.out.print("This week's lucky numbers are ");
// for (int i = 0; i<5; i++)
// System.out.print((int) (Math.random()*45+1) + " ");
// }
//}
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int alphabet[] = new int[26];
// while(true) {
// String str = t.nextLine();
// if (str.equals(";"))
// break;
//
// for(int i=0; i<str.length(); i++) {
// char p;
// if(str.charAt(i) >= 'A' && str.charAt(i) <='Z') {
// p = (char) (str.charAt(i) + 32);
// alphabet[p-'a']++;
// }
// if(str.charAt(i)>= 'a' && str.charAt(i)<='z') {
// p = (char)str.charAt(i);
// alphabet[p-'a']++;
// }
// }
//
//
// }
//
// for (int i=0; i<26;i++) {
// System.out.print((char)('A'+i)+":"+alphabet[i]+'\t');
// for(int j=0; j<alphabet[i];j++) {
// System.out.print("-");
// }
// System.out.println();
// }
//
// }
//}