题目背景

寻宝者在古墓中发现一列宝箱，每个宝箱装有数量不等的金币。机关限定：每个宝箱要么整个搬走，要么原封不动。

题目描述

有 $n$ 个宝箱排成一列，第 $i$ 个宝箱中恰好有 $a_i$ 枚金币。

有 $q$ 次询问，每次询问给出区间 $[l, r]$。设

$$S(l, r) = \left\{ \sum_{i \in T} a_i \;\middle|\; T \subseteq \{l, l+1, \dots, r\} \right\}$$

即从第 $l$ 到第 $r$ 个宝箱中选取若干箱（每箱至多选一次）所能凑出的金币总数构成的集合。请回答 $S(l, r)$ 中最小的凑不出的正整数，即

$$\min \left\{ x \in \mathbb{Z}_{>0} \mid x \notin S(l, r) \right\}$$

本题的询问是加密的。设 $\mathrm{last}$ 表示上一次询问的答案（初始 $\mathrm{last} = 0$）。每次询问读入两个整数 $l', r'$，实际的询问区间为

$$l = (l' + \mathrm{last}) \bmod n + 1, \qquad r = (r' + \mathrm{last}) \bmod n + 1$$

若 $l > r$ 则交换 $l, r$。你需要回答该区间对应的答案，并将 $\mathrm{last}$ 更新为本次答案。

输入格式

第一行两个整数 $n, q$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

接下来 $q$ 行，每行两个整数 $l', r'$，表示加密后的询问。

输出格式

共 $q$ 行，每行一个整数，表示对应询问的答案。

样例

样例输入

5 3
1 2 4 8 16
5 4
3 4
3 5

样例输出

32
4
1

样例说明：初始 last = 0：$l=(5+0)\bmod 5+1=1$，$r=(4+0)\bmod 5+1=5$，区间 (1,5)，答案 32；更新 last=32：$l=(3+32)\bmod 5+1=1$，$r=(4+32)\bmod 5+1=2$，区间 (1,2)，答案 4；更新 last=4：$l=(3+4)\bmod 5+1=3$，$r=(5+4)\bmod 5+1=5$，区间 (3,5)，答案 1。

数据范围与提示

对于全部数据：$1 \le n, q \le 10^5$，$1 \le a_i \le 10^9$，$1 \le l \le r \le n$。

时间限制：4 秒；内存限制：1024 MB。