Problem description

Archibald jest inspektorem w Izbie Skarbowej i bardzo lubi swoją pracę. Właśnie dowiedział się, że powinien przygotować cykliczny harmonogram kontroli na przyszłość. Harmonogram taki jest ciągiem (f₀,f₁,f₂,…,f_N − 1) i organizuje pracę inspektora na przestrzeni ciągów kolejnych N dni.

Archibald każdego dnia przeprowadza pojedynczą kontrolę, w i-tym dniu zajmując się firmą numer f_{(i mod  N)}. Rozpoczyna więc pracę zerowego dnia, przeprowadzając kontrole w kolejnych podmiotach wedle harmonogramu, w dniu N zaś zaczyna od początku, i tak dalej, wszakże nie wypada pozostawić przedsiębiorstw bez żadnej pomocy. Pod nadzorem Archibalda znajduje się dokładnie 26 firm, identyfikowanych za pomocą kolejnych dużych liter alfabetu angielskiego.

Po rozmowie z przełożonym stało się jasne, że istnieje tylko jeden wymóg Izby wobec harmonogramów – inspektor nie może kontrolować tej samej firmy w dwóch kolejnych dniach. W takim przypadku ułożenie planu przyszłej pracy wyglądało na banalne, Archibald udał się więc na lunch, rozmyślając błogo o swoich udanych audytach z młodości.

Po powrocie do biura czekała go przykra niespodzianka. Przełożony inspektora zapisał już do systemu część cyklicznego harmonogramu dla Archibalda, ustalając niektóre wartości f_j. Nici z planów… Trzeba ratować, co się da, pomyślał Archibald – niech chociaż harmonogram ogranicza się do kontroli możliwie niedużej liczby spośród wszystkich firm (Archibald ma słabą pamięć i może się pogubić jeśli będzie musiał pamiętać informacje o wszystkich firmach.). Pomóż mu uzupełnić pozostałe wartości f_j, rozszerzając harmonogram do pełnego i spełniającego warunki w taki sposób, by jego kontrole odbywały się w najmniejszej możliwej liczbie różnych przedsiębiorstw. Możliwe, że nie da się uzupełnić harmonogramu tak, by inspektor nigdy nie kontrolował żadnej firmy dwa razy z rzędu (wtedy jednak przynajmniej da się wytknąć przełożonemu błąd).

Napisz program, który: wczyta częściowo wypełniony harmonogram, wyznaczy optymalne jego uzupełnienie i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wyjścia znajduje się ciąg wielkich liter alfabetu angielskiego lub symboli ?, reprezentujący częściowy harmonogram kontroli. Litery odpowiadają ustalonym przez przełożonego celom kontroli (w kolejnych dniach cyklu), natomiast symbole ? to wolne wartości, które Archibald musi uzupełnić.

Wyjście

W pierwszym wierszu wyjścia należy wypisać jedną liczbę całkowitą – minimalną liczbę różnych kontrolowanych firm.

W drugim (ostatnim) wierszu wyjścia należy wypisać ciąg złożony z wielkich liter alfabetu angielskiego, który rozszerza częściowy harmonogram kontroli z wejścia i jednocześnie pozwala Archibaldowi kontrolować najmniejszą możliwą liczbę firm.

Jeśli możliwe jest wiele minimalnych rozszerzeń, wypisz dowolne z nich.

Jeśli poprawne rozszerzenie nie jest możliwe, zamiast tego należy wypisać jedynie jedno słowo NIE.

Ograniczenia

Długość ciągu z wejścia (a zarazem liczba dni cyklu) nie przekracza miliona.

Przykład

AB??C?

3
ABABCB

ZZ??

NIE