## 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 Si and you need to output how many times Si 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.

### Input

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, Si-2 on i-th line. Input will not exceed 600 kb.

### Output

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

### Example

`Input:aaaaa2 0 0aaaOutput:55`

hide comments
 < Previous 1 2 Next > Amit Ajaat: 2015-06-21 20:43:15 14507647 is my solution I.D and i challenge you and your online judges, to find mistake in my program. I used Z algorithm by concatenating required string to be searched at very beginning of the original string given in testcase, still getting wrong answer.........very stupid question .....tell me why i am getting wrong answer. i am talking to you "Tooru Ichii".... ljmocic: 2015-04-11 20:06:38 Thank you @PetarV , i was a little disappointed so i didn't even read the comments. Seems like pretty easy problem, but it gave me lot of headeaches. PetarV: 2015-04-09 23:13:17 @ ljmocic: As Encho previously said, SPOJ always tests on *all* testcases, then reports the *first* error it found while doing so. As such, it might not be the 14th that's causing your SEGF, it could be any of them. ljmocic: 2015-04-09 16:09:07 What is wrong with 14th test case? Always getting segmentation fault on that case. Encho: 2015-04-05 12:08:39 As far as I know SPOJ doesn't stop grading once you get WA or TL, therefore all these comments "What is test #14, i get WA" are useless. I think there are 14 tests in total, if you're getting WA - then one of them is wrong, not necessarily the 14th. Kegla: 2015-04-02 09:25:46 I am having issue(WrongAnswer) with the 14th test case too...not having a clue where is a problem. Ognjen Arsenijevic: 2015-04-01 15:28:52 what is 14th test case? I'm getting WA at that test case and I don't know why. E. Choroba: 2011-08-22 15:07:42 A and B should not be 0 according to the Input section, but they are 0 in the example. EDIT: fixed Last edit: 2011-05-20 17:46:55 Mark Gordon: 2011-08-22 15:07:42 @Santiago The time shown by SPOJ is the aggregate time over all test cases. That's why they can be over the time limit for a single test case. What does your code being 'short' have to do with it getting TLE? Sounds like you just have the wrong algorithm. Santiago Palacio: 2011-08-22 15:07:42 Is it possible to use fscanf with spoj? i dont use a THAT long algorithm, i've tested for a 40000 letter long string, and it works fine, except for 14th case. Last edit: 2011-05-02 05:54:17

 Added by: Tooru Ichii Date: 2011-04-18 Time limit: 0.721s Source limit: 44444B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 Resource: Immagination