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: "Gey cool...gey...gey...gey... gey cool~". While this streamer playing his video games, you still need to finish your OJ test. The following is your problem.

---

You will have n numbers and q times of queries.

These n numbers are placed in an array which position starts from 1.

Each query includes two numbers a, b which indicate the range from position a to position b.

The sum of a range indicates the sum of numbers from position a to position b.

The rules to sum up all the numbers are as follow.

If a is bigger than b , you need to sum up the numbers from a to the end and also the part from start to b.(blue part)

If a is smaller than b you just need to sum up the numbers from a to b.(blue part)

If a is equal to b, than there's only one number, and the number will be the sum.(blue part)

Your task is finding the range from queries that has the maximum sum.

Print the range and it's value.

 

Note that the position starts from 1.

If you find multiple answers, you only need to answer the first one appear in the queries.

You can use prefix sum to solve this problem.

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

Input

Input end with EOF.

Each testcase contains several lines.

First line contains two integer n(1<= n <= 2000000) and q(1<= q<=2000000)

Second line contains n integers. Each number ranged from 1~1000000000.

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

Testcases are divided by a blank line.

Output

For each testcases print the answer in the following format:

Max_range: (%d,%d); Value: %d

The first two integer means the two numbers which indicate the maximum range.

The last integer means the sum of this range.

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

Sample Input  Download

Sample Output  Download

Tags

Discuss