Games on a CD

题意翻译

已知g个长度为k互不相同的字符串r[1..g]和一个长度为n×k的环形字符串s，问是否能从r[1..g]中选出n个组成字符串s。如果能，则输出YES，并在第二行按在s中的顺序输出对应的r的编号，否则输出NO。 [输入格式] 输入的第一行包含两个正整数n和k（1≤n≤10^5，1≤k≤10^5） 输入的第二行包含一个由小写英文字母组成的环形字符串。字符串的长度为n*k。 保证长度不大于10^6。 输入的第三行包含一个正整数g（n≤g≤10^5）。 确保这些字符串长度之和不超过2*10^6。 接下来的g行中的每一行都包含一个字符串-每个字符串由小写英文字母组成，长度为k。 保证是唯一的。 [输出格式] 如果能，则输出YES，并在第二行按在s中的顺序输出对应的r的编号，否则输出NO。

题目描述

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.

输入输出格式

输入格式

The first line of the input contains two positive integers $ n $ and $ k $ ( $ 1<=n<=10^{5} $ , $ 1<=k<=10^{5} $ ) — 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 $ 10^{6} $ . The third line of the input contains one positive integer $ g $ ( $ n<=g<=10^{5} $ ) — 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·10^{6} $ . 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.

输出格式

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.

输入输出样例

输入样例 #1

3 1
abc
4
b
a
c
d

输出样例 #1

YES
2 1 3 

输入样例 #2

4 2
aabbccdd
4
dd
ab
bc
cd

输出样例 #2

NO