← 返回题目列表

Codeforces · 1172/F

F. Nauuo 和 Bug

中文机器翻译题面 查看原题

Nauuo 是一个热爱编码的女孩。

有一天,她正在解决一个问题,需要计算一些数字对 $$$p$$$ 取模的总和。

她编写了以下代码并得到了“错误答案”的结论。

她很快就发现了这个错误——ModAdd函数只适用于$$$[0,p)$$$范围内的数字,但问题中的数字可能超出了该范围。她很好奇这个错误的函数,所以她想知道它的结果。

然而,原来的代码运行速度太慢,所以她请你帮助她。

给定一个数组 $$$a_1,a_2,\ldots,a_n$$$ 和一个数字 $$$p$$$。 Nauuo 会进行 $$$m$$$ 查询,在每个查询中,你都会得到 $$$l$$$ 和 $$$r$$$,并且你必须计算 Sum(a,l,r,p) 的结果。您可以在上面的伪代码中看到 Sum 函数的定义。

请注意,上面代码中的整数不会溢出。

输入

第一行包含三个整数 $$$n$$$, $$$m$$$, $$$p$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le m \le 2 \cdot 10^5$$$, $$$1 \le p \le 10^9$$$) — 给定数组的长度,查询的数量和模数。请注意,模数仅在 ModAdd 函数中使用。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9\le a_i\le10^9$$$) — 给定数组。

在下面的 $$$m$$$ 行中,每行包含两个整数 $$$l$$$、$$$r$$$ ($$$1\le l\le r\le n$$$) — 您必须计算 Sum(a,l,r,p) 的结果。

输出

输出包含 $$$m$$$ 个整数,用于按给定顺序回答查询。

示例

输入 #1

4 5 6
7 2 -3 17
2 3
1 3
1 2
2 4
4 4

输出 #1

-1
0
3
10
11