RRANGE  Ranges
There are N contiguous cells numbered from 1 to N. Initially, each cell contains a 0 in it. A subcontiguous group of cells can be updated this way:
1) A range [i,j] is defined such that i < j
2) 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:
1) A range [u,v] is defined such that u < v
2) 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
hide comments
fanatique:
20140615 09:58:28
can't we solve using BIT? 

aristofanis:
20140614 17:41:33
@npsabari: It can be solved with segment tree with complexity O((U+Q) log N), although


npsabari:
20140128 10:14:43
Did anyone manage to solve it in complexity better than O(U*Q)? 

rahul kumar:
20131217 21:39:44
nice problem...:P 

Vikas Kushwaha:
20130118 06:57:28
Such a nice question..


Ehor Nechiporenko:
20121225 09:48:13
So NICE!! 

DaRksTar:
20120705 10:54:14
weird !!


Romal Thoppilan:
20120705 07:14:46
Tough time debugging .. !


Angel Paredes:
20120220 03:58:40
Both updates and questions are defined by two integers between 1 and N, so the test case you are asking for is incorrect.

Added by:  Angel Paredes 
Date:  20120213 
Time limit:  0.124s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Copa Lenin 2012  Level 1 