Description

A famous streamer once said: "From now on, CRAZY GIVE HEAD!!". The streamer was so furious that he said many dirty words. You wonder how many times did a specific word appears in those words.

You will have one long string S and one short string p.

Then you will have q times of queries.

Each query includes two numbers a, b which indicate the range in string S.

The sum of a range indicates the occurrences of string p from position a of string S to position b of string S.

Your task is finding the maximum sum from all the queries.

Note that the index is start from 1.

 

Hint: The biggest problem is that if you construct a prefix sum array based on the occurrences of p[0] and check if it makes the entire p , you will get error when the range cut the "part of p".

Therefore consider this: if we want to avoid the "part of p" problem we can consider that if a part of p will be cut in range (L, R) that means p[0] must in the place of (R-length(p)+2, R). Therefore we only need to consider range (L,R-length(p)+1)

To sum up, we can change the range (L, R) into (L, R-length(p)+1). Use the prefix sum array to calculate this problem will be like: prefix[ R-length(p)+1 ] - prefix[ L-1 ]. In this way, we can avoid the "part of p" problem and solve the question.

⠄⠄⠄⠄⠄⠄⠄
 ⠄⠄⠄⠄⠄⠄⠄⠈⠉⠁⠈⠉⠉⠙⠿⣿⣿⣿⣿⣿
 ⠄⠄⠄⠄⠄⠄⠄⠄⣀⣀⣀⠄⠄⠄⠄⠄⠹⣿⣿⣿
 ⠄⠄⠄⠄⠄⢐⣲⣿⣿⣯⠭⠉⠙⠲⣄⡀⠄⠈⢿⣿
 ⠐⠄⠄⠰⠒⠚⢩⣉⠼⡟⠙⠛⠿⡟⣤⡳⡀⠄⠄⢻
 ⠄⠄⢀⣀⣀⣢⣶⣿⣦⣭⣤⣭⣵⣶⣿⣿⣏⠄⠄⣿
 ⠄⣼⣿⣿⣿⡉⣿⣀⣽⣸⣿⣿⣿⣿⣿⣿⣿⡆⣀⣿
 ⢠⣿⣿⣿⠿⠟⠛⠻⢿⠿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣼
 ⠄⣿⣿⣿⡆⠄⠄⠄⠄⠳⡈⣿⣿⣿⣿⣿⣿⣿⣿⣿
 ⠄⢹⣿⣿⡇⠄⠄⠄⠄⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
 ⠄⠄⢿⣿⣷⣨⣽⣭⢁⣡⣿⣿⠟⣩⣿⣿⣿⠿⠿⠟
 ⠄⠄⠈⡍⠻⣿⣿⣿⣿⠟⠋⢁⣼⠿⠋⠉⠄⠄⠄⠄
 ⠄⠄⠄⠈⠴⢬⣙⣛⡥⠴⠂⠄⠄⠄⠄⠄⠄⠄⠄⠄...
(the photo of the famous streamer)

Input

Input end with EOF.

Each testcase contains several lines.

First line contains two string S(1<= strlen(S) <= 1000) and p(1<= strlen(q)<=1000)

Second line one integer q(1 <= q <= 200000)

The following are q lines. Each line contain two integer a,b(1<= a <= b <= strlen(S))

Output

For each testcases print the maximum sum from all the queries.

Remember to print \n at the end of each output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

No description, literally. I'm tired.

_(:3∠」)_

• You have a sequence a. Initially, a has exactly one integer. You're at the place of the 1st element.

• There are some operations below:

  • insert <val1> <val2>: insert <val2> number of elements, all with value <val1>. Insert them next to your position.

  • erase <val>: erase <val> number of elements next to you.

  • move <value>: Move <value> number of indexes forward. Note that <value> might be negative, which means you might move forward or backward.

  • show: Start from your position, output the sequence a. Each element separated by a space. Note that there should be no space at the end but a '\n'.

 

For example: a = {2}, and execute operations below:

• insert 3 6 // a = {2,3,3,3,3,3,3}, you're at the 1st position.

• insert 1 1 // a = {2,1,3,3,3,3,3,3}, you're at the 1st position.

• erase 2 // a = {2,3,3,3,3,3}, you're at the 1st position. Erase 1 and 3.

• move 5 // a = {3,2,3,3,3,3}, you're at the 1st position. Originally was the 6th position.

• erase 3 // a = {3,3,3}, you're at the 1st position. Erase the first 2 and two 3.

• show // print 3 3 3. Note that there should be a '\n' at the end.

Input

The first line contains an integer x, indicates the first element in a.

The next line contains an integer n, indicates the number of operations.

There are n lines below. Each line contains exactly one operation.

1 <= n <= 3000. All numbers in a are in int range. We guaranteed that there must be at least 1 element in a, and the number of insert and erase elements won't exceed 3000.

Also, the total elements of a won't exceed 3000.

Output

Output the correct a if there's show operation.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss