There are N contiguous cells numbered from 1 to N. Initially, each cell contains a 0 in it. A sub-contiguous group of cells can be updated this way:

• A range [i, j] is defined such that i < j
• The cell numbered i is added 1; the cell numbered i + 1 is added 2, and so on until the cell numbered j is reached and added j – i + 1

For example, if N = 7 and the updates [3, 6] and [4, 7] were performed, this is what would happen.

• Initially: {0, 0, 0, 0, 0, 0, 0}
• Update [3, 6]: {0, 0, 1, 2, 3, 4, 0}
• Update [4, 7]: {0, 0, 1, 3, 5, 7, 4}

After performing some update operations, it would be amazing to answer questions like the following:

• A range [u, v] is defined such that u < v.
• The answer is the sum of every cell in the range [u, v] (both u and v are included) modulus 10,000.

Given N and U updates ranges. You have to write a program capable of answering Q questions.

Input

The first line contains three integers: N (1 ≤ N ≤ 1, 000,000,000), U and Q (1 ≤ U, Q ≤ 1, 000), representing the number of cells, the number of update operations, and the number of questions respectively.

Each of the following U lines contains two integers i and j (1 ≤ i < j ≤ N) separated by a single space indicating an update operation.

Each of the following Q lines contains two integers u and v (1 ≤ u < v ≤ N) separated by a single space indicating a question.

Output

For each question [u, v] you must print the sum of all contiguous cells starting at u and ending at v modulus 10,000.

Example

Input:
7 2 2
3 6
4 7
4 6
1 7

Output:
15
20