Inspired 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 ki-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 cj is contained in a substring of his masterpiece starting from position lj and ending at rj 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≤105,1≤m≤105)− 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 ki(0≤ki≤100)− circular shifts used during n days of work.
Following m lines contains two integer numbers lj,rj and a lowercase latin letter cj each− requests description. For each request you need to count number of times letter cj is contained in a substring of the masterpiece from position lj to rj inclusively. Positions are numerated starting from 1. It is guaranteed that 1≤lj≤rj≤1018 and both lj and rj 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.