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

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

    public boolean isDigit(char c) {
 		return Character.isDigit(c) || c == '-';
    }

    public MyScanner (InputStream is) {
    	try {
        	br = new BufferedReader(new InputStreamReader(is, "utf-8"));
        } catch(UnsupportedEncodingException e){
        	System.out.println("UnsupportedEncodingException");
        }
    }

    public MyScanner (String line) {
        br = new StringReader(line);
    }
   // 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 nextLine() 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 (isDigit(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 hasNextLine() throws IOException {
        return hasNextChar();
    }

    public boolean hasNextInt() throws IOException {
        skipBlank();
        if (hasNextChar() && isDigit(nextChar())) {
        	pos--;
        	return true;
        }
        return false;
    }

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

    public void close() throws IOException {
    	br.close();
    }
}