题目描述

有 $n$ 个物品，物品 $i$ 有两个属性 $a_i, b_i$。对于一个物品集合 $S$，定义 $f(S)$ 是如下问题的答案：

• 对于每个物品 $i \in S$，选择 $0, a_i, b_i$ 三个数中的一个，使得所有物品选择的数之和是 $m$ 的倍数的方案数。

定义物品集合 $S = \{1, 2, \dots, n\}$。有 $q$ 次询问，每次给定四个正整数 $1 \le l_1 \le r_1 < l_2 \le r_2 \le n$，求： $$ \sum_{l_1 \le i \le r_1} \sum_{l_2 \le j \le r_2} f(S \setminus \{i, j\}) $$ 答案对 $10^9 + 7$ 取模。

输入格式

第一行，三个正整数 $n, m, q$。

接下来 $n$ 行，每行两个非负整数 $a_i, b_i$。

接下来 $q$ 行，每行四个正整数 $l_1, r_1, l_2, r_2$，表示一次询问。

输出格式

$q$ 行，每行一个非负整数，表示答案对 $10^9 + 7$ 取模后的值。

样例

输入

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

输出

33
9
11
80
37

数据范围

对于所有数据：

• $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$)

特殊性质 $A$：每次询问都在所有满足条件的 $(l_1, r_1, l_2, r_2)$ 中随机选择。

特殊性质 $B$：$q \le 10^5$。

特殊性质 $C$：对于每个物品 $i$，$a_i = b_i$。