#P8779. [蓝桥杯 2022 省 A] 推导部分和

[蓝桥杯 2022 省 A] 推导部分和

题目描述

对于一个长度为 NN 的整数数列 A1,A2,ANA_{1}, A_{2}, \cdots A_{N},小蓝想知道下标 llrr 的部分和 $\sum\limits_{i=l}^{r}A_i=A_{l}+A_{l+1}+\cdots+A_{r}$ 是多少?

然而,小蓝并不知道数列中每个数的值是多少,他只知道它的 MM 个部分和的值。其中第 ii 个部分和是下标 lil_{i}rir_{i} 的部分和 $\sum_{j=l_{i}}^{r_{i}}=A_{l_{i}}+A_{l_{i}+1}+\cdots+A_{r_{i}}$, 值是 SiS_{i}

输入格式

第一行包含 3 个整数 NMN 、 MQQ。分别代表数组长度、已知的部分和数量 和询问的部分和数量。

接下来 MM 行,每行包含 33 个整数 li,ri,Sil_{i}, r_{i}, S_{i}

接下来 QQ 行,每行包含 22 个整数 llrr,代表一个小蓝想知道的部分和。

输出格式

对于每个询问, 输出一行包含一个整数表示答案。如果答案无法确定, 输出 UNKNOWN

5 3 3
1 5 15
4 5 9
2 3 5
1 5
1 3
1 2
15
6
UNKNOWN

提示

对于 10%10 \% 的评测用例, 1N,M,Q10,100Si1001 \leq N, M, Q \leq 10,-100 \leq S_{i} \leq 100

对于 20%20 \% 的评测用例, 1N,M,Q20,1000Si10001 \leq N, M, Q \leq 20,-1000 \leq S_{i} \leq 1000

对于 30%30 \% 的评测用例, $1 \leq N, M, Q \leq 50,-10000 \leq S_{i} \leq 10000$ 。

对于 40%40 \% 的评测用例, $1 \leq N, M, Q \leq 1000,-10^{6} \leq S_{i} \leq 10^{6}$ 。

对于 60%60 \% 的评测用例, $1 \leq N, M, Q \leq 10000,-10^{9} \leq S_{i} \leq 10^{9}$ 。

对于所有评测用例, $1 \leq N, M, Q \leq 10^{5},-10^{12} \leq S_{i} \leq 10^{12}, 1 \leq l_{i} \leq r_{i} \leq N$, 1lrN1 \leq l \leq r \leq N 。数据保证没有矛盾。

蓝桥杯 2022 省赛 A 组 J 题。