Składanie słów

Limit pamięci: 32 MB

Dane jest słowo stanowiące wzorzec oraz skończony ciąg niepustych słów . W ciągu trzeba wskazać słowa, które po złączeniu, w takiej kolejności, w jakiej występują w ciągu , utworzą wzorzec. Rozwiązaniem ma być rosnący ciąg numerów wyrazów danego ciągu , które po złączeniu utworzą wzorzec. Wzorzec i każde słowo w ciągu składają się z co najwyżej 150 małych liter alfabetu angielskiego od 'a' do 'z' i nie zawierają znaków narodowych. Liczba wyrazów w ciągu jest dodatnia i nie większa niż .

Przykład

Wzorzec rytter można utworzyć ze słów ciągu wybierając kolejno i łącząc wyrazy o numerach . Wybranie wyrazów: jest innym sposobem otrzymania tego samego wzorca.

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia następujące dane: wzorzec , liczbę wyrazów ciągu , a następnie kolejne wyrazy tego ciągu,
• jeżeli nie istnieje rozwiązanie zadania utworzenia wzorca z wyrazów ciągu , zgodnie z podanymi wyżej warunkami, to zapisuje na standardowym wyjściu jedno słowo NIE,
• jeżeli istnieją rozwiązania i jest ich mniej niż , zapisuje na standardowym wyjściu liczbę rozwiązań, a następnie jedno dowolne rozwiązanie zadania,
• jeżeli rozwiązań jest więcej niż zapisuje na standardowym wyjściu liczbę , a następnie jedno dowolne rozwiązanie zadania.

Wejście

• W pierwszym wierszu standardowego wejścia zapisane jest jedno słowo złożone z co najwyżej 150 małych liter alfabetu angielskiego. Jest to wzorzec .
• W drugim wierszu jest zapisana dodatnia liczba całkowita . Jest to liczba wyrazów ciągu .
• W kolejnych wierszach są zapisane kolejne niepuste słowa tworzące ciąg , każdy wyraz jest zapisany w osobnym wierszu i składa się z co najwyżej 150 małych liter alfabetu angielskiego. Pierwsza litera słowa jest zawsze pierwszym znakiem w wierszu, a bezpośrednio po ostatniej jest koniec wiersza.

Wyjście

Na standardowym wyjściu należy zapisać:

• albo jedno słowo NIE, w przypadku gdy ze słów w ciągu nie można ułożyć wzorca w sposób zgodny z warunkami zadania,
• albo w pierwszym wierszu jedną liczbą, to jest liczbę rozwiązań zadania, albo , a w kolejnych wierszach rosnący ciąg numerów wyrazów wybranych z ciągu , które po złożeniu utworzą wzorzec - każdą liczbę w osobnym wierszu.

Przykład

Dla danych wejściowych:

rytter
10
ry
r
yt
y
tt
t
e
te
r
er

poprawną odpowiedzią jest:

9
2
4
5
7
9

Autor zadania: Wojciech Rytter.