SP10611 RRANGE - Ranges

有 $N$ 个连续排列的单元格，编号从 $1$ 到 $N$。每个单元格初始时的值都是 $0$。可以通过以下方式更新某一段连续的区间： 1. 选择一个区间 $[i, j]$，其中 $i < j$。 2. 对于这个区间，将第 $i$ 个单元格的值增加 $1$，第 $i + 1$ 个单元格的值增加 $2$，以此类推，直到第 $j$ 个单元格，其值增加 $j - i + 1$。 例如，假如 $N = 7$，并且执行了两次更新操作：先更新区间 $[3, 6]$，再更新区间 $[4, 7]$，状态变化如下： 初始状态：{0, 0, 0, 0, 0, 0, 0} 更新 $[3, 6]$ 后：{0, 0, 1, 2, 3, 4, 0} 更新 $[4, 7]$ 后：{0, 0, 1, 3, 5, 7, 4} 在经过这些更新后，你需要回答以下类型的问题： 1. 选择一个区间 $[u, v]$，其中 $u < v$。 2. 计算并输出该区间内所有单元格值的和，然后对 10,000 取模后的结果。 给定 $N$ 和 $U$ 次更新区间。你需要编写一个程序，能够回答 $Q$ 个问题。

第一行包含三个整数：$N$（$1 \le N \le 1,000,000,000$），$U$ 和 $Q$（$1 \le U, Q \le 1,000$），分别表示单元格数量、更新操作数量和要回答的问题数量。 接下来的 $U$ 行，每行包含两个整数 $i$ 和 $j$（$1 \le i < j \le N$），表示一次更新操作的区间。 接下来的 $Q$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u < v \le N$），表示需要回答的问题区间。

对于每个问题区间 $[u, v]$，输出该区间内所有单元格的值之和，并对 10,000 取模后的结果。 **本翻译由 AI 自动生成**