There are $n$ items, where item $i$ has two attributes $a_i$ and $b_i$. For a set of items $S$, define $f(S)$ as the answer to the following problem:

• For each item $i \in S$, choose one of the three values $0, a_i, b_i$ such that the sum of the chosen values for all items is a multiple of $m$. Find the number of such ways.

Define the set of all items as $S = \{1, 2, \dots, n\}$. There are $q$ queries. Each query provides four positive integers $1 \le l_1 \le r_1 < l_2 \le r_2 \le n$. Calculate: $$ \sum_{l_1 \le i \le r_1} \sum_{l_2 \le j \le r_2} f(S \setminus \{i, j\}) $$ The answer should be taken modulo $10^9 + 7$.

Input

The first line contains three positive integers $n, m, q$.

The next $n$ lines each contain two non-negative integers $a_i, b_i$.

The next $q$ lines each contain four positive integers $l_1, r_1, l_2, r_2$, representing a query.

Output

Output $q$ lines, each containing a non-negative integer representing the answer modulo $10^9 + 7$.

Examples

Input 1

6 10 5
2 3
7 1
1 4
8 1
2 5
8 9
1 2 3 4
1 1 2 2
1 1 5 5
1 3 4 6
1 5 6 6

Output 1

33
9
11
80
37

Constraints

For all data:

• $1 \le n \le 10^4$
• $2 \le m \le 200$
• $1 \le q \le 10^6$
• $0 \le a_i, b_i < m$ ($1 \le i \le n$)

Special Property $A$: Each query is chosen randomly from all valid $(l_1, r_1, l_2, r_2)$ tuples.

Special Property $B$: $q \le 10^5$.

Special Property $C$: For each item $i$, $a_i = b_i$.