2053: [USACO 2025 February Contest, Gold] Problem 2. The Best Subsequence

Farmer John has a binary string of length N (1 ≤ N ≤ 10⁹), initially all zeros.

He will first perform M (1 ≤ M ≤ 2⋅10⁵) 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 ≤ Q ≤ 2⋅10⁵) 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₁ s₂ … s_k, then output ∑^k−1_i=0  (2ⁱ ⋅ s_k−i) (that is, its value when interpreted as a binary number) modulo 10⁹+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 ≠ B_i, we have A_i > B_i.

The first line contains N, M, and Q.

The next M lines contain two integers, l and r (1 ≤ l ≤ r ≤ N) — the endpoints of each update.

The next Q lines contain three integers, l, r, and k (1 ≤ l ≤ r ≤ N, 1 ≤ k ≤ r − l + 1) — the endpoints of each query and the length of the subsequence.

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