In an $n \times m$ grid graph with obstacles, we denote the cell in the $x$-th row and $y$-th column as $(x, y)$. A cycle in the grid is called a valid simple cycle if it satisfies the following two conditions:

1. It does not pass through any obstacle.
2. It does not self-intersect.

There are $Q$ queries. For each query, determine how many valid simple cycles pass through the edge between $(x, y)$ and $(x+1, y)$.

Input

The first line contains three non-negative integers $n$, $m$, and $k$, representing an $n \times m$ grid graph with $k$ obstacles.

The next $k$ lines each contain two positive integers $x, y$ $(1 \leq x \leq n, 1 \leq y \leq m)$, representing that $(x, y)$ is an obstacle (duplicates are possible).

The next line contains an integer $Q$, representing the number of queries.

The next $Q$ lines each contain two positive integers $x, y$ $(1 \leq x \leq n-1, 1 \leq y \leq m)$, asking for the number of valid simple cycles that pass through the edge between cell $(x, y)$ and $(x+1, y)$.

Output

Output $Q$ lines, each corresponding to a query. Please output the answer modulo $(1000000000+7)$.

Examples

Input

4 4 4
2 2
2 4
3 2
4 4
4
1 1
1 4
3 3
2 2

Output

1
0
1
0

Input

1000 2 10
426 2
595 2
665 1
447 2
604 2
202 1
26 1
79 1
291 2
6 2
10
932 1
857 2
31 1
458 1
793 1
691 1
438 1
404 1
541 1
872 2

Output

18156
27456
235
1496
26496
8034
96
2373
4982
26496

Constraints