Inżynieria genetyczna

Limit pamięci: 128 MB

Bajtoccy paleoarcheologowie odkopali niedawno kilka bursztynów, w których zatopione są komary. Po przeanalizowaniu próbek owadów okazało się, że pochodzą one z jury, a więc prawdopodobnie miały styczność z wielkimi gadami, które wówczas dominowały na bajtockich lądach. To podsunęło genetykom oryginalny pomysł: spróbują odzyskać z krwi komarów materiał genetyczny bajtoraptora.

Genom bajtoraptora, tak jak u wszystkich bajtockich organizmów, jest ciągiem składającym się z pewnej liczby bajtokwasów. Rodzaje bajtokwasów oznaczamy dla uproszczenia liczbami naturalnymi. W genomie występuje redundancja - każdy rodzaj bajtokwasu jest -krotnie powtórzony (w szczególności, długość każdego poprawnego genomu jest wielokrotnością ). Innymi słowy, jeśli podzielimy genom na bloki składające się z kolejnych bajtokwasów, to każdy blok będzie zawierać bajtokwasy tego samego rodzaju.

Genetykom udało się wydzielić z krwi komara podejrzany łańcuch długości składający się z bajtokwasów. Niestety łańcuch ten może nie być prawidłowym genomem - naukowcy podejrzewają, że mógł on zostać zanieczyszczony obcymi bajtokwasami. Chcą teraz sprawdzić swoją hipotezę i usunąć z tego ciągu jak najmniej bajtokwasów, tak aby powstał prawidłowy genom. W przypadku wielu równie dobrych możliwości, naukowców interesuje genom, który jest najwcześniejszy w porządku leksykograficznym*. Twoim zadaniem jest pomóc im w dokonaniu przełomowego odkrycia!

*Niech i to dwa różne ciągi równej długości, składające się z bajtokwasów. Aby stwierdzić, który z nich jest wcześniejszy w porządku leksykograficznym, należy znaleźć pierwszą pozycję, na której te ciągi się różnią. Wcześniejszy w porządku leksykograficznym jest ten ciąg, który na tej pozycji zawiera bajtokwas oznaczony mniejszą liczbą.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i (, ), oznaczające długość wydzielonego łańcucha bajtokwasów i stopień redundancji poprawnego genomu. W drugim wierszu znajduje się ciąg liczb całkowitych (), oznaczających rodzaje kolejnych bajtokwasów w łańcuchu.

Wyjście

Na wyjście należy wypisać dwa wiersze. Pierwszy z nich powinien zawierać liczbę () oznaczającą długość najdłuższego poprawnego genomu, który może powstać poprzez usunięcie niektórych bajtokwasów z podanego łańcucha.

W drugim wierszu należy wypisać ciąg liczb oznaczających rodzaje kolejnych bajtokwasów w poprawnym genomie. Jeśli istnieje wiele rozwiązań, Twój program powinien wypisać najmniejsze leksykograficznie. Jeśli (tzn. genetykom nie udało się wydzielić żadnego niepustego poprawnego genomu), to drugi wiersz wyjścia powinien być pusty.

Przykład

Dla danych wejściowych:

16 3
3 2 3 1 3 1 1 2 4 2 1 1 2 2 2 2

poprawną odpowiedzią jest:

9
1 1 1 2 2 2 2 2 2

Autor zadania: Tomasz Idziaszek