You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个长度为 $N$ 的整数数列 $A_{1}, A_{2}, \cdots A_{N}$，已知它的 $M$ 个部分和的值。其中第 $i$ 个部分和是下标 $l_{i}$ 到 $r_{i}$ 的部分和 $\sum_{j=l_{i}}^{r_{i}}=A_{l_{i}}+A_{l_{i}+1}+\cdots+A_{r_{i}}$, 值是 $S_{i}$ 。现在想知道下标 $l$ 到 $r$ 的部分和 $\sum\limits_{i=l}^{r}A_i=A_{l}+A_{l+1}+\cdots+A_{r}$ 是多少？$Q$次询问。

输入格式

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

接下来 $M$ 行，每行包含 $3$ 个整数 $l_{i}, r_{i}, S_{i}$。

接下来 $Q$ 行，每行包含 $2$ 个整数 $l$ 和 $r$，代表一个小蓝想知道的部分和。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

15
6
UNKNOWN

样例输入 #2

6 6 5
3 4 -1013
3 6 -879
1 6 -866
1 6 -866
4 5 726
2 6 -342
1 2
4 6
3 4
3 4
2 4

样例输出 #2

13
UNKNOWN
-1013
-1013
-476

样例输入 #3

4 4 4
2 4 1050
4 4 1029
2 4 1050
1 2 339
2 3
3 3
1 2
3 4

样例输出 #3

21
UNKNOWN
339
UNKNOWN

提示

对于所有评测用例, $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$, $1 \leq l \leq r \leq N$ 。数据保证没有矛盾。

特殊性质A：对于$M$个部分和，$l_i=r_i$。

特殊性质B：对于$Q$个询问，有$l=r$。