题目描述

给定长度为 $n$ 的序列 $a, b$。

你需要构造一个序列 $c$，构造方法为：

• 选择 $k$ 个 $i$，令 $c_i \leftarrow a_i$。
• 对于其他 $i$，令 $c_i \leftarrow b_i$。

求序列 $c$ 的最大子段和的最小值，并给出一种方案。

输入格式

第一行，两个整数 $n, k$；

第二行，$n$ 个整数 $a_1, a_2, \cdots, a_n$；

第三行，$n$ 个整数 $b_1, b_2, \cdots, b_n$。

输出格式

第一行，一个整数，表示序列 $c$ 的最大子段和的最小值；

第二行，一个长为 $n$ 的字符串 $s$，若令 $c_i \leftarrow a_i$，$s_i = \text{A}$；否则，$s_i = \text{B}$。

如有多解，输出任意一组均可。

6 2
-1 7 0 2 -5 0
3 1 4 -3 -3 12

4
BBABBA

3 2
-1 -4 -1
-4 -2 -1

0
AAB

提示

对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$0 \leq k \leq n$，$-10^9 \leq a_i, b_i \leq 10^9$。