Bajtocka 艺术画廊计划举办一场由 Anna 和 Bogusław Bitocki 夫妇创作的画展。这对夫妇以其独特的艺术风格而闻名。每周初，他们会共同选定一个新画作的主题。随后，Anna 和 Bogusław 会在这一周内各自独立工作，创作出两幅同名作品——一幅由 Anna 创作，另一幅由 Bogusław 创作。这对夫妇已经这样合作了 $n$ 周，因此他们总共创作了 $n$ 对画作。

作为画廊馆长，你负责履行画廊与 Bitocki 夫妇签署的展览协议。根据协议，你需要向参观者展示 $n$ 幅画作——即每周创作的画作中各选出一幅。这些画作将按创作顺序从左到右排列在同一面长墙上。因此，墙上从左往右的第 $i$ 幅画必须是第 $i$ 周创作的两幅作品中的其中之一。你在选择每周展示哪一幅画时拥有一定的自由度。协议对你唯一的限制是：在所有展示的画作中，必须恰好有 $k$ 幅是由 Anna 创作的，其余画作则由 Bogusław 创作。

不幸的是，在展览开幕前不久，发生了一件非常令人不安的事情！你从警方那里获悉，一伙窃贼正计划洗劫你的画廊。你知道窃贼计划偷走墙上某一段连续区域内的所有展出画作。也就是说，他们会选择两个整数 $\ell$ 和 $r$（满足 $1 \le \ell \le r \le n$），并在夜幕掩护下偷走从第 $\ell$ 幅到第 $r$ 幅（含）的所有画作。未展示给参观者的作品是安全的，不会被偷走。此外，你还了解到窃贼对收藏中每一幅画的估价（以 Bajtalar 为单位）。有趣的是，有些估价可能是负数：有些作品要么非常笨重且难以偷窃，要么在偷窃后几乎不可能转手。窃贼的最终收益显然是所有被盗作品估价的总和。你可以假设窃贼会选择参数 $\ell$ 和 $r$ 以最大化他们的收益。特别地，如果他们无法选择这些参数使得收益为正，他们将放弃计划，最终收益为零。

当然，你无法阻止窃贼。但你可以尝试通过选择展出的画作来最小化窃贼的最终收益。那么，你应该选择哪些画作？如果窃贼的抢劫计划成功，你必须预期的窃贼收益是多少？

输入格式

输入的第一行包含两个整数 $n, k$ ($1 \le n \le 100\,000, 0 \le k \le n$)，分别表示收藏中的画作对数以及你必须在画廊中展示的 Anna Bitocka 的画作数量。

第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($-10^9 \le a_i \le 10^9$)，表示 Anna Bitocka 后续画作的估价；Anna 的第 $i$ 幅画对窃贼而言价值 $a_i$ Bajtalar。

第三行包含 $n$ 个整数 $b_1, \dots, b_n$ ($-10^9 \le b_i \le 10^9$)，表示 Bogusław Bitocki 画作的相应估价。

输出格式

输出两行。第一行应包含一个非负整数 $x$ —— 在你最优选择画作的情况下，窃贼可能获得的最小最终收益（以 Bajtalar 为单位）。

第二行输出一个示例方案，该方案使得最终收益等于 $x$ Bajtalar。该方案应为一个长度为 $n$ 的字符串；如果第 $i$ 幅展示的画作应为 Anna Bitocka 的第 $i$ 幅作品，则第 $i$ 个字符应为 A；如果应为 Bogusław Bitocki 的第 $i$ 幅作品，则应为 B。如果存在多个最优解，输出其中任意一个即可。

样例

输入 1

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

输出 1

4
BBABBA

输入 2

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

输出 2

0
AAB