M-Stone Games_第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明）

时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

There are $n$ piles of stones, the $i$ -th of which contains $s_i$ stones. The tiles are numbered from $1$ to $n$ . Rika and Satoko are playing a game on it.

During each round of the game, Rika chooses some piles from all $n$ piles. Let denote the set of all chosen piles as $S$ . Satoko then writes a non-negative integer $x$ . If Rika takes some piles from $S$ with the number of stones among all the taken piles equal to $x$ , she wins the game, while otherwise (Rika cannot find such piles) Satoko wins the game. Note that each tile can be taken at most once during a round, and it is possible that Rika does not pick up any tile (when $x=0$ ).

There are $Q$ rounds of game in total, and for the $i$ -th round of game Rika will let $S$ be the set of all piles with index between $l_i$ and $r_i$ . For each round, Satoko wonders the minimum integer $x$ she can write to win the game. As you are a master of programming, it is your turn to solve the problem!

输入描述:

The first line of input contains two integers $n$ and $Q$ , where $n(1\leq n\leq 10^6)$ is the number of tiles and $Q(1\leq Q\leq 10^5)$ is the number of the rounds of the games.

The second line contains $n$ integers $s_1,...,s_n$ , the $i$ -th of which, $s_i(1\leq s_i\leq 10^9)$ , indicates the number of stones in the tile with index $i$ .

Satoko wants you to compute the answers immediately after Rika chooses the interval, so she uses the following method to encrypt the input. The $i$ -th of the next $Q$ lines contains two integers $l_i',r_i'(1\leq l_i', r_i'\leq n)$ . The chosen index range for the $i$ -th round, $l_i,r_i$ , can be computed by the following formula:

$l_i = \min\{ (l_i'+ans_{i-1}) \bmod n+1, (r_i'+ans_{i-1}) \bmod n+1 \}$

$r_i = \max\{ (l_i'+ans_{i-1}) \bmod n+1, (r_i'+ans_{i-1}) \bmod n+1 \}$

where $ans_i$ denotes the answer for the $i$ -th round of the game (and thus $ans_{i-1}$ is the answer for the previous round). You can assume that $ans_0=0$ . It is clear that under the given constraints, $1\leq l_i\leq r_i\leq n$ holds.

输出描述:

Output  lines, the -th of which contains a single integer , denoting the minimum integer  Satoko can choose to win the -th round of the game.

示例1

输入

复制

输出

复制

说明

In the example above, the actual query intervals are , , ,  and .