[AdditionalFile3607.zip](file://AdditionalFile3607.zip?type=additional_file)

#3607. 「PA 2021」Wystawa

标签: 传统 | 时间限制: 9000 ms | 内存限制: 512 MiB |

题目描述

题目译自 PA 2021 Runda 3 Wystawa

给定长度为 $n$ 的序列 $\{a_i\}$ 与 $\{b_i\}$ ，你需要构造一个序列 $c$ ，使得 $c_i=a_i$ 或 $c_i=b_i$ ，并且 $c_i = a_i$ 的位置个数恰好为 $k$ 。

记序列 $c$ 的最大子段和为 $s$ ，求 $\max(s, 0)$ 的最小值，并给出一种方案。

输入格式

第一行两个正整数 $n,k$，表示序列长度和使用 $\{a_i\}$ 中的数个数的限制。

第二行 $n$ 个整数 $a_i$ 。

第三行 $n$ 个整数 $b_i$ 。

输出格式

第一行一个整数，表示 $\max(s, 0)$ 的最小值。

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

样例 1

输入

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

输出

4
BBABBA

样例 2

输入

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

输出

0
AAB

数据范围与提示

$1 \leq n \leq 10 ^ 5$ ，$0 \leq k \leq n$

$|a_i| \leq 10 ^ 9$ ，$|b_i| \leq 10 ^ 9$