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;
    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 char nextchar() throws IOException {
        if (pos>=len){
            readBuffer();
        }
        return buffer[pos++];
    }

    public boolean hasNextChar() throws IOException{
        nextchar();
        pos--;
        return !EOF;
    }
    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 int nextInt() throws IOException {
        skipBlank();
        StringBuilder sb = new StringBuilder();
        char c;
        while (hasNextChar()){
            c = nextchar();
            if (Character.isDigit(c))
            {
                sb.append(c);
            }
            else {
                if (!Character.isWhitespace(c))
                {
                    throw new InputMismatchException("");
                }
                break;
            }
        }
        try {
            return Integer.parseInt(sb.toString());
        } catch (NumberFormatException e) {
            throw new InputMismatchException();
        }
    }
    private void skipBlank() throws IOException{
        while (true) {
        if (!hasNextChar() || !Character.isWhitespace(nextchar())) break;
    }
        pos--;
    }
}