SP8747 NSUBSTR2 - Substrings II

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

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