Lexicographically Maximum Subsequence Query on a Flipped Bit String

Farmer John has a bit string of length \(N\) (\(1 \le N \le 10^9\)), initially all zeros. He then performs \(M\) update operations (\(1 \le M \le 2\cdot10^5\)). In each update, he flips every bit in the interval \([l, r]\) (i.e. changes a 0 to a 1 and vice versa).

After all the updates are done, he makes \(Q\) queries (\(1 \le Q \le 2\cdot10^5\)). Each query is given by three integers \(l, r, k\). Let \(S\) be the substring from index \(l\) to \(r\) (inclusive) of the final bit string. The task is to choose a subsequence of \(S\) of length \(k\) that is lexicographically maximum.

The lexicographical comparison is defined as follows: For two binary strings \(A = a_1a_2\dots a_k\) and \(B = b_1b_2\dots b_k\) of equal length, \(A\) is considered greater than \(B\) if there exists an index \(i\) such that \(a_j = b_j\) for all \(j b_i\). Equivalently, if you interpret the string as a binary number with \(a_1\) as the most significant bit, the larger binary number is considered lexicographically larger.

Your answer for a query is not the subsequence itself but an integer computed as follows. Suppose the chosen subsequence is \(s_1s_2\dots s_k\) (where each \(s_i\) is either 0 or 1). Then output

\(\displaystyle \sum_{i=0}^{k-1}2^i \cdot s_{k-i} \quad (\bmod\;10^9+7)\)

This is essentially the value of the binary number represented by the subsequence.

Note: A subsequence of a string is a sequence that can be obtained by deleting some (or none) of the characters without changing the order of the remaining characters.

inputFormat

The input begins with two integers \(N\) and \(M\) on the first line.

Then \(M\) lines follow, each containing two integers \(l\) and \(r\) describing an update operation.

Next, there is an integer \(Q\) indicating the number of queries.

Each of the next \(Q\) lines contains three integers \(l\), \(r\), and \(k\) representing a query.

outputFormat

For each query, output a single integer which is the computed value of the lexicographically maximum subsequence of length \(k\) from the corresponding substring after all updates, taken modulo \(10^9+7\).

sample

5 2
2 4
3 5
1
1 5 3

5