One day before the contest, shnirelman completely destroyed problem H in less than 15 minutes. Thankfully, I had an idea of a replacement problem.

const val chars = "01ABab"

fun main() = repeat(readln().toInt()) {
  val a = readln().split(" ").map { it.toInt() }
  println(a.mapIndexed { i, x -> 
    CharArray (x) { j -> chars[i * 2 + j % 2] }
  }.flatMap { it.asIterable() }.joinToString(""))
}

fun main() = repeat(readln().toInt()) {
  val n = readln().toInt() * 2
  val a = readln().split(" ").map { it.toInt() }.sorted()
  println(if ((1 until n - 1 step 2).any { i ->
    a[i + 1] - a[i] < maxOf(a[i] - a[i - 1], a[i + 2] - a[i + 1])
  }) "NO" else "YES")
}

const val coins = "BSG"

fun main() {
  val s = readln()
  val sum = Array(3) { 
    s.map { c -> if (c == coins[it]) 1 else 0 }
     .scan(0) { x, y -> x + y }
  }
  
  val q = readln().toInt()
  println((0 until q).map {
    val (l, r) = readln().split(" ").map { it.toInt() }
    val cnt = sum.map { it[r] - it[l - 1] }
    cnt.max() + cnt.min()
  }.joinToString("\n"))
}

import kotlin.system.exitProcess

fun main() {
    val (nString, h) = readln().split(" ")

    fun ask(pos: Int): String {
        println("? ${pos + 1}")
        System.out.flush()
        val resp = readln()
        if (resp == "-1")
            exitProcess(0)
        return resp
    }

    fun isLower(s: String) = s[0].isLowerCase()

    val lowerCaseFirst = isLower(ask(0))
    fun lowerOrEqual(a: String, b: String) : Boolean {
        if (isLower(a) == isLower(b))
            return a <= b;
        return isLower(a) == lowerCaseFirst
    }
    var l = 0
    var r = nString.toInt()
    while (r - l > 1) {
        val mid = (l + r) / 2
        if (lowerOrEqual(ask(mid), h))
            l = mid
        else
            r = mid
    }
    println("! ${l + 1}")
}

fun main() = repeat(readLine()!!.toInt()) {
    val n = readLine()!!.toInt()
    var s = readLine()!!
    var a = readLine()!!.split(" ").map { it.toInt() }
    
    var ans = 0.toLong()
    
    repeat(2) {
        var sum = 0.toLong()
        for (i in 0 until n) {
            if (s[i] == '<')
                ans = maxOf(ans, sum + a[i])
            sum += maxOf(a[i], 0)
        }
        a = a.reversed()
        s = s.reversed().replace('<', '.').replace('>', '<').replace('.', '>')
    }
    
    println(ans)
}

const val N = 505
const val INF = 1e9.toInt()

fun main() {
  val n = readln().toInt()
  val a = readln().split(" ").map { it.toInt() - 1}
  val b = readln().split(" ").map { it.toInt() - 1}
  
  val cnt = Array(N) { IntArray(N) { 0 } }
  val dp = Array(2) { Array(N) { IntArray(N) { INF } } }
  dp[0][0][0] = 0

  for (t in 0 until 2 * n) {
    val ct = t and 1
    val nt = ct xor 1
    
    if (t < n) {
      for (i in 0 until N) for (j in 0 until N) {
        if (a[t] <= i || b[t] <= j) ++cnt[i][j];
      } 
    }

    dp[nt].forEach { it.fill(INF) }
    for (i in 0 until N) for (j in 0 until N) {
      if (dp[ct][i][j] != INF) {
        val lft = minOf(t + 1, n) - i - j
        if (cnt[i][j] > i + j) {
          dp[nt][i + 1][j] = minOf(dp[nt][i + 1][j], dp[ct][i][j] + lft - 1)
          dp[nt][i][j + 1] = minOf(dp[nt][i][j + 1], dp[ct][i][j] + lft - 1)
        } else {
          if (t < n || lft == 0) dp[nt][i][j] = minOf(dp[nt][i][j], dp[ct][i][j] + lft)
        }
      }
    }
  }

  var ans = INF
  for (i in 0 until N) for (j in 0 until N) ans = minOf(ans, dp[0][i][j])
  if (ans == INF) ans = -1
  println(ans)
}

fun main() {
    data class ModInt(val value : Int = 0) {
        val MOD = 998244353
        operator fun plus(oth : ModInt) : ModInt {
            val cur = (this.value + oth.value) % MOD
            return ModInt(cur)
        }
        operator fun times(oth : ModInt) : ModInt {
            val cur = value.toLong() * oth.value % MOD
            return ModInt(cur.toInt())
        }
        fun pow(k: Int) : ModInt {
            var ans = ModInt(1)
            var a = ModInt(value)
            var curPw = k
            while (curPw > 0) {
                if (curPw % 2 == 1)
                    ans *= a
                a *= a
                curPw /= 2
            }
            return ans
        }
        fun inverse() = this.pow(MOD - 2)
        override fun toString() = this.value.toString()
    }

    val n = readln().toInt()
    val a = readln().split(" ").map { it.toInt() }

    val factorials = (1..n).runningFold(ModInt(1)) { acc, it -> acc * ModInt(it) }
    val invFact = factorials.map { it.inverse() }

    fun choose(n : Int, k : Int) : ModInt {
        if (k < 0 || n < k)
            return ModInt(0)
        return factorials[n] * invFact[k] * invFact[n - k]
    }

    val sum = a.sumOf { it.toLong() }
    val delta = List(n) { n - it - 1 - a[it] }.sortedDescending()

    var ansVal = sum
    var ansCnt = ModInt(1)

    var curSum = 0L
    var lf = 0
    var rg = 0
    for (k in 1..n) {
        curSum += delta[k - 1]
        while (delta[lf] > delta[k - 1])
            lf++
        while (rg < delta.size && delta[rg] >= delta[k - 1])
            rg++
        val curVal = sum + curSum - k.toLong() * (k - 1) / 2
        val curCnt = choose(rg - lf, k - lf)
        if (ansVal < curVal) {
            ansVal = curVal
            ansCnt = ModInt(0)
        }
        if (ansVal == curVal) {
            ansCnt += curCnt
        }
    }
    println("$ansVal $ansCnt")
}

import java.util.*

data class Node(var x: Int = 0, var a: Int = 0, var b: Int = 0)

fun get(n: Node, x: Int): Int {
    return when {
        n.x == -1 -> x
        x < n.x -> n.a
        else -> n.b
    }
}

fun combine(a: Node, b: Node): Node {
    return when {
        a.x == -1 -> b
        b.x == -1 -> a
        else -> Node(a.x, get(b, a.a), get(b, a.b))
    }
}

fun emptyNode(): Node {
    return Node(-1, -1, -1)
}

fun fromLength(len: Int): Node {
    return if (len == -1) emptyNode() else Node(len, len, len - 1)
}

const val N = 300003
const val M = 300001

val S = sortedSetOf<Int>()
val T = Array<Node>(4 * N) { emptyNode() }

fun recalc(v: Int) {
    T[v] = combine(T[v * 2 + 1], T[v * 2 + 2])
}

fun build(v: Int, l: Int, r: Int) {
    if (l == r - 1) {
        T[v] = emptyNode()
    } else {
        val m = (l + r) / 2
        build(v * 2 + 1, l, m)
        build(v * 2 + 2, m, r)
        recalc(v)
    }
}

fun upd(v: Int, l: Int, r: Int, pos: Int, x: Int) {
    if (l == r - 1) {
        T[v] = fromLength(x)
    } else {
        val m = (l + r) / 2
        if (pos < m) upd(v * 2 + 1, l, m, pos, x)
        else upd(v * 2 + 2, m, r, pos, x)
        recalc(v)
    }
}

fun get(v: Int, l: Int, r: Int, L: Int, R: Int): Node {
    if (L >= R) return emptyNode()
    if (L == l && R == r) return T[v]
    val m = (l + r) / 2
    return combine(get(v * 2 + 1, l, m, L, minOf(m, R)), get(v * 2 + 2, m, r, maxOf(L, m), R))
}

fun prepare() {
    build(0, 0, M)
    upd(0, 0, M, 0, 0)
    S.add(0)
}

fun insertValue(x: Int) {
    val it = S.ceiling(x)
    if (it != null) {
        upd(0, 0, M, it, it - x)
    }
    S.lower(x)?.let { upd(0, 0, M, x, x - it) }
    S.add(x)
}

fun eraseValue(x: Int) {
    upd(0, 0, M, x, -1)
    S.remove(x)
    val it = S.ceiling(x)
    if (it != null) {
        val y = it
        S.lower(y)?.let { upd(0, 0, M, y, y - it) }
    }
}

fun getGrundy(x: Int): Int {
    val n = get(0, 0, M, 0, x)
    val it = S.lower(x)
    val y = it ?: return x
    val valY = get(n, 0)
    val dist = x - y
    return if (dist <= valY) dist - 1 else dist
}

fun main() {
    val q = readln().toInt()
    
    prepare()
    println((0 until q).map {
        val params = readln().split(" ").map { it.toInt() }
        val (t, x) = params.take(2)
        if (t == 1) {
            if (S.contains(x)) eraseValue(x) else insertValue(x)
            null
        } else {
            val res = params.drop(2).fold(0) { r, y -> r xor getGrundy(y) }
            if (res == 0) "Second" else "First"
        }
    }.filterNotNull().joinToString("\n"))
}

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val x = IntArray(m)
    val y = IntArray(m)
    val edgeId = mutableMapOf<Pair<Int, Int>, Int>()
    val inDeg = IntArray(n)
    val outDeg = IntArray(n)

    for (i in 0 until m) {
        val (xi, yi) = readLine()!!.split(" ").map { it.toInt() }
        x[i] = xi - 1
        y[i] = yi - 1
        edgeId[Pair(x[i], y[i])] = i
        inDeg[y[i]]++
        outDeg[x[i]]++
    }

    var c = 0
    for (i in 0 until n) {
        c = maxOf(c, inDeg[i], outDeg[i])
    }

    val color = Array(n * 2) { IntArray(c) { -1 } }
    for (i in 0 until m) {
        val a = x[i]
        val b = y[i] + n
        var ca = 0
        while (color[a][ca] != -1) ca++
        var cb = 0
        while (color[b][cb] != -1) cb++
        color[a][ca] = b
        color[b][cb] = a
        if (ca != cb) {
            var cur = b
            while (cur != -1) {
                val temp = color[cur][cb]
                color[cur][cb] = color[cur][ca]
                color[cur][ca] = temp
                cur = color[cur][cb]
                val tempCa = ca
                ca = cb
                cb = tempCa
            }
        }
    }

    val ans = MutableList(m) { 0 }
    for (i in 0 until n) {
        for (j in 0 until c) {
            if (color[i][j] != -1) {
                ans[edgeId[Pair(i, color[i][j] - n)]!!] = j
            }
        }
    }

    val xsAdd = mutableListOf<Int>()
    val ysAdd = mutableListOf<Int>()
    var k = 0
    for (i in 0 until c) {
        val nxt = IntArray(n) { -1 }
        val pre = IntArray(n) { -1 }
        for (j in 0 until m) {
            if (ans[j] == i) {
                nxt[x[j]] = y[j]
                pre[y[j]] = x[j]
            }
        }
        val parts = mutableListOf<Pair<Int, Int>>()
        for (j in 0 until n) {
            if (pre[j] == -1) {
                var l = j
                var r = j
                while (nxt[r] != -1) r = nxt[r]
                parts.add(Pair(l, r))
            }
        }
        val p = parts.size
        k += p
        for (j in 0 until p) {
            xsAdd.add(parts[j].second)
            ysAdd.add(parts[(j + 1) % p].first)
        }
        for (j in 0 until p) {
            ans += i
        }
    }

    println(k)
    for (i in 0 until k) {
        println("$$${xsAdd[i] + 1} $$${ysAdd[i] + 1}")
    }
    println(c)
    for (x in ans) {
        print("${x + 1} ")
    }
    println()
}