Problem Description

You are given two sequences $a$ and $b$ of length $n$.

You need to construct a sequence $c$ as follows:

• Choose $k$ indices $i$ and set $c_i \leftarrow a_i$.
• For all other $i$, set $c_i \leftarrow b_i$.

Find the minimum possible value of the maximum subarray sum of sequence $c$, and output one valid construction.

Input Format

The first line contains two integers $n, k$.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$.

The third line contains $n$ integers $b_1, b_2, \cdots, b_n$.

Output Format

The first line contains one integer, the minimum possible value of the maximum subarray sum of sequence $c$.

The second line contains a string $s$ of length $n$. If $c_i \leftarrow a_i$, then $s_i = \text{A}$; otherwise, $s_i = \text{B}$.

If there are multiple solutions, output any one of them.

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

Hint

For $100\%$ of the testdata, $1 \leq n \leq 10^5$, $0 \leq k \leq n$, and $-10^9 \leq a_i, b_i \leq 10^9$.

Translated by ChatGPT 5