Games on a CD
Contest: Technocup 2017 - Elimination Round 1 (Unofficially Open for Everyone, Rated for Div. 2)
Difficulty rating: 2300
Tags: data structures, hashing, string suffix structures, strings

Several years ago Tolya had n computer games and at some point of time he decided to burn them to CD. After that he wrote down the names of the games one after another in a circle on the CD in clockwise order. The names were distinct, the length of each name was equal to k. The names didn't overlap.

Thus, there is a cyclic string of length n·k written on the CD.

Several years have passed and now Tolya can't remember which games he burned to his CD. He knows that there were g popular games that days. All of the games he burned were among these g games, and no game was burned more than once.

You have to restore any valid list of games Tolya could burn to the CD several years ago.

Input format:
The first line of the input contains two positive integers n and k (1 ≤ n ≤ 105, 1 ≤ k ≤ 105) — the amount of games Tolya burned to the CD, and the length of each of the names.

The second line of the input contains one string consisting of lowercase English letters — the string Tolya wrote on the CD, split in arbitrary place. The length of the string is n·k. It is guaranteed that the length is not greater than 106.

The third line of the input contains one positive integer g (n ≤ g ≤ 105) — the amount of popular games that could be written on the CD. It is guaranteed that the total length of names of all popular games is not greater than 2·106.

Each of the next g lines contains a single string — the name of some popular game. Each name consists of lowercase English letters and has length k. It is guaranteed that the names are distinct.

Output format:
If there is no answer, print "NO" (without quotes).

Otherwise, print two lines. In the first line print "YES" (without quotes). In the second line, print n integers — the games which names were written on the CD. You should print games in the order they could have been written on the CD, it means, in clockwise order. You can print games starting from any position. Remember, that no game was burned to the CD more than once. If there are several possible answers, print any of them.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Example input:
3 1
abc
4
b
a
c
d

Example output:
YES
2 1 3

Example input:
4 2
aabbccdd
4
dd
ab
bc
cd

Example output:
NO

Editorial:
With help of Aho Corasick algorithm we need to build the suffix tree on the set of game names ans in the vertex of the tree (which correspond to the name of some game, this vertex will be on the depth k) we will store the number of this game.
Builded tree allows to add symbols to some string one by one and find the vertex which corresponds to the longest prefix from all prefixes of game names which equals to the suffix of our string. If the length of this prefix equals to k the suffix equals to some game name.
Let's write the string which wrote on disk twice and calculate idxi — the index of the game which name equals to substring of doubled string from index i - k + 1 to index i inclusively (if such index does not exist it's equals to  - 1).
Now we need to iterate through the indexes of symbols which is last in the name of some game. We can iterate from 0 to k - 1. With fixed f we need to check that all game names with last symbols in indexes $$f + ik \mod nk$$ for 0 ≤ i < n are different (for it we need to check that among idx(f + ik)%nk + nk there is no  - 1 and all of them are different). If it is performed — print YES and now it is easy to restore the answer. If the condition failed for all f — print NO.
Asymptotic behavior of this solution  — $${\cal O}(nk+\sum|t_{i}|)$$