33730번 - The Best Subsequence 다국어

문제

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$.

입력

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 $Q$ lines. The $i$th line should contain the answer for the $i$th query.

제한

힌트