问题描述

对于一个长度为 $N$ 的整数数列 $A_{1}, A_{2}, \cdots A_{N}​$, 小蓝想知道下标 $l$ 到 $r$ 的部分和 $\sum_{i=l}^{r}=A_{l}+A_{l+1}+\cdots+A_{r}$​ 是多少?

然而, 小蓝并不知道数列中每个数的值是多少, 他只知道它的 $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}$。

输入格式

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

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

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

输出格式

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

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

15
6
UNKNOWN

评测用例规模与约定

对于 10% 的评测用例, $1 \leq N, M, Q \leq 10,-100 \leq A_{i} \leq 100$。

对于 20% 的评测用例, $1 \leq N, M, Q \leq 20,-1000 \leq A_{i} \leq 1000$。

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

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

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

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