C. Boboniu и строка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Boboniu определяет BN-строку как строку $$$s$$$ из символов 'B' и 'N'.

Он может совершать следующие операции над BN-строкой $$$s$$$:

  • Удалить один символ из $$$s$$$.
  • Удалить подстроку «BN» или «NB» из $$$s$$$.
  • Добавить символ 'B' или 'N' в конец $$$s$$$.
  • Добавить строку «BN» или «NB» в конец $$$s$$$.

Строка $$$a$$$ является подстрокой строки $$$b$$$ если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, нуля или всех) символов из начала и нескольких (возможно, нуля или всех) символов из конца.

Boboniu считает, что BN-строки $$$s$$$ и $$$t$$$ похожи если и только если:

  • $$$|s|=|t|$$$.
  • Существует перестановка $$$p_1, p_2, \ldots, p_{|s|}$$$, что для всех $$$i$$$ ($$$1\le i\le |s|$$$), $$$s_{p_i}=t_i$$$.

Boboniu также определяет $$$\text{dist}(s,t)$$$, расстояние между $$$s$$$ и $$$t$$$, как минимальное число операций, необходимое чтобы сделать $$$s$$$ похожей на $$$t$$$.

Теперь Boboniu дал вам $$$n$$$ непустых BN-строк $$$s_1,s_2,\ldots, s_n$$$ и просит вас найти непустую BN-строку $$$t$$$, что максимальное расстояние до строки из $$$s$$$ минимизировано, т.е. вам нужно минимизировать $$$\max_{i=1}^n \text{dist}(s_i,t)$$$.

Входные данные

В первой строке записано одно целое число $$$n$$$ ($$$1\le n\le 3\cdot 10^5$$$).

Каждая из следующих $$$n$$$ строк содержит слову $$$s_i$$$ ($$$1\le |s_i| \le 5\cdot 10^5$$$). Гарантируется, что $$$s_i$$$ состоит только из 'B' и 'N'. Сумма $$$|s_i|$$$ не превосходит $$$5\cdot 10^5$$$.

Выходные данные

В первой строке, выведите минимальное значение $$$\max_{i=1}^n \text{dist}(s_i,t)$$$.

Во второй строке, выведите подходящее $$$t$$$.

Если есть несколько возможных $$$t$$$, вы можете вывести любое.

Примеры
Входные данные
3
B
N
BN
Выходные данные
1
BN
Входные данные
10
N
BBBBBB
BNNNBBNBB
NNNNBNBNNBNNNBBN
NBNBN
NNNNNN
BNBNBNBBBBNNNNBBBBNNBBNBNBBNBBBBBBBB
NNNNBN
NBBBBBBBB
NNNNNN
Выходные данные
12
BBBBBBBBBBBBNNNNNNNNNNNN
Входные данные
8
NNN
NNN
BBNNBBBN
NNNBNN
B
NNN
NNNNBNN
NNNNNNNNNNNNNNNBNNNNNNNBNB
Выходные данные
12
BBBBNNNNNNNNNNNN
Входные данные
3
BNNNBNNNNBNBBNNNBBNNNNBBBBNNBBBBBBNBBBBBNBBBNNBBBNBNBBBN
BBBNBBBBNNNNNBBNBBBNNNBB
BBBBBBBBBBBBBBNBBBBBNBBBBBNBBBBNB
Выходные данные
12
BBBBBBBBBBBBBBBBBBBBBBBBBBNNNNNNNNNNNN
Примечание

В первом примере $$$\text{dist(B,BN)}=\text{dist(N,BN)}=1$$$, $$$\text{dist(BN,BN)}=0$$$. Таким образом максимальное значение равно $$$1$$$.