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

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

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

当三块石板被放入后，魔法环装置会启动，并得到如下的能量值：$(a_{i}mod{a}_j)+(a_{j}mod{a}_k)+(a_{k}mod{a}_i)$。这是因为石板的能量在魔法环中单向流动，当能量从石板 $x$ 流向石板 $y$ 时，由于石板能量不匹配，$(a_{x}mod{a}_y)$ 的能量在流动中被保留下来，形成能量余留。最终装置的能量值为三项能量余留之和。

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

形式化题意：

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

有 $q$ 个询问，每个询问给定一个区间 $[l,r]$，你要选择三个下标 $i,j,k\in [l,r]$ 满足 $i\ne j,j\ne k,k\ne i$，最大化 $(a_{i}mod{a}_j)+(a_{j}mod{a}_k)+(a_{k}mod{a}_i)$ 的值。

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

输入格式

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

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

之后 $q$ 行每行两个整数 $l^{\prime },r^{\prime }$，表示解密前的询问。

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

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

保证输入的 $l^{\prime },r^{\prime }\in [1,n]$，且解密后的 $l,r\in [1,n]$ 并满足 $r-l+1\ge 3$。

输出格式

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

样例零

input

4 2 0
21 10 40 8
1 4
2 4

output

32
18

explanation

在样例零中，可以选择：

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

本样例不会放入测试中。

样例一～十

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

限制与约定

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

对于所有数据，保证 $3\le n\le 2\times {10}^6$，$1\le q\le 8\times {10}^5$，$\text{op}\in \{0,1\}$，$1\le a_i\le {10}^{18}$，$a_1\sim a_n$ 互不相等，$1\le l\le r\le n$，$r-l+1\ge 3$。

时间限制：$3\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$