带可选字符的多字符串匹配

有一个文本串，它的长度为$m (1 \leq m \leq 2000000)$，现在想找出其中所有的符合特定模式的子串位置。

符合特定模式是指，该子串的长度为$n (1 \leq n \leq 500)$，并且第$i$个字符需要在给定的字符集合$S_{i}$中。

因此，描述这一特定模式，共需要$S_{1},S_{2},...,S_{n}$这$n$个字符集合。每个集合的大小都在$1\sim 62$之间，其中的字符只为数字或大小写字母。

第一行为一个字符串，表示待匹配的文本串。注意文本串中可能含有数字和大小写字母之外的字符。

第二行为一个整数$n$。

以下$n$行，分别描述$n$个字符集合。每行开始是一个$1\sim 62$之间的整数，随后有一个空格，接下来有一个字符串表示对应字符集合的内容。整数表示字符集合的大小，因此它也就是字符串的长度。输入保证字符串中的字符只为数字或大小写字母且没有重复。<b>（注：本题有多组测试数据）</b>

每当从某个位置开头的，长度为$n$的子串符合输入的模式，就输出一行，其中包含一个整数，为它在文本串的起始位置。位置编号从$1$开始。

如果文本串没有任何位置符合输入模式，则最后输出一个字符串"NULL"，占一行。

aaaabacabcabd
3
3 abc
2 bc
3 abc

4
6
8
9

2016"百度之星" - 复赛（Astar Round3）