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

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