CF1172F Nauuo and Bug

Nauuo 是一个热爱编程的女孩。 有一天，她正在解决一个需要计算若干数对 $p$ 取模和的问题。 她写了如下代码，但得到了“Wrong answer”的判定。  她很快发现了 bug —— 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 \times 10^5$，$1 \le p \le 10^9$），分别表示数组长度、询问次数和模数。注意，模数仅在 ModAdd 函数中使用。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$），表示给定的数组。 接下来的 $m$ 行，每行包含两个整数 $l$、$r$（$1 \le l \le r \le n$），表示你需要计算 Sum(a, l, r, p) 的结果。

输出 $m$ 个整数，按询问顺序依次给出每个询问的答案。

由 ChatGPT 4.1 翻译