結果

問題 No.1298 OR XOR
ユーザー da_louis
提出日時 2020-11-27 21:32:02
言語 Kotlin
(2.1.0)
結果
AC  
実行時間 310 ms / 2,000 ms
コード長 29,298 bytes
コンパイル時間 28,844 ms
コンパイル使用メモリ 494,180 KB
実行使用メモリ 59,232 KB
最終ジャッジ日時 2024-07-26 11:45:08
合計ジャッジ時間 30,989 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:70:13: warning: 'appendln(Int): kotlin.text.StringBuilder /* = java.lang.StringBuilder */' is deprecated. Use appendLine instead. Note that the new method always appends the line feed character '\n' regardless of the system line separator.
            appendln(n)
            ^
Main.kt:103:48: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
    private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte()
                                               ^
Main.kt:103:62: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
    private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte()
                                                             ^
Main.kt:104:68: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
    private fun Byte.toNumVal() = if (this.isNumeric()) this - '0'.toByte() else error("$this is not numeric")
                                                                   ^
Main.kt:136:22: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
        if (b == '-'.toByte()) {
                     ^
Main.kt:162:22: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
        if (b == '-'.toByte()) {
                     ^
Main.kt:168:22: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
        if (b == '.'.toByte()) {
                     ^

ソースコード

diff #
プレゼンテーションモードにする

import java.io.ByteArrayInputStream
import java.io.ByteArrayOutputStream
import java.io.PrintStream
fun main() = if (localEnv && execChecker) checker() else contest276a()
fun contest276a() = solve()
@OptIn(ExperimentalStdlibApi::class)
private fun solve() = Messiah_contest276a(mod).exec {
    val n = readLong()
    val bitCount = n.countOneBits()
    if (bitCount <= 1) return@exec println("-1 -1 -1")
    var bitCountA = bitCount / 2
    var a = 0L
    var b = 0L
    var c = 0L
    var base = 1L
    for (bit in n.toString(2).reversed().map { it == '1' }) {
        if (bit) {
            if (bitCountA > 0) {
                a += base
                bitCountA--
            } else {
                b += base
            }
            c += base
        }
        base *= 2
    }
    val answer = "$a $b $c"
    println(answer)
}
private const val mod = 1_000_000_007
// region kokokara template dayo (^o^)
private const val execChecker = false
private val localEnv = "ENABLE_DEBUG_MODE_FOR_COMPETITIVE_PROGRAMING" in System.getenv()
private fun checker() = Messiah_contest276a(mod).exec {
    debugln("#######################################################")
    debugln("###############  executing check mode.  ###############")
    debugln("#######################################################")
    fun getOutPut(input: String, action: () -> Unit): String {
        System.setIn(ByteArrayInputStream(input.toByteArray()))
        val sysOut = ByteArrayOutputStream()
        System.setOut(PrintStream(sysOut))
        action()
        return sysOut.toString()
    }
    val wrongCases = mutableSetOf<List<String>>()
    while (wrongCases.size < 10) {
        /*
        examples
        val randomString = (1..20).map { ('a'..'z').random() }.joinToString("")
        val randomNum = Random.nextInt(0,2000)
         */
        val n = 0
        val input = buildString {
            appendln(n)
        }
        val solve = getOutPut(input, ::solve)
        val greedy = getOutPut(input, ::greedy)
        if (solve != greedy && wrongCases.add(listOf(solve, greedy))) {
            debugln("#################### wrong case: ${wrongCases.size} ####################")
            debugln("input:")
            debugln(input)
            debugln("solve:")
            debugln(solve)
            debugln("greedy:")
            debugln(greedy)
        }
    }
}
private fun greedy() = Messiah_contest276a(mod).exec {
    TODO()
}
@Suppress("ClassName", "unused", "FunctionName", "PropertyName")
private class Messiah_contest276a(mod: Int) {
    //////////////////////////////////////////////////
    // IO
    //////////////////////////////////////////////////
    private val input = System.`in`
    private val buffer = ByteArray(1024)
    private var pointer = 0
    private var bufferLength = 0
    private val sb = StringBuilder()
    private fun Byte.isPrintable() = this in 33..126
    private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte()
    private fun Byte.toNumVal() = if (this.isNumeric()) this - '0'.toByte() else error("$this is not numeric")
    private val lineSeparator: String = System.lineSeparator()
    private fun hasNextByte(): Boolean {
        return if (pointer < bufferLength) true else {
            pointer = 0
            bufferLength = input.read(buffer)
            bufferLength > 0
        }
    }
    private fun readByte(): Byte = if (hasNextByte()) buffer[pointer++] else -1
    private fun skipUnprintable() = run { while (hasNextByte() && !buffer[pointer].isPrintable()) pointer++ }
    private fun hasNext(): Boolean = run { skipUnprintable() }.run { hasNextByte() }
    private fun hasNextOrError() = if (!hasNext()) error("has no next element.") else Unit
    fun readString(): String {
        hasNextOrError()
        val sb = StringBuilder()
        var b = readByte()
        while (b.isPrintable()) {
            sb.appendCodePoint(b.toInt())
            b = readByte()
        }
        return sb.toString()
    }
    fun readLong(): Long {
        hasNextOrError()
        var n = 0L
        var negative = false
        var b = readByte()
        if (b == '-'.toByte()) {
            negative = true
            b = readByte()
        }
        if (!b.isNumeric()) error("$b is not numeric.")
        while (true) {
            when {
                b.isNumeric() -> n = n * 10 + b.toNumVal()
                b.toInt() == -1 || !b.isPrintable() -> return if (negative) -n else n
                else -> error("failed to parse. [n=$n, b=$b]")
            }
            b = readByte()
        }
    }
    fun readInt() = readLong()
        .let { if (it in Int.MIN_VALUE..Int.MAX_VALUE) it.toInt() else error("$it is not in range of Int.") }
    fun readIntAsIndex() = readInt().dec()
    fun readDouble(): Double {
        hasNextOrError()
        var n = 0.0
        var div = 1.0
        var negative = false
        var b = readByte()
        if (b == '-'.toByte()) {
            negative = true
            b = readByte()
        }
        do n = n * 10 + b.toNumVal()
        while (run { b = readByte() }.run { b.isNumeric() })
        if (b == '.'.toByte()) {
            while (run { b = readByte() }.run { b.isNumeric() })
                n += b.toNumVal() / (run { div *= 10 }.run { div })
        }
        return if (negative) -n else n
    }
    fun readString(size: Int): Array<String> = Array(size) { readString() }
    @Suppress("UNUSED_PARAMETER")
    fun readChars(h: Int, w: Int): Array<CharArray> = Array(h) { readString().toCharArray() }
    fun readLong(size: Int): LongArray = LongArray(size) { readLong() }
    fun readLong(h: Int, w: Int): Array<LongArray> = Array(h) { readLong(w) }
    fun readInt(size: Int): IntArray = IntArray(size) { readInt() }
    fun readInt(h: Int, w: Int): Array<IntArray> = Array(h) { readInt(w) }
    fun readIntAsIndex(size: Int): IntArray = IntArray(size) { readIntAsIndex() }
    fun readIntAsIndex(h: Int, w: Int): Array<IntArray> = Array(h) { readIntAsIndex(w) }
    fun readDouble(size: Int): DoubleArray = DoubleArray(size) { readDouble() }
    fun readDouble(h: Int, w: Int): Array<DoubleArray> = Array(h) { readDouble(w) }
    fun readBooleanWithSeparator(size: Int, trueElement: String): BooleanArray =
        BooleanArray(size) { readString() == trueElement }
    fun readBooleanWithSeparator(h: Int, w: Int, trueElement: String): Array<BooleanArray> =
        Array(h) { readBooleanWithSeparator(w, trueElement) }
    @Suppress("UNUSED_PARAMETER")
    fun readBooleanWithoutSeparator(size: Int, trueElement: Char): BooleanArray =
        readString().map { it == trueElement }.toBooleanArray()
    fun readBooleanWithoutSeparator(h: Int, w: Int, trueElement: Char): Array<BooleanArray> =
        Array(h) { readBooleanWithoutSeparator(w, trueElement) }
    fun println(): Unit = run { sb.append(lineSeparator) }
    fun print(any: Any): Unit = run { sb.append(any.toString()) }
    fun println(any: Any): Unit = run { sb.append(any.toString() + lineSeparator) }
    fun flush() = run { kotlin.io.println(sb); sb.clear() }
    fun debugln(any: Any): Unit = run { if (localEnv) System.err.println(any) }
    fun debugln(): Unit = run { if (localEnv) System.err.println() }
    fun debugln(action: () -> Unit): Unit = run { if (localEnv) action() }
    fun exec(action: Messiah_contest276a.() -> Unit) {
        var t: Throwable? = null
        Thread(null, { action() }, "sandbox.test.solve", 128 * 1024 * 1024)
            .apply { setUncaughtExceptionHandler { _, t1 -> t = t1 } }
            .apply { start() }.join()
        t?.let { throw it }
        kotlin.io.print(sb)
    }
    fun readLine(): Nothing = error("readLine is disabled.")
    //////////////////////////////////////////////////
    // Mod
    //////////////////////////////////////////////////
    class ModIntFactory(private val mod: Int) {
        private val ma = ModArithmetic.of(mod)
        /**
         * ModInt を生成する.
         * 生成された ModInt は、[value] をファクトリ生成時に指定した mod で割った余りを持つ.
         */
        fun create(value: Long): ModInt {
            val v = (value % mod).let { if (it < 0) it + mod else it }
            return if (ma is ModArithmetic.ModArithmeticMontgomery) {
                ModInt(ma.generate(v))
            } else {
                ModInt(v.toInt())
            }
        }
        inner class ModInt(private var rawValue: Int) {
            val mod = this@ModIntFactory.mod
            val value: Int
                get() = if (ma is ModArithmetic.ModArithmeticMontgomery) {
                    ma.reduce(rawValue.toLong())
                } else {
                    rawValue
                }
            operator fun plus(mi: ModInt) = ModInt(ma.add(rawValue, mi.rawValue))
            operator fun minus(mi: ModInt) = ModInt(ma.sub(rawValue, mi.rawValue))
            operator fun times(mi: ModInt) = ModInt(ma.mul(rawValue, mi.rawValue))
            operator fun div(mi: ModInt) = ModInt(ma.div(rawValue, mi.rawValue))
            /** (this * inv) % mod = 1 を満たすような inv を ModInt として生成して返す. */
            fun inv() = ModInt(ma.inv(rawValue))
            /** (this ^ [b]) % mod の結果を ModInt として生成して返す. */
            fun pow(b: Long) = ModInt(ma.pow(rawValue, b))
            /** this を this + [mi] に変更する */
            fun addAsg(mi: ModInt): ModInt {
                rawValue = ma.add(rawValue, mi.rawValue)
                return this
            }
            /** this を this - [mi] に変更する */
            fun subAsg(mi: ModInt): ModInt {
                rawValue = ma.sub(rawValue, mi.rawValue)
                return this
            }
            /** this を this * [mi] に変更する */
            fun mulAsg(mi: ModInt): ModInt {
                rawValue = ma.mul(rawValue, mi.rawValue)
                return this
            }
            /** this を this / [mi] に変更する */
            fun divAsg(mi: ModInt): ModInt {
                rawValue = ma.div(rawValue, mi.rawValue)
                return this
            }
            override fun toString(): String {
                return value.toString()
            }
            override fun equals(other: Any?): Boolean {
                if (other is ModInt) {
                    return mod == other.mod && value == other.value
                }
                return false
            }
            override fun hashCode(): Int {
                return (1 * 37 + mod) * 37 + value
            }
        }
        internal interface ModArithmetic {
            fun mod(): Int
            fun add(a: Int, b: Int): Int
            fun sub(a: Int, b: Int): Int
            fun mul(a: Int, b: Int): Int
            fun div(a: Int, b: Int): Int {
                return mul(a, inv(b))
            }
            fun inv(a: Int): Int
            fun pow(a: Int, b: Long): Int
            class ModArithmetic1 : ModArithmetic {
                override fun mod(): Int {
                    return 1
                }
                override fun add(a: Int, b: Int): Int {
                    return 0
                }
                override fun sub(a: Int, b: Int): Int {
                    return 0
                }
                override fun mul(a: Int, b: Int): Int {
                    return 0
                }
                override fun inv(a: Int): Int {
                    throw ArithmeticException("divide by zero")
                }
                override fun pow(a: Int, b: Long): Int {
                    return 0
                }
            }
            class ModArithmetic2 : ModArithmetic {
                override fun mod(): Int {
                    return 2
                }
                override fun add(a: Int, b: Int): Int {
                    return a xor b
                }
                override fun sub(a: Int, b: Int): Int {
                    return a xor b
                }
                override fun mul(a: Int, b: Int): Int {
                    return a and b
                }
                override fun inv(a: Int): Int {
                    if (a == 0) throw ArithmeticException("divide by zero")
                    return a
                }
                override fun pow(a: Int, b: Long): Int {
                    return if (b == 0L) 1 else a
                }
            }
            class ModArithmetic998244353 : ModArithmetic {
                private val mod = 998244353
                override fun mod(): Int {
                    return mod
                }
                override fun add(a: Int, b: Int): Int {
                    val res = a + b
                    return if (res >= mod) res - mod else res
                }
                override fun sub(a: Int, b: Int): Int {
                    val res = a - b
                    return if (res < 0) res + mod else res
                }
                override fun mul(a: Int, b: Int): Int {
                    return (a.toLong() * b % mod).toInt()
                }
                override fun inv(a: Int): Int {
                    var va = a
                    var b = mod
                    var u: Long = 1
                    var v: Long = 0
                    while (b >= 1) {
                        val t = (va / b).toLong()
                        va -= (t * b).toInt()
                        val tmp1 = va
                        va = b
                        b = tmp1
                        u -= t * v
                        val tmp2 = u
                        u = v
                        v = tmp2
                    }
                    u %= mod.toLong()
                    if (va != 1) {
                        throw ArithmeticException("divide by zero")
                    }
                    return (if (u < 0) u + mod else u).toInt()
                }
                override fun pow(a: Int, b: Long): Int {
                    var vb = b
                    if (vb < 0) throw ArithmeticException("negative power")
                    var res: Long = 1
                    var pow2 = a.toLong()
                    var idx: Long = 1
                    while (vb > 0) {
                        val lsb = vb and -vb
                        while (lsb != idx) {
                            pow2 = pow2 * pow2 % mod
                            idx = idx shl 1
                        }
                        res = res * pow2 % mod
                        vb = vb xor lsb
                    }
                    return res.toInt()
                }
            }
            class ModArithmetic1000000007 : ModArithmetic {
                private val mod = 1000000007
                override fun mod(): Int {
                    return mod
                }
                override fun add(a: Int, b: Int): Int {
                    val res = a + b
                    return if (res >= mod) res - mod else res
                }
                override fun sub(a: Int, b: Int): Int {
                    val res = a - b
                    return if (res < 0) res + mod else res
                }
                override fun mul(a: Int, b: Int): Int {
                    return (a.toLong() * b % mod).toInt()
                }
                override fun div(a: Int, b: Int): Int {
                    return mul(a, inv(b))
                }
                override fun inv(a: Int): Int {
                    var va = a
                    var b = mod
                    var u: Long = 1
                    var v: Long = 0
                    while (b >= 1) {
                        val t = (va / b).toLong()
                        va -= (t * b).toInt()
                        val tmp1 = va
                        va = b
                        b = tmp1
                        u -= t * v
                        val tmp2 = u
                        u = v
                        v = tmp2
                    }
                    u %= mod.toLong()
                    if (va != 1) {
                        throw ArithmeticException("divide by zero")
                    }
                    return (if (u < 0) u + mod else u).toInt()
                }
                override fun pow(a: Int, b: Long): Int {
                    var vb = b
                    if (vb < 0) throw ArithmeticException("negative power")
                    var res: Long = 1
                    var pow2 = a.toLong()
                    var idx: Long = 1
                    while (vb > 0) {
                        val lsb = vb and -vb
                        while (lsb != idx) {
                            pow2 = pow2 * pow2 % mod
                            idx = idx shl 1
                        }
                        res = res * pow2 % mod
                        vb = vb xor lsb
                    }
                    return res.toInt()
                }
            }
            class ModArithmeticMontgomery(mod: Int) : ModArithmeticDynamic(mod) {
                private val negInv: Long
                private val r2: Long
                private val r3: Long
                fun generate(x: Long): Int {
                    return reduce(x * r2)
                }
                fun reduce(x: Long): Int {
                    var vx = x
                    vx = vx + (vx * negInv and 0xffffffffL) * mod ushr 32
                    return (if (vx < mod) vx else vx - mod).toInt()
                }
                override fun mul(a: Int, b: Int): Int {
                    return reduce(a.toLong() * b)
                }
                override fun inv(a: Int): Int {
                    var va = a
                    va = super.inv(va)
                    return reduce(va * r3)
                }
                override fun pow(a: Int, b: Long): Int {
                    return generate(super.pow(a, b).toLong())
                }
                init {
                    var inv: Long = 0
                    var s: Long = 1
                    var t: Long = 0
                    for (i in 0..31) {
                        if (t and 1 == 0L) {
                            t += mod.toLong()
                            inv += s
                        }
                        t = t shr 1
                        s = s shl 1
                    }
                    val r = (1L shl 32) % mod
                    negInv = inv
                    r2 = r * r % mod
                    r3 = r2 * r % mod
                }
            }
            class ModArithmeticBarrett(mod: Int) : ModArithmeticDynamic(mod) {
                private val mh: Long
                private val ml: Long
                private fun reduce(x: Long): Int {
                    var vx = x
                    var z = (vx and mask) * ml
                    z = (vx and mask) * mh + (vx ushr 32) * ml + (z ushr 32)
                    z = (vx ushr 32) * mh + (z ushr 32)
                    vx -= z * mod
                    return (if (vx < mod) vx else vx - mod).toInt()
                }
                override fun mul(a: Int, b: Int): Int {
                    return reduce(a.toLong() * b)
                }
                companion object {
                    private const val mask = 0xffffffffL
                }
                init {
                    /**
                     * m = floor(2^64/mod)
                     * 2^64 = p*mod + q, 2^32 = a*mod + b
                     * => (a*mod + b)^2 = p*mod + q
                     * => p = mod*a^2 + 2ab + floor(b^2/mod)
                     */
                    val a = (1L shl 32) / mod
                    val b = (1L shl 32) % mod
                    val m = a * a * mod + 2 * a * b + b * b / mod
                    mh = m ushr 32
                    ml = m and mask
                }
            }
            open class ModArithmeticDynamic(val mod: Int) : ModArithmetic {
                override fun mod(): Int {
                    return mod
                }
                override fun add(a: Int, b: Int): Int {
                    val sum = a + b
                    return if (sum >= mod) sum - mod else sum
                }
                override fun sub(a: Int, b: Int): Int {
                    val sum = a - b
                    return if (sum < 0) sum + mod else sum
                }
                override fun mul(a: Int, b: Int): Int {
                    return (a.toLong() * b % mod).toInt()
                }
                override fun inv(a: Int): Int {
                    var va = a
                    var b = mod
                    var u: Long = 1
                    var v: Long = 0
                    while (b >= 1) {
                        val t = (va / b).toLong()
                        va -= (t * b).toInt()
                        val tmp1 = va
                        va = b
                        b = tmp1
                        u -= t * v
                        val tmp2 = u
                        u = v
                        v = tmp2
                    }
                    u %= mod.toLong()
                    if (va != 1) {
                        throw ArithmeticException("divide by zero")
                    }
                    return (if (u < 0) u + mod else u).toInt()
                }
                override fun pow(a: Int, b: Long): Int {
                    var vb = b
                    if (vb < 0) throw ArithmeticException("negative power")
                    var res = 1
                    var pow2 = a
                    var idx: Long = 1
                    while (vb > 0) {
                        val lsb = vb and -vb
                        while (lsb != idx) {
                            pow2 = mul(pow2, pow2)
                            idx = idx shl 1
                        }
                        res = mul(res, pow2)
                        vb = vb xor lsb
                    }
                    return res
                }
            }
            companion object {
                fun of(mod: Int): ModArithmetic {
                    return when {
                        mod <= 0 -> throw IllegalArgumentException()
                        mod == 1 -> ModArithmetic1()
                        mod == 2 -> ModArithmetic2()
                        mod == 998244353 -> ModArithmetic998244353()
                        mod == 1000000007 -> ModArithmetic1000000007()
                        mod and 1 == 1 -> ModArithmeticMontgomery(mod)
                        else -> ModArithmeticBarrett(mod)
                    }
                }
            }
        }
    }
    val modArithmetic = ModIntFactory.ModArithmetic.of(mod)
    fun Int.plusMod(b: Int): Int = modArithmetic.add(this, b)
    fun Int.minusMod(b: Int): Int = modArithmetic.sub(this, b)
    fun Int.timesMod(b: Int): Int = modArithmetic.mul(this, b)
    fun Int.divMod(b: Int): Int = modArithmetic.div(this, b)
    fun Int.invMod(): Int = modArithmetic.inv(this)
    fun Int.powMod(b: Long): Int = modArithmetic.pow(this, b)
    val mod: Int get() = modArithmetic.mod()
    //////////////////////////////////////////////////
    // Misc
    //////////////////////////////////////////////////
    /**
     * `n.indices()` is sugar syntax of `0 until n`.
     */
    val Int.indices: IntRange get() = 0 until this
    /**
     * `[index] in [this]` is sugar syntax of `index in 0 until [this]`.
     */
    operator fun Int.contains(index: Int): Boolean = index in this.indices
    /**
     * `[this].mapIndices { transform }` is sugar syntax of `(0 until [this]).map{ transform(it) }`.
     */
    inline fun <R> Int.mapIndices(transform: (Int) -> R): List<R> = this.indices.map(transform)
    /**
     * `[this].mapIndices(x) { transform }` is sugar syntax of
     * `(0 until [this]).map{ y1-> (0 until [x]).map { x1-> transform(y1,x1) } }`.
     */
    inline fun <R> Int.mapIndices(x: Int, transform: (Int, Int) -> R): List<List<R>> =
        this.mapIndices { y1 -> x.mapIndices { x1 -> transform(y1, x1) } }
    /**
     * `[this].mapIndices(x) { transform }` is sugar syntax of
     * `(0 until [this]).map{ y1-> (0 until [x]).map { x1-> transform(y1,x1) } }`.
     */
    inline fun <R> Int.flatMapIndices(x: Int, transform: (Int, Int) -> R): List<R> =
        this.indices.flatMap { y1 -> x.mapIndices { x1 -> transform(y1, x1) } }
    /**
     * `[this].forEachIndices { transform }` is sugar syntax of `(0 until [this]).map{ transform(it) }`.
     */
    inline fun Int.forEachIndices(transform: (Int) -> Unit): Unit = this.indices.forEach(transform)
    /**
     * `[this].forEachIndices(x) { transform }` is sugar syntax of
     * `(0 until [this]).map{ y1-> (0 until [x]).map { x1-> transform(y1,x1) } }`.
     */
    inline fun Int.forEachIndices(x: Int, transform: (Int, Int) -> Unit): Unit =
        this.forEachIndices { y1 -> x.forEachIndices { x1 -> transform(y1, x1) } }
    /**
     * get characters numeric value.
     * e.g.: '0' to 0
     */
    fun Char.toNumericValue(): Int = this - '0'
    fun Char.caseToIndexedValue(): Int = this - 'a'
    //    fun Char.isLowerCase() = this in 'a'..'z'
    //
    //    fun Char.isUpperCase() = this in 'A'..'Z'
    /**
     * make triple. e.g.:`1 to 2 to 3`
     */
    infix fun <A, B, C> Pair<A, B>.to(c: C): Triple<A, B, C> = Triple(this.first, this.second, c)
    fun YesNo(b: Boolean): String = if (b) Yes else No
    val Yes = "Yes"
    val No = "No"
    fun YES_NO(b: Boolean): String = if (b) YES else NO
    val YES = "YES"
    val NO = "NO"
    fun IntArray.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
    fun LongArray.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
    fun CharArray.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
    fun <T> Array<T>.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
    fun <T> MutableList<T>.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
    fun IntArray.changeMinOf(i: Int, v: Int): Unit = run { this[i] = kotlin.math.min(this[i], v) }
    fun IntArray.changeMaxOf(i: Int, v: Int): Unit = run { this[i] = kotlin.math.max(this[i], v) }
    fun LongArray.changeMinOf(i: Int, v: Long): Unit = run { this[i] = kotlin.math.min(this[i], v) }
    fun LongArray.changeMaxOf(i: Int, v: Long): Unit = run { this[i] = kotlin.math.max(this[i], v) }
    fun IntArray.plusAssignMod(i: Int, v: Int): Unit = run { this[i] = this[i].plusMod(v) }
    fun IntArray.minusAssignMod(i: Int, v: Int): Unit = run { this[i] = this[i].minusMod(v) }
    fun IntArray.timesAssignMod(i: Int, v: Int): Unit = run { this[i] = this[i].timesMod(v) }
    fun IntArray.divAssignMod(i: Int, v: Int): Unit = run { this[i] = this[i].divMod(v) }
    fun IntArray.powAssignMod(i: Int, v: Long): Unit = run { this[i] = this[i].powMod(v) }
    fun LongArray.plusAssignMod(i: Int, v: Int): Unit = run {
        this[i] = (this[i] % mod).toInt().plusMod(v).toLong()
    }
    fun LongArray.minusAssignMod(i: Int, v: Int): Unit = run {
        this[i] = (this[i] % mod).toInt().minusMod(v).toLong()
    }
    fun LongArray.timesAssignMod(i: Int, v: Int): Unit = run {
        this[i] = (this[i] % mod).toInt().timesMod(v).toLong()
    }
    fun LongArray.divAssignMod(i: Int, v: Int): Unit = run {
        this[i] = (this[i] % mod).toInt().divMod(v).toLong()
    }
    fun LongArray.powAssignMod(i: Int, v: Long): Unit = run {
        this[i] = (this[i] % mod).toInt().powMod(v).toLong()
    }
    /**
     * same usage as `IntArray.scan`, but it will faster than that.
     */
    inline fun IntArray.scanArray(initial: Int, operation: (acc: Int, Int) -> Int): IntArray {
        val accumulator = IntArray(this.size + 1).apply { this[0] = initial }
        for (i in this.indices) accumulator[i + 1] = operation(accumulator[i], this[i])
        return accumulator
    }
    /**
     * same usage as `LongArray.scan`, but it will faster than that.
     */
    inline fun LongArray.scanArray(initial: Long, operation: (acc: Long, Long) -> Long): LongArray {
        val accumulator = LongArray(this.size + 1).apply { this[0] = initial }
        for (i in this.indices) accumulator[i + 1] = operation(accumulator[i], this[i])
        return accumulator
    }
    /**
     * same usage as `IntArray.scanReduce`, but it will faster than that.
     */
    inline fun IntArray.scanReduceArray(operation: (acc: Int, Int) -> Int): IntArray {
        val accumulator = IntArray(this.size).apply { this[0] = this@scanReduceArray[0] }
        for (i in 1..this.lastIndex) accumulator[i] = operation(accumulator[i - 1], this[i])
        return accumulator
    }
    /**
     * same usage as `LongArray.scanReduce`, but it will faster than that.
     */
    inline fun LongArray.scanReduceArray(operation: (acc: Long, Long) -> Long): LongArray {
        val accumulator = LongArray(this.size).apply { this[0] = this@scanReduceArray[0] }
        for (i in 1..this.lastIndex) accumulator[i] = operation(accumulator[i - 1], this[i])
        return accumulator
    }
}
// endregion kokomade template dayo (^o^)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0