gold_The_Best_Subsequence (USACO February_Contest)
Time limit: 2 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: data structures, segment tree, greedy, coordinate compression

Farmer John has a binary string of length $N$ $(1 \leq N \leq 10^9)$, initially
all zeros.
He will first perform $M$ ($1 \leq M \leq 2 \cdot 10^5$) updates on the string,
in order.  Each update flips every character from $l$ to $r$. Specifically,
flipping a character changes it from $0$ to $1$, or vice versa.
Then, he asks you $Q$ ($1 \leq Q \leq 2 \cdot 10^5$) queries. For each query, he
asks you to output the lexicographically greatest subsequence of length $k$
comprised of characters from the substring from $l$ to $r$. If your answer is a
binary string $s_1s_2 \dots s_k$, then output
$\sum_{i=0}^{k-1} 2^i \cdot s_{k-i}$ (that is, its value when interpreted as a
binary number) modulo $10^9+7$.
A subsequence is a string that can be derived from another string by deleting
some or no characters without changing the order of the remaining characters.
Recall that string $A$ is lexicographically greater than string $B$ of equal
length if and only if at the first position $i$, if it exists, where
$A_i \neq B_i$, we have $A_i > B_i$.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains $N$, $M$, and $Q$.
The next $M$ lines contain two integers, $l$ and $r$ ($1 \leq l \leq r \leq N$)
— the endpoints of each update.
The next $Q$ lines contain three integers, $l$, $r$, and $k$
($1 \leq l \leq r \leq N, 1 \leq k \leq r - l + 1$) — the endpoints of each
query and the length of the subsequence.
OUTPUT FORMAT (print output to the terminal / stdout):
Output $Q$ lines. The $i$th line should contain the answer for the $i$th query.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
21
13
7
3
1
5
5
3
1
After performing the $M$ operations, the string is $10101$.
For the first query, there is only one subsequence of length $5$, $10101$, which
is interpreted as
$1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 21$.
For the second query, there are $5$ unique subsequences of length $4$: $0101$,
$1101$, $1001$, $1011$, $1010$. The lexicographically largest subsequence is
$1101$, which is interpreted as
$1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1\cdot 2^0 = 13$.
For the third query, the lexicographically largest sequence is $111$, which is
interpreted as $7$.
SAMPLE INPUT:
9 1 1
7 9
1 8 8
SAMPLE OUTPUT:
3
SAMPLE INPUT:
30 1 1
1 30
1 30 30
SAMPLE OUTPUT:
73741816
Make sure to output the answer modulo $10^9+7$.
SCORING:
Input 4: $N \leq 10, Q \leq 1000$
Input 5: $M \leq 10$
Inputs 6-7: $N, Q \leq 1000$
Inputs 8-12: $N \leq 2 \cdot 10^5$
Inputs 13-20: No additional constraints.
Problem credits: Chongtian Ma

Starter code:

Grader code:

Setup script:

Evaluation script: