NSUBSTR2 - Substrings II


# 题目描述 给你一个字符集为小写字母的字符串$T$,同时给你两个参数A和B,有Q组询问 每次询问一个字符串在$T$中出现了多少次 每一次询问之后,假设这次询问的答案为$ans$,你需要把第$((A * ans + B) \% 26) + 1$个小写字母加入到$T$的末尾 接下来$q$ 行,依次是询问的字符串 # 输入格式 第一行一个字符串$T$ 第二行三个整数$q, a, b$,分别表示询问次数,参数A和参数B # 数据范围 $|T| \le 40000$ $1 \le q \le 40000$ $0 \le 27$ $0 \le 26$ 输入文件大小不会超过$600kb$ # 输出格式 一共输出$q$行,第$i$行表示第$i$次询问的答案 # 输入样例 ``` plain aaaaa 2 0 0 a aa ``` # 输出样例 ``` plain 5 5 ``` # 样例说明 第一次询问的时候,$a$在$aaaaa$中一共出现了$5$次,$ans=5$,之后需要添加第$((0 * ans + 0) \% 26) + 1=1$个小写字母,即$a$,加入到$T$的尾部 此时$T$是$aaaaaa$ 第二个询问$aa$在$aaaaaa$中出现了多少次,显然是$5$次 感谢@KingSann 提供的翻译


You are given a string T which consists of 40000 lowercase latin letters at most. You are also given some integers A, B and Q. You have to answer Q queries. For i-th query you are given a string S $ _{i} $ and you need to output how many times S $ _{i} $ appears in T. Immediately after answering the current query you need to add ((A\*ans+B) modulo 26+1)-th lowercase symbol of the English alphabet to the end of T where ans is the answer to this query.



The first line of input contains a string T. The next line consists of three integers Q (1<=Q<=40000), A (0<=A<=27) and B (0<=B<=26). The following Q lines contain Q query strings, S $ _{i-2} $ on i-th line. Input will not exceed 600 kb.


Output Q lines. Output the answer to the i-th query on the i-th line output.


输入样例 #1

\naaaaa\n2 0 0\na\naa\n\n

输出样例 #1