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