Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Polycarp's Masterpiece

time limit per test

1 secondmemory limit per test

512 megabytesinput

standard inputoutput

standard outputInspired by success of Joanne Rowling and her fantasy series of Harry Potter, Polycarp decided to create his own masterpiece. He has already picked a name for his future bestseller — string *s*.

Polycarp faced a number of difficulties while he was working on the main story of his book so he decided to become Malevich in a literature and create his own "Black Square".

Chapters of his masterpiece were written by Polycarp in *n* days. He started from writing down the string *s*. Every day (during the following *n* days) he did the following procedure: on the *i*-th day he added to the right of current text *t* its *k*_{i}-th circular shift. It means that every day content of his masterpiece doubled in size.

Circular shift of a string *r* is defined as a string resulted after movement of the last character of *r* to the first position in the string. As an example: circular shift of «masterpiece» is «emasterpiec». The *i*-th circular shift of a string *r* is defined as a string resulted after applying *i* subsequent circular shifts of the string *r* (e.g., the third circular shift of «masterpiece» is «ecemasterpi»).

After *n* days of tedious work Polycarp managed to write a very long text deserving the efforts made. However, text of his masterpiece was so long that it was nearly impossible to do any analysis of its content.

Help Polycarp to answer *m* requests about his masterpiece: for the *j*-th request you will need to find how many times a letter *c*_{j} is contained in a substring of his masterpiece starting from position *l*_{j} and ending at *r*_{j} inclusively.

Input

The first line contains a name of the masterpiece — string *s*. The string *s* contains only lowercase latin letters and its length is between 1 and 100 inclusively.

The second line contains a pair of integer numbers *n* and *m* (1 ≤ *n* ≤ 10^{5}, 1 ≤ *m* ≤ 10^{5}) — a number of days Polycarp worked on his masterpiece and a number of requests you need to answer for the text respectively.

The next line consists of *n* integer numbers *k*_{i} (0 ≤ *k*_{i} ≤ 100) — circular shifts used during *n* days of work.

Following *m* lines contains two integer numbers *l*_{j}, *r*_{j} and a lowercase latin letter *c*_{j} each — requests description. For each request you need to count number of times letter *c*_{j} is contained in a substring of the masterpiece from position *l*_{j} to *r*_{j} inclusively. Positions are numerated starting from 1. It is guaranteed that 1 ≤ *l*_{j} ≤ *r*_{j} ≤ 10^{18} and both *l*_{j} and *r*_{j} do not exceed length of the masterpiece.

Output

Output should contain *m* lines, where the *j*-th line contains the answer on the *j*-th request.

Examples

Input

masterpiece

1 3

3

1 22 m

9 14 e

8 15 p

Output

2

4

0

Input

polycarp

1 2

0

2 15 p

1 16 p

Output

2

4

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/19/2018 02:31:17 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|