10341: H

有一天，FQ在玩一个游戏。

FQ有个数组 a[1...k]，一开始 a[i] = i (1 ≤ i ≤ k)。然后FQ不断的对这个数组进行操作，每次的操作都是把这个数组的一个区间反转。

举例来说，FQ一开始有 a[1...5] = {1, 2, 3, 4, 5}。然后他将 a[2...4] 反转，数组就变成了 {1, 4, 3, 2, 5}；再将 a[2...5] 反转，就得到了 a[1...5] = {1, 5, 2, 3, 4}。

FQ总共对这个数组进行了 n 次操作，并把操作记录了下来。这个时候ZQ出场了，ZQ找到了FQ的记录，但是由于天气原因，FQ的记录不全——ZQ得到的记录是FQ全部记录下的操作序列的一个子串。ZQ就只得认为他得到的序列是FQ的全部操作。在ZQ看来，FQ的序列最终是什么样子的呢？

多组数据，第一行输入数据数 T(T ≤ 50)。

每组数据第一行为 k(1 ≤ k ≤ 20)，n(1 ≤ n ≤ 10⁵)。接下来 n 对整数 l, r(1 ≤ l ≤ r ≤ k) 表示FQ的 n 个操作。

再之后一个整数 q(1 ≤ q ≤ 10⁵)，表示q组查询。之后q行，每行是一对整数 x, y(1 ≤ x ≤ y ≤ n)，表示ZQ得到的记录是FQ记录的第x条到第y条。

对于每组数据的每组查询，你应该求出按照记录的第x条到第y条操作反转初始数组之后的结果。并对这个结果求哈希值。假设求得的序列是 b[1...k]，要求的哈希值是 (∑[1 ≤ i ≤ k] b[i] × 23ⁱ) mod 1000000007。

每组数据，你要输出的结果是所有查询的哈希值的和取模1000000007的余数。每组数据的结果占一行，共T行。

1
5 2
2 4
2 5
2
1 2
1 1

59391934