ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5063: Polycarp's Masterpiece

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：5 通过：1
提交提交记录统计Web Board

题目描述

C. Polycarp's Masterpiece
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output
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.
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

输入样例 复制

输出样例 复制

分类标签