Description

Uncle Huang wants to find a tutor. He has n students to choose from. 

Students are indexed 1, 2, . . . , n and standing in a circle. 

Uncle Huang will count every k-th students in clock-wise.  

The k-th student is going to be chosen but the student will disappear(Nobody knows why!) therefore Uncle Huang will continue his counting and start from the next student.

The last remaining student will be his tutor.

Tell Uncle Huang the index of the student who will be his tutor.

example: If n = 5, k = 7

Hint: 約瑟夫斯問題(https://zh.wikipedia.org/wiki/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98)

This problem is partial judge.

Note: k might be very large, if you just count k students you will get TLE. Try to count less by using mod.

 

Input

The input will end by EOF

Every testcase only contains two integer n(1<= n <= 1000) and k(1 <= k <= 10⁹)

Output

For each testcase print the index of the student who last remaining.

remember to print \n at the end of every output.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12301.c

Partial Judge Header

12301.h

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