import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.InputMismatchException;

public  class FastScanner {
    private BufferedReader br;
    private int pos, len;
    private char[] buffer = new char[4096];
    private boolean EOF = false;
    private StringBuilder sb = new StringBuilder();

    public FastScanner (InputStream is) {
        br = new BufferedReader(new InputStreamReader(is));
    }
   // public FastScanner(String string)
    private void readBuffer() throws IOException{
        len = br.read(buffer);
        while (len == 0){
            len = br.read(buffer);
        }
        if (len == -1)
        {
            EOF = true;
        }
        pos = 0;
    }

    public String readLine() throws IOException{
        StringBuilder sb = new StringBuilder();
        char c;
        while(hasNextChar()){
            c = nextChar();
            if (c == '\n')
            {
                break;
            }
            if (c != '\r') {
                sb.append(c);
            }
        }
        return sb.toString();
    }

    public char nextChar() throws IOException {
        if (pos >= len){
            readBuffer();
        }
        return buffer[pos++];
    }

    public int nextInt() throws IOException {
        skipBlank();
        sb = new StringBuilder();
        char c;
        while (hasNextChar()){
            c = nextChar();
            if (Character.isDigit(c) || c == '-')
            {
                sb.append(c);
            }
            else {
                break;
            }
        }
        try {
            return Integer.parseInt(sb.toString());
        } catch (NumberFormatException e) {
            throw new InputMismatchException();
        }
    }

    public boolean hasNextChar() throws IOException{
        nextChar();
        pos--;
        return !EOF;
    }

    public boolean hasNextInt() throws IOException{
        try {
        	int next = nextInt();
        	pos -= sb.toString().length();
        } catch (InputMismatchException e) {
        	return false;
        }
        return true;
    }

    private void skipBlank() throws IOException{
        while (true) {
        if (!hasNextChar() || !Character.isWhitespace(nextChar())) break;
    }
        pos--;
    }
}