The Concatenation of Words

We are given a pattern word $w$ and a finite sequence of nonempty words $C = (w_1, \ldots, w_k)$. We want to select some words of $C$ and concatenate them in the same order in which they appear in $C$ (that is, choosing a strictly increasing sequence of indices) so that the concatenation equals the pattern $w$. Each word may be used at most once, and the chosen indices must be strictly increasing.

The pattern $w$ and every word of $C$ consist only of lowercase English letters ('a' to 'z'), carry no diacritics, and have length at most 150 each. The number of words satisfies $1 \le k \le 200$.

For example, the pattern rytter can be formed from $C = (\text{ry}, \text{r}, \text{yt}, \text{y}, \text{tt}, \text{t}, \text{e}, \text{te}, \text{r}, \text{er})$ by choosing the words at indices (2, 4, 5, 7, 9), giving r + y + tt + e + r. Choosing indices (1, 5, 10), giving ry + tt + er, is another way to obtain the same pattern.

We want two things: how many such selections exist, and, among all of them, the lexicographically smallest one.

Write a program that:

• reads the pattern $w$, the number of words $k$, and the words of $C$;
• prints the single word NIE if there is no way to form the pattern $w$ by concatenating a strictly increasing selection of words of $C$;
• otherwise prints the number of valid selections (the exact count when it is at most 999999, or 1000000 when it is 1000000 or more), then the lexicographically smallest valid selection, giving the chosen indices in increasing order, one per line.

The lexicographic order on index sequences compares them element by element: at the first position where two sequences differ, the one with the smaller index is smaller, and if one sequence is a proper prefix of the other, the shorter one is smaller.

• The first line contains one word of at most 150 lowercase English letters, the pattern $w$.
• The second line contains a positive integer $k$ ($k \le 200$), the number of words of the sequence $C$.
• Each of the next $k$ lines contains one word of $C$ in order. Each word is nonempty, consists of at most 150 lowercase English letters, starts at the first character of its line, and ends right after its last letter.

Print:

• the single word NIE when it is impossible to form the pattern from the words of $C$ under the rules above; or
• on the first line, the number of valid selections. This is the exact count when it is at most 999999, and exactly 1000000 when the true count is 1000000 or more. On the following lines, print the indices of the words forming the lexicographically smallest valid selection, in increasing order, one per line.