P8779 [Lanqiao Cup 2022 NOI Qualifier A] Deriving Partial Sums

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}$.

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.

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

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