Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
55 - ZOJ Monthly, September 2006 - 1002
Sum of Continuous Subsequences

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Now you play the following game with your friend. Your friend writes down a sequence of numbers. He chooses some continuous subsequences (for example the subsequence from the second to the fifth number inclusively), and tells you the sums of the subsequences. Then he chooses some other continuous sequences and asks you the sums of them. Can you answer the questions?

Input

Input consists of multiple cases.

The first of each case contain three integer n, m and k(1 ≤ n ≤ 5000, 0 ≤ m, k ≤ 10000).Integer n is the length of the subsequences, m is the number of sums which your friend tells you, k is the number of questions you should answer. There are three integers a, b and s (1 ≤ a ≤ b ≤ n, -100,000,000 ≤ s ≤ 100,000,000) in the following m lines. They mean the sum of the subsequence from the a th to the b th number inclusively is s. Each of the following k lines contains two integer c, d(1 ≤ c ≤ d ≤ n).

Output

You should output the sum of the continuous subsequences from c th to d th number in a single line for each question. If you can't find the answer output "UNKNOWN" in a single line.

Output one blank line after each test case.

Hint:

Input will not be self-contradictory

Sample Input

10 5 5
1 5 4
2 5 4
3 6 5
1 9 9
6 6 2
1 9
2 6
1 2
3 5
1 7

Sample Output

9
6
1
3
UNKNOWN

Author: ZHANG, Zhetao


Submit    Status