#P18733. [正睿NOI2021训练] -1

[正睿NOI2021训练] -1

-1

有 nn 颗糖果排成一排,第 ii 颗的美味值为 aia_i。

每次询问给出一个后缀 [i,n][i,n] 和数量 cc。你需要在该后缀中选择恰好 cc 颗糖果,任意两颗被选中的糖果不能相邻,并使美味值之和最大。输出这个最大值。

询问强制在线。输入给出的是编码后的 i′,c′i',c',设上次询问的答案为 lastanslastans,则真实参数为

$$i=(i'+lastans)\bmod n+1,\qquad c=(c'+lastans)\bmod n+1.$$

第一次询问之前 lastans=0lastans=0。答案可能超过 32 位整数范围。

输入格式

第一行两个正整数 n,qn,q。第二行 nn 个正整数 a1,…,ana_1,\ldots,a_n。

接下来 qq 行,每行两个非负整数 i′,c′i',c',表示一次编码后的询问。

输出格式

按顺序输出 qq 个整数,表示各次询问的答案。相邻答案以空白分隔。

数据范围

1≤n≤2000001\le n\le200000,1≤q≤5000001\le q\le500000,1≤ai≤1091\le a_i\le10^9。保证每次解码后的询问满足 n−i+2≥2cn-i+2\ge2c,即存在合法选取方案。

样例 1

输入

3 3
10 1 10
0 1
2 1
1 2

输出

20 10 10

样例的真实询问依次为 (1,2),(2,1),(3,1)(1,2),(2,1),(3,1),对应答案为 20,10,1020,10,10。