Robot Selection and Dominance

You are given a set of n people. Each person has two integer parameters \(a_i\) and \(b_i\). We say person \(i\) is stronger than person \(j\) if and only if \(a_i > a_j\) and \(b_i > b_j\).

Your task is to add exactly \(K\) robots. You can choose the parameters for each robot arbitrarily subject to the following two conditions:

1. No two robots have the same pair of parameters.
2. For each robot, there exists at least one person in the group who is stronger than the robot. In other words, for a robot with parameters \((x,y)\), there must exist a person with parameters \((a_i,b_i)\) satisfying \(a_i > x\) and \(b_i > y\); equivalently, the point \((x,y)\) lies in the rectangle \([0,a_i)\times[0,b_i)\).

Initially, you are given the parameters of n people. Then, there will be Q queries. In each query a new person (newcomer) is introduced. For each query, consider the group consisting of the initial n people and the newcomer. Let the set of all valid integer coordinate points (\(x,y\) with \(x,y \ge 0\)) where a robot can be placed be defined as:

[ R = { (x,y) \in \mathbb{Z}_{\ge 0}^2 \mid \exists; \text{person } (a,b) \text{ in the current group such that } x < a \text{ and } y < b }. ]

Your task for each query is to compute the number of ways to choose K distinct valid points from \(R\). Since the answer can be large, output it modulo 10009.

Note: The number of valid points \(|R|\) can be computed as follows. Define a function

[ f(x) = \max{b : \text{there exists a person with parameters } (a,b) \text{ and } a > x}, ]

for (x) from (0) to (X-1) where (X = \max{a \text{ among persons}}). Then the number of valid points is given by

[ |R| = \sum_{x=0}^{X-1} f(x). ]

inputFormat

The first line of input contains three integers: n (the number of initial people), \(K\) (the number of robots), and Q (the number of queries).

The next n lines each contain two integers \(a_i\) and \(b_i\), representing the parameters of the initial people.

The following Q lines each contain two integers representing the parameters of the newcomer for that query.

outputFormat

For each query, output a single integer on a new line, representing the number of valid schemes to choose \(K\) robots (i.e. choose \(K\) distinct points from the valid set \(R\)) modulo 10009.

sample

2 1 1
5 1
1 5
3 3

13

</p>