2030: [蓝桥杯2022初赛] 推导部分和

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:550 通过:151

题目描述

对于一个长度为N 的整数数列A[1], A[2], ... , A[N],小蓝想知道下标 l 到 r 的部分和 A[l] + A[l+1] + ... + A[r] 是多少?
然而,小蓝并不知道数列中每个数的值是多少,他只知道它的 M 个部分和的值。
其中第i 个部分和是下标 li 到 ri 的部分和:A[li] + A[li+1] + ... + A[ri],值是Si。

输入格式

第一行包含3个整数N、M和Q,分别代表数组长度、已知的部分和数量和询问的部分和数量。
接下来M行,每行包含3个整数 li, ri, Si。
接下来Q行,每行包含2个整数 l 和 r,代表小蓝想知道的部分和。
10%的测试数据:1≤N,M,Q≤10, -100≤Si≤100;
20%的测试数据:1≤N,M,Q≤20, -1000≤Si≤1000;
30%的测试数据:1≤N,M,Q≤50, -10000≤Si≤10000;
40%的测试数据:1≤N,M,Q≤1000, -10^6≤Si≤10^6;
60%的测试数据:1≤N,M,Q≤10000, -10^9≤Si≤10^9;
100%的测试数据:1≤N,M,Q≤10^5, -10^12≤Si≤10^12, 1≤li≤ri≤N,1≤l≤r≤N。
数据保证没有矛盾。

输出格式

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

输入样例 复制

5 3 3
1 5 15
4 5 9
2 3 5
1 5
1 3
1 2

输出样例 复制

15
6
UNKNOWN