You are given a string T which consists of at most 40000 lowercase Latin letters. 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 letters 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, S_i-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:
aaaaa
2 0 0
a
aa

Output:
5
5