private static class Scanner {
  private DataInputStream din = new DataInputStream(System.in);
  private int size = 1 << 16;
  private byte[] buffer = new byte[size];
  private int pos;
  private int len;
  public Scanner() throws IOException {
    fillBuffer();
    pos--;
  }
  private void fillBuffer() throws IOException {
    len = din.read(buffer);
    pos = 0;
  }
  private char advance() throws IOException {
    if (++pos == len) {
      fillBuffer();
    }
    return (char) buffer[pos];
  }
  public String nextLine() throws IOException {
    StringBuffer sb = new StringBuffer(size);
    char c;
    while ((c = advance()) != '\n' && c != '\r') {
      sb.append(c);
    }
    if (c == '\r') {
      advance();
    }
    return sb.toString();
  }
  public int nextInt() throws IOException {
    return (int) nextLong();
  }
  public long nextLong() throws IOException {
    char c;
    while ((c = advance()) == ' ' || c == '\n' || c == '\r');
    boolean negative = c == '-';
    long num = negative ? 0 : c - '0';
    while ((c = advance()) >= '0' && c <= '9') {
      num *= 10;
      num += c - '0';
    }
    pos--;
    return negative ? -num : num;
  }
}