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.