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)\).
Выходные данные
В первой строке, выведите минимальное значение \(\max_{i=1}^n \text{dist}(s_i,t)\).
Во второй строке, выведите подходящее \(t\).
Если есть несколько возможных \(t\), вы можете вывести любое.
Примечание
В первом примере \(\text{dist(B,BN)}=\text{dist(N,BN)}=1\), \(\text{dist(BN,BN)}=0\). Таким образом максимальное значение равно \(1\).