import kotlin.math.max import kotlin.math.min val MOD = 1_000_000_007 fun main() { val (N, X) = readInts() val A = readInts() if (N == 1) { println("B") return } val dpL = Array(N){SegmentTree(N, true){a, b -> a and b}} val dpR = Array(N){SegmentTree(N, true){a, b -> a and b}} for (i in 0 until N) { // 1個だけ残ってる場合はlose dpL[i].update(0, false) dpR[i].update(0, false) } val mxR = run { val res = IntArray(N) var sum = 0L var r = N - 1 for (l in N - 1 downTo 0) { sum += A[l] while (r > l && sum > X) { sum -= A[r] r-- } res[l] = r - l + 1 } res } debug(mxR) val mxL = run { val res = IntArray(N) var sum = 0L var l = 0 for (r in 0 until N) { sum += A[r] while (l < r && sum > X) { sum -= A[l] l++ } res[r] = r - l + 1 } res } debug(mxL) for (len in 2 until N + 1) { for (l in 0 until N - len) { val r = l + len - 1 val win = !dpL[l].query(0, min(len-1, mxR[l])) or !dpR[r].query(0, min(len-1, mxL[r])) dpL[l].update(len - 1, win) dpR[r].update(len - 1, win) } } if (dpL[0].query(N-1, N)) println("A") else println("B") } class SegmentTree(n: Int, val zero: Boolean, val f: (Boolean, Boolean) -> Boolean) { private val N = if (Integer.highestOneBit(n) == n) n else Integer.highestOneBit(n) shl 1 private val dat = BooleanArray(2 * N){zero} fun update(i: Int, a: Boolean) { var ix = i + N dat[ix] = a while(ix > 1) { dat[ix shr 1] = f(dat[ix], dat[ix xor 1]) ix = ix shr 1 } } /** * [a, b) */ fun query(a: Int, b: Int): Boolean { var res: Boolean = zero var left = a + N var right = b - 1 + N while(left <= right) { if ((left and 1) == 1) res = f(res, dat[left]) if ((right and 1) == 0) res = f(res, dat[right]) left = (left + 1) shr 1 // 右の子供なら右の親に移動 right = (right - 1) shr 1 // 左の子供なら左の親に移動 } return res } } private val isDebug = try { // なんか本番でエラーでる System.getenv("MY_DEBUG") != null } catch (t: Throwable) { false } private fun readLn() = readLine()!! private fun readStrings() = readLn().split(" ") private fun readInts() = readStrings().map { it.toInt() }.toIntArray() private fun readLongs() = readStrings().map { it.toLong() }.toLongArray() private inline fun debug(msg: () -> String) { if (isDebug) System.err.println(msg()) } private fun debug(a: LongArray) { debug{a.joinToString(" ")} } private fun debug(a: IntArray) { debug{a.joinToString(" ")} } private fun debug(a: BooleanArray) { debug{a.map{if(it) 1 else 0}.joinToString("")} } private fun debugDim(A: Array) { if (isDebug) { for (a in A) { debug(a) } } }