import java.io.*;

public class FastScanner {
    private final Reader in;
    private final char[] buffer = new char[1 << 16]; // 64KB buffer
    private int len = 0, pos = 0;
    private boolean eof = false;

    public FastScanner(InputStream input) {
        this.in = new InputStreamReader(input);
    }

    public FastScanner(String fileName) throws IOException {
        this.in = new InputStreamReader(new FileInputStream(fileName), "UTF-8");
    }

    private void fillBuffer() throws IOException {
        if (eof) return;
        len = in.read(buffer);
        if (len == -1) {
            eof = true;
        }
        pos = 0;
    }

    private boolean isWhitespace(char c) {
        return c <= ' ';
    }

    public boolean hasNext() throws IOException {
        skipWhitespace();
        return !eof;
    }

    public String next() throws IOException {
        skipWhitespace();
        if (eof) return null;
        StringBuilder sb = new StringBuilder();
        while (true) {
            if (pos >= len) {
                fillBuffer();
                if (eof) break;
            }
            char c = buffer[pos];
            if (isWhitespace(c)) break;
            sb.append(c);
            pos++;
        }
        return sb.toString();
    }

    public boolean hasNextInt() throws IOException {
        skipWhitespace();
        if (eof) return false;

        int p = pos;
        if (p >= len) fillBuffer();
        if (eof) return false;

        char c = buffer[p];
        return (c == '-' || Character.isDigit(c));
    }

    public int nextInt() throws IOException {
        skipWhitespace();
        int sign = 1, res = 0;
        if (pos >= len) fillBuffer();
        if (buffer[pos] == '-') {
            sign = -1;
            pos++;
        }
        while (true) {
            if (pos >= len) {
                fillBuffer();
                if (eof) break;
            }
            char c = buffer[pos];
            if (!Character.isDigit(c)) break;
            res = res * 10 + (c - '0');
            pos++;
        }
        return res * sign;
    }

    private void skipWhitespace() throws IOException {
        while (true) {
            if (pos >= len) {
                fillBuffer();
                if (eof) return;
            }
            if (!isWhitespace(buffer[pos])) break;
            pos++;
        }
    }
}