import java.util.*;
import java.io.*;
import java.math.*;
public class Homework {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	public static void main(String[] args) throws IOException{

	}
    static String next() throws IOException {
    	while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine().trim());
    	return st.nextToken();
    }
    static long readLong() throws IOException {
    	return Long.parseLong(next());
	}
    static int readInt() throws IOException {
    	return Integer.parseInt(next());
    }
    static short readShort() throws IOException{
    	return Short.parseShort(next());
    }
    static double readDouble() throws IOException {
        return Double.parseDouble(next());
    }
    static char readCharacter() throws IOException {
        return next().charAt(0);
    }
    static String readLine() throws IOException {
        return br.readLine().trim();
    }
}