RRANGE - Ranges

no tags 

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:

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: 2014-06-15 09:58:28

can't we solve using BIT?

aristofanis: 2014-06-14 17:41:33

@npsabari: It can be solved with segment tree with complexity O((U+Q) log N), although
the implementation will be very tricky... Notice that one should perform some kind of
space reduction in order to get AC.

Last edit: 2014-06-14 17:42:09
npsabari: 2014-01-28 10:14:43

Did anyone manage to solve it in complexity better than O(U*Q)?

rahul kumar: 2013-12-17 21:39:44

nice problem...:P

Vikas Kushwaha: 2013-01-18 06:57:28

Such a nice question..
enjoyed solving it...

Ehor Nechiporenko: 2012-12-25 09:48:13

So NICE!!

DaRksTar: 2012-07-05 10:54:14

weird !!

Romal Thoppilan: 2012-07-05 07:14:46

Tough time debugging .. !

Angel Paredes: 2012-02-20 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.

There are no tricky test cases. Everything should go fine with the proper solution.

Last edit: 2012-02-20 04:02:09

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