Pen Pineapple Apple Pen
All submissions for this problem are available.There are $K$ magical pens (numbered $1$ through $K$). You are given strings $P_1, P_2, \ldots, P_K$ (each of which consists of characters from **'a', 'b', ..., 't'**) ; for each valid $i$, the $i$-th pen can only write letters from the string $P_i$. You want to write a word $S$ of length $N$. All the characters of $S$ are between **'a'** and **'t'** inclusive. This string must be written from left to right. To write it, you pick up some pen and start writing; after you've written some prefix of $S$, you can put down that pen, pick up another pen, continue writing $S$ from the point where you put down the previous pen, later pick up another pen (any pen) and continue writing $S$ with that pen, and so on until you write the whole string $S$. You may pick up each pen any number of times, including zero. You have to find a way of writing the word $S$ such that the number of times you change the pen (put down the pen you're currently writing with and pick up another) is the smallest possible. If there are multiple solutions, you may find any one. It is guaranteed that it is possible to write $S$ with the given pens. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first line of each test case contains two space-separated integers $N$ and $K$. - The second line contains a single string $S$. - For each valid $i$, the $i$-th of the next $K$ lines contains a single string $P_i$. ### Output For each test case, print a single line containing $N$ space-separated integers. For each valid $i$, the $i$-th of these integers should be the number of the pen with which you want to write the $i$-th character of $S$. Your output will be considered correct if each character can be written with the pen you want to write it with and the number of times you have to change the pen you are writing with is minimum possible. ### Constraints - $1 \le T \le 10$ - $1 \le N \le 10^6$ - $1 \le K \le 10^5$ - $S, P_1, P_2, \ldots, P_K$ contain only characters **'a', 'b', ..., 't'** - $1 \le |P_i| \le 20$ for each valid $i$ - For each valid $i$, all characters of $P_i$ are pairwise distinct - The sum of lengths of all the strings on the input does not exceed $2 \cdot 10^6$ ### Example Input ``` 3 4 2 abcd ab cd 4 2 baab ab ca 4 2 acaa ab cd ``` ### Example Output ``` 1 1 2 2 1 1 1 1 1 2 1 1 ``` ### Explanation **Example case 1:** You can write the first two characters with the first pen and the next two characters with the second pen. This means you have to change the pen once (from pen $1$ to pen $2$). **Example case 2:** You can write the whole string $S$ with the first pen, so you never have to change the pen you are writing with. **Example case 3:** You can write the first character with the first pen, the second character with the second pen and then the last two characters again with the first pen. Thus, you have to change the pen twice (from pen $1$ to pen $2$ and then from pen $2$ to pen $1$).
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.