题目描述

Farmer John 有一个长为 $N$ 的位串（$1 \leq N \leq 10^9$），初始时全部为零。

他将首先按顺序对字符串执行 $M$ 次更新（$1 \leq M \leq 2 \cdot 10^5$）。每次更新会翻转从 $l$ 到 $r$ 的每个字符。具体地说，翻转一个字符会将其从 $0$ 变为 $1$，或反之。

然后，他会进行 $Q$ 次查询（$1 \leq Q \leq 2 \cdot 10^5$）。对于每个查询，他要求你输出由从 $l$ 到 $r$ 的子串中的字符组成的长为 $k$ 的字典序最大子序列。如果你的答案是一个位串 $s_1s_2 \dots s_k$，则输出 $\sum_{i=0}^{k-1} 2^i \cdot s_{k-i}$（即将其解释为二进制数时的值）模 $10^9+7$ 的余数。

一个字符串的子序列是可以从中通过删除一些或不删除字符而不改变余下字符的顺序得到的字符串。

我们知道，字符串 $A$ 的字典序大于长度相等的字符串 $B$，当且仅当在第一个 $A_i \neq B_i$ 的位置 $i$ 上（如果存在），我们有 $A_i > B_i$。

输入格式

输入的第一行包含 $N$，$M$ 和 $Q$。

以下 $M$ 行，每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq N$），为每次更新的端点。

以下 $Q$ 行，每行包含三个整数 $l$，$r$ 和 $k$（$1 \leq l \leq r \leq N$，$1 \leq k \leq r - l + 1$），为每个查询的端点和子序列的长度。

输出格式

输出 $Q$ 行。第 $i$ 行包含第 $i$ 个查询的答案。

5 3 9
1 5
2 4
3 3
1 5 5
1 5 4
1 5 3
1 5 2
1 5 1
2 5 4
2 5 3
2 5 2
2 5 1

21
13
7
3
1
5
5
3
1

9 1 1
7 9
1 8 8

3

30 1 1
1 30
1 30 30

73741816

提示

样例 1 解释：

在执行 $M$ 次操作后，位串为 $10101$。

对于第一个查询，长度为 $5$ 的子序列仅有一个，$10101$，其解释为 $1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 21$。

对于第二个查询，长度为 $4$ 的不同的子序列有 $5$ 个：$0101$，$1101$，$1001$，$1011$，$1010$。字典序最大的子序列为 $1101$，其解释为 $1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1\cdot 2^0 = 13$。

对于第三个查询，字典序最大的序列是 $111$，其解释为 $7$。

样例 3 解释：

确保输出答案对 $10^9+7$ 取模。

• 测试点 $4$：$N \leq 10, Q \leq 1000$。
• 测试点 $5$：$M \leq 10$。
• 测试点 $6\sim 7$：$N, Q \leq 1000$。
• 测试点 $8\sim 12$：$N \leq 2 \cdot 10^5$。
• 测试点 $13\sim 20$：没有额外限制。