#P1394C. Boboniu and String

    ID: 1405 远端评测题 3000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>binary searchgeometryternary search*2600

Boboniu and String

Description

Boboniu defines BN-string as a string ss of characters 'B' and 'N'.

You can perform the following operations on the BN-string ss:

  • Remove a character of ss.
  • Remove a substring "BN" or "NB" of ss.
  • Add a character 'B' or 'N' to the end of ss.
  • Add a string "BN" or "NB" to the end of ss.

Note that a string aa is a substring of a string bb if aa can be obtained from bb 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 ss and tt are similar if and only if:

  • s=t|s|=|t|.
  • There exists a permutation p1,p2,,psp_1, p_2, \ldots, p_{|s|} such that for all ii (1is1\le i\le |s|), spi=tis_{p_i}=t_i.

Boboniu also defines dist(s,t)\text{dist}(s,t), the distance between ss and tt, as the minimum number of operations that makes ss similar to tt.

Now Boboniu gives you nn non-empty BN-strings s1,s2,,sns_1,s_2,\ldots, s_n and asks you to find a non-empty BN-string tt such that the maximum distance to string ss is minimized, i.e. you need to minimize maxi=1ndist(si,t)\max_{i=1}^n \text{dist}(s_i,t).

The first line contains a single integer nn (1n31051\le n\le 3\cdot 10^5).

Each of the next nn lines contains a string sis_i (1si51051\le |s_i| \le 5\cdot 10^5). It is guaranteed that sis_i only contains 'B' and 'N'. The sum of si|s_i| does not exceed 51055\cdot 10^5.

In the first line, print the minimum maxi=1ndist(si,t)\max_{i=1}^n \text{dist}(s_i,t).

In the second line, print the suitable tt.

If there are several possible tt's, you can print any.

Input

The first line contains a single integer nn (1n31051\le n\le 3\cdot 10^5).

Each of the next nn lines contains a string sis_i (1si51051\le |s_i| \le 5\cdot 10^5). It is guaranteed that sis_i only contains 'B' and 'N'. The sum of si|s_i| does not exceed 51055\cdot 10^5.

Output

In the first line, print the minimum maxi=1ndist(si,t)\max_{i=1}^n \text{dist}(s_i,t).

In the second line, print the suitable tt.

If there are several possible tt's, you can print any.

Samples

样例输入 1

3
B
N
BN

样例输出 1

1
BN

样例输入 2

10
N
BBBBBB
BNNNBBNBB
NNNNBNBNNBNNNBBN
NBNBN
NNNNNN
BNBNBNBBBBNNNNBBBBNNBBNBNBBNBBBBBBBB
NNNNBN
NBBBBBBBB
NNNNNN

样例输出 2

12
BBBBBBBBBBBBNNNNNNNNNNNN

样例输入 3

8
NNN
NNN
BBNNBBBN
NNNBNN
B
NNN
NNNNBNN
NNNNNNNNNNNNNNNBNNNNNNNBNB

样例输出 3

12
BBBBNNNNNNNNNNNN

样例输入 4

3
BNNNBNNNNBNBBNNNBBNNNNBBBBNNBBBBBBNBBBBBNBBBNNBBBNBNBBBN
BBBNBBBBNNNNNBBNBBBNNNBB
BBBBBBBBBBBBBBNBBBBBNBBBBBNBBBBNB

样例输出 4

12
BBBBBBBBBBBBBBBBBBBBBBBBBBNNNNNNNNNNNN

Note

In the first example dist(B,BN)=dist(N,BN)=1\text{dist(B,BN)}=\text{dist(N,BN)}=1, dist(BN,BN)=0\text{dist(BN,BN)}=0. So the maximum distance is 11.