#P1394C. Boboniu and String
Boboniu and String
Description
Boboniu defines BN-string as a string of characters 'B' and 'N'.
You can perform the following operations on the BN-string :
- Remove a character of .
- Remove a substring "BN" or "NB" of .
- Add a character 'B' or 'N' to the end of .
- Add a string "BN" or "NB" to the end of .
Note that a string is a substring of a string if can be obtained from by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
Boboniu thinks that BN-strings and are similar if and only if:
- .
- There exists a permutation such that for all (), .
Boboniu also defines , the distance between and , as the minimum number of operations that makes similar to .
Now Boboniu gives you non-empty BN-strings and asks you to find a non-empty BN-string such that the maximum distance to string is minimized, i.e. you need to minimize .
The first line contains a single integer ().
Each of the next lines contains a string (). It is guaranteed that only contains 'B' and 'N'. The sum of does not exceed .
In the first line, print the minimum .
In the second line, print the suitable .
If there are several possible 's, you can print any.
Input
The first line contains a single integer ().
Each of the next lines contains a string (). It is guaranteed that only contains 'B' and 'N'. The sum of does not exceed .
Output
In the first line, print the minimum .
In the second line, print the suitable .
If there are several possible 's, you can print any.
Samples
Note
In the first example , . So the maximum distance is .