The Bajtocka Art Gallery is planning to organize an exhibition of paintings by the married couple Anna and Bogusław Bitocki. The couple is known for their unconventional approach to art. At the beginning of each week, they choose a title for a new painting together. Then, Anna and Bogusław work independently for the entire week, creating two works with the same title—one by Anna and one by Bogusław. The couple has been working this way for $n$ weeks, producing $n$ pairs of paintings.

As the gallery curator, you are responsible for fulfilling the contract for the exhibition that the gallery has signed with the Bitockis. According to the contract, you must display $n$ paintings to the visitors—one painting created each week. The paintings will be arranged on one long wall, from left to right, in the order they were created by the couple. Thus, the $i$-th painting from the left on the wall must be one of the two works created during the $i$-th week of their artistic collaboration. However, you have relative freedom in choosing which of the two paintings created in the $i$-th week you will hang. The only condition imposed on you by the contract is that exactly $k$ of the displayed paintings must have been created by Anna, and the remaining works by Bogusław.

Unfortunately, shortly before the exhibition opening, something very disturbing happened! You received information from the police that a gang of thieves is planning a robbery on your gallery. You know that the thieves plan to steal all the displayed paintings from a certain contiguous part of the wall. Thus, they will choose two integers $\ell$ and $r$ (such that $1 \le \ell \le r \le n$) and, under the cover of night, steal all paintings from the $\ell$-th to the $r$-th inclusive. Works not displayed to the visitors are safe and will not be stolen. Furthermore, you have learned how many "bajtalar" the thieves value each painting in the collection at. Interestingly, some valuations can be negative: some works are either very cumbersome and difficult to steal, or it will be almost impossible to resell them later. The final profit of the gang is, of course, the sum of the valuations of all stolen works. You can assume that the thieves will choose the parameters $\ell$ and $r$ to maximize their profit. If, in particular, they are unable to choose these parameters in such a way that their profit is positive, they will abandon their plan and their final profit will be zero.

Of course, you cannot stop the burglars. However, you can try to discourage them from the robbery. You want to hang such paintings that will minimize the final profit of the gang of thieves. Which paintings should you choose? And what gang profit must you reckon with if their robbery plan succeeds?

Input

The first line of input contains two integers $n, k$ ($1 \le n \le 100\,000, 0 \le k \le n$) — the number of pairs of paintings in the collection and the number of Anna Bitocka's paintings that you must hang in the gallery, respectively.

The second line of input contains $n$ integers $a_1, \dots, a_n$ ($-10^9 \le a_i \le 10^9$), representing the valuations of the successive paintings by Anna Bitocka; the $i$-th painting by Anna is worth $a_i$ bajtalar to the gang. The third line contains $n$ integers $b_1, \dots, b_n$ ($-10^9 \le b_i \le 10^9$), representing the analogous valuations of the paintings by Bogusław Bitocki.

Output

Output two lines. The first line should contain a non-negative integer $x$ — the minimum possible final profit of the gang of thieves in bajtalar, assuming you choose the paintings optimally.

The second line of the output should provide an example solution forcing a final profit equal to $x$ bajtalar. The solution should be a string of $n$ characters; the $i$-th character ($1 \le i \le n$) should be 'A' if the $i$-th displayed painting should be the $i$-th painting created by Anna Bitocka, and 'B' if it should be the $i$-th painting created by Bogusław Bitocki. If there are multiple optimal solutions, you may provide any one.

Examples

Input 1

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

Output 1

4
BBABBA

Input 2

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

Output 2

0
AAB