import java.io.*
import java.math.*
import java.util.*

class FastReader {
  private val BUFFER_SIZE: Int = 1 shl 12
  private var LENGTH: Int = -1
  private val din: DataInputStream 
  private val buffer: ByteArray = ByteArray(BUFFER_SIZE)
  private var bufferPointer: Int = 0
  private var bytesRead: Int = 0
  private var buf: CharArray = CharArray(0)
  constructor(inputStream: InputStream) {
    din = DataInputStream(inputStream)
  }
  constructor(fileName: String) {
    din = DataInputStream(FileInputStream(fileName))
  }
  fun nextInt(): Int {
    var ret: Int = 0
    var c: Byte
    do {
      c = read()
    } while (c <= 32)
    var neg: Boolean = c == 45.toByte()
    if (neg) c = read()
    do {
      ret = ret * 10 + c - 48
      c = read()
    } while (c >= 48)
    if (neg) return -ret
    return ret
  }
  fun nextLong(): Long {
    var ret: Long = 0L
    var c: Byte
    do {
      c = read()
    } while (c <= 32)
    var neg: Boolean = c == 45.toByte()
    if (neg) c = read()
    do {
      ret = ret * 10 + c - 48
      c = read()
    } while (c >= 48)
    if (neg) return -ret
    return ret
  }
  fun nextDouble(): Double {
    var ret: Double = 0.0
    var div: Double = 1.0
    var c: Byte
    do {
      c = read()
    } while (c <= 32)
    var neg: Boolean = c == 45.toByte()
    if (neg) c = read()
    do {
      ret = ret * 10 + c - 48
      c = read()
    } while (c >= 48)
    if (c == 46.toByte()) {
      c = read()
      while (c >= 48) {
        div *= 10
        ret += (c - 48) / div
        c = read()
      }
    }
    if (neg) return -ret
    return ret
  }
  fun nextChar(): Char {
    var c: Byte
    do {
      c = read()
    } while (c <= 32)
    return c.toChar()
  }
  fun next(): String {
    var c: Byte
    var cnt: Int = 0
    do {
      c = read()
    } while (c <= 32)
    do {
      buf[cnt++] = c.toChar()
      c = read()
    } while (c > 32)
    return String(buf, 0, cnt)
  }
  fun nextLine(): String {
    while (bufferPointer > 0 && buffer[bufferPointer - 1] == 13.toByte())
      read()
    var c: Byte
    var cnt: Int = 0
    c = read()
    while (c != 10.toByte() && c != 0.toByte()) {
      if (c != 13.toByte()) buf[cnt++] = c.toChar()
      c = read()
    }
    return String(buf, 0, cnt)
  }
  fun setLength(len: Int) {
    LENGTH = len
    buf = CharArray(len)
  }
  fun hasNext(): Boolean {
    while (peek() > -1 && peek() <= 32) read()
    return peek() > -1
  }
  fun hasNextLine(): Boolean {
    while (peek() == 13.toByte()) read()
    return peek() > -1
  }
  private fun fillBuffer() {
    bufferPointer = 0
    bytesRead = din.read(buffer, bufferPointer, BUFFER_SIZE)
    if (bytesRead == -1) buffer[0] = -1
  }
  private fun read(): Byte {
    if (bufferPointer == bytesRead) fillBuffer()
    return buffer[bufferPointer++]
  }
  private fun peek(): Byte {
    if (bufferPointer == bytesRead) fillBuffer()
    return buffer[bufferPointer]
  }
  fun close() {
    din.close()
  }
}
