#P18733. [正睿NOI2021训练] -1
[正睿NOI2021训练] -1
-1
有 颗糖果排成一排,第 颗的美味值为 。
每次询问给出一个后缀 和数量 。你需要在该后缀中选择恰好 颗糖果,任意两颗被选中的糖果不能相邻,并使美味值之和最大。输出这个最大值。
询问强制在线。输入给出的是编码后的 ,设上次询问的答案为 ,则真实参数为
$$i=(i'+lastans)\bmod n+1,\qquad c=(c'+lastans)\bmod n+1.$$第一次询问之前 。答案可能超过 32 位整数范围。
输入格式
第一行两个正整数 。第二行 个正整数 。
接下来 行,每行两个非负整数 ,表示一次编码后的询问。
输出格式
按顺序输出 个整数,表示各次询问的答案。相邻答案以空白分隔。
数据范围
,,。保证每次解码后的询问满足 ,即存在合法选取方案。
样例 1
输入
3 3
10 1 10
0 1
2 1
1 2
输出
20 10 10
样例的真实询问依次为 ,对应答案为 。