Problems
Farmer John has a binary string of length N (1 ≤ N ≤ 10⁹), initially consisting entirely of zeros.
He then performs M (1 ≤ M ≤ 2⋅10⁵) updates on the string, in order. Each update flips every character from position l to r - turning 0s into 1s and 1s into 0s.
After all updates, he poses Q (1 ≤ Q ≤ 2⋅10⁵) queries. For each query, you are given integers l, r, and k (1 ≤ k ≤ r-l+1); you must output the lexicographically greatest subsequence of length k from the substring spanning positions l to r. If the resulting binary string is s₁s₂…sₖ, then you should output
∑₍i=0₎^(k -1) 2ⁱ ⋅ s₍k -i₎
(i.e. its value when interpreted as a binary number) modulo 10⁹+7.
Recall that a subsequence is obtained by deleting some or no characters without changing the order of the remaining characters, and for binary strings of equal length, the one with a 1 in the first differing position is considered lexicographically greater.
Input
The first line contains three integers N, M, and Q.
The next M lines each contain two integers l and r (1 ≤ l ≤ r ≤ N), representing an update that flips every character from position l to r.
The following Q lines each contain three integers l, r, and k (1 ≤ l ≤ r ≤ N, 1 ≤ k ≤ r-l+1), which specify the interval for the query and the length of the subsequence to extract.
Output
For each query, determine the lexicographically greatest subsequence of length k from the substring between positions l and r.
Interpret this subsequence as a binary number and output its value modulo 10⁹+7, with each answer on a new line.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 10 | |
| #2 | 10 | |
| #3 | 20 | |
| #4 | 30 | |
| #5 | 30 | No additional constraints |
Example #1
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
For the first query, the only subsequence of length 5 is "10101", which, when interpreted as a binary number, equals 21.
For the second query, among all subsequences of length 4 in the interval [1,5], the lexicographically greatest is "1101", which equals 13.
For the third query, the lexicographically greatest subsequence of length 3 is "111", which equals 7.
The remaining queries are evaluated similarly.
Example #2
9 1 1
7 9
1 8 8
3
A single update flips the characters in positions 7 to 9. Then, the query asks for the lexicographically greatest subsequence of length 8 from positions 1 to 8. The answer, when computed as specified, is 3.
Example #3
30 1 1
1 30
1 30 30
73741816
After the update on the entire string, the query asks for the lexicographically greatest subsequence of length 30 from positions 1 to 30. Its binary interpretation modulo 10⁹+7 is 73741816.
You must sign in to write code.