Problem Description

Given an integer sequence $A_{1}, A_{2}, \cdots A_{N}$ of length $N$, Xiao Lan wants to know the partial sum from index $l$ to $r$, i.e., $\sum\limits_{i=l}^{r} A_i = A_{l} + A_{l+1} + \cdots + A_{r}$.

However, Xiao Lan does not know the value of each number in the sequence. He only knows the values of $M$ partial sums. The $i$-th partial sum is the sum from index $l_{i}$ to $r_{i}$, i.e., $\sum_{j=l_{i}}^{r_{i}} A_j = A_{l_{i}} + A_{l_{i}+1} + \cdots + A_{r_{i}}$, and its value is $S_{i}$.

Input Format

The first line contains $3$ integers $N, M, Q$, representing the array length, the number of known partial sums, and the number of queried partial sums.

The next $M$ lines each contain $3$ integers $l_{i}, r_{i}, S_{i}$.

The next $Q$ lines each contain $2$ integers $l$ and $r$, representing a partial sum that Xiao Lan wants to know.

Output Format

For each query, output one line containing one integer as the answer. If the answer cannot be determined, output UNKNOWN.

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

15
6
UNKNOWN

Hint

For $10\%$ of the test cases, $1 \leq N, M, Q \leq 10$, $-100 \leq S_{i} \leq 100$.

For $20\%$ of the test cases, $1 \leq N, M, Q \leq 20$, $-1000 \leq S_{i} \leq 1000$.

For $30\%$ of the test cases, $1 \leq N, M, Q \leq 50$, $-10000 \leq S_{i} \leq 10000$.

For $40\%$ of the test cases, $1 \leq N, M, Q \leq 1000$, $-10^{6} \leq S_{i} \leq 10^{6}$.

For $60\%$ of the test cases, $1 \leq N, M, Q \leq 10000$, $-10^{9} \leq S_{i} \leq 10^{9}$.

For all test cases, $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$. The testdata guarantees that there are no contradictions.

Lanqiao Cup 2022 Provincial Contest A Group, Problem J.

Translated by ChatGPT 5