跳蚤国王为庆祝这次盛典精心策划了一项挑战，名为“环环相扣”。这项挑战不仅是对选手智慧与策略的极大考验，更是对跳蚤王国机械工艺的完美展示。

跳蚤王国的魔法工匠们准备了一组长度为 $n$ 的独特石板，每块石板有一个能量值 $a_1, a_2, \ldots, a_n$，这些值互不相等。

在这项挑战中，伏特会多次出题，每次会给出一个下标区间 $[l, r]$，选手需要在这个下标区间内选择三块不同的石板，将它们按任意顺序放入魔法环装置的插槽中。

当三块石板被放入后，魔法环装置会启动，并得到如下的能量值：$(a_i\bmod a_j)+(a_j\bmod a_k)+(a_k\bmod a_i)$。这是因为石板的能量在魔法环中单向流动，当能量从石板 $x$ 流向石板 $y$ 时，由于石板能量不匹配，$(a_x \bmod a_y)$ 的能量在流动中被保留下来，形成能量余留。最终装置的能量值为三项能量余留之和。

作为挑战者，你的任务是从每个给定的区间中，选择三块不同的石板，最大化装置的能量值。

形式化题意：

给定一个长度为 $n$ 的整数序列 $a_1\sim a_n$，其中的元素两两互不相等。

有 $q$ 个询问，每个询问给定一个区间 $[l,r]$，你要选择三个下标 $i,j,k\in[l,r]$ 满足 $i\neq j,j\neq k,k\neq i$，最大化 $(a_i\bmod a_j)+(a_j\bmod a_k)+(a_k\bmod a_i)$ 的值。

你只需要输出这个最大值。

输入格式

第一行三个整数 $n,q,\text{op}$ 表示序列的长度、询问的个数，以及是否强制在线。

第二行 $n$ 个整数 $a_1\sim a_n$。

之后 $q$ 行每行两个整数 $l',r'$，表示解密前的询问。

• 如果 $\text{op}=0$，那么 $(l,r)=(l',r')$。
• 如果 $\text{op}=1$，那么 $(l,r)=((l'+\text{lastans}) \bmod n, (r'+\text{lastans}) \bmod n)$，这里的 $\bmod$ 运算返回 $[1, n]$ 内唯一同余的整数。

其中，$\text{lastans}$ 表示上一个询问的答案，初始时 $\text{lastans}=0$。

保证输入的 $l',r'\in[1,n]$，且解密后的 $l,r\in[1,n]$ 并满足 $r-l+1\geq3$。

输出格式

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

样例零

input

4 2 0
21 10 40 8
1 4
2 4

output

32
18

explanation

在样例零中，可以选择：

• $ (i, j, k) = (1, 4, 3) $，对应的值为 $ (21 \bmod 8) + (8 \bmod 40) + (40 \bmod 21) = 32 $。
• $ (i, j, k) = (4, 2, 3) $，对应的值为 $ (8 \bmod 10) + (10 \bmod 40) + (40 \bmod 8) = 18 $。

本样例不会放入测试中。

样例一～十

见附件下载，它们分别对应子任务 $1\sim10$。

限制与约定

本题采用捆绑测试，各个子任务之间开启所有合理的子任务依赖。

对于所有数据，保证 $3\leq n\leq2\times10^6$，$1\leq q\leq8\times10^5$，$\text{op}\in\{0,1\}$，$1\leq a_i\leq10^{18}$，$a_1\sim a_n$ 互不相等，$1\leq l\leq r\leq n$，$r-l+1\geq3$。

暂时只能针对 $\text{op}=0$ 提交 hack 数据。

时间限制：$3\texttt{s}$

空间限制：$512\texttt{MB}$