The Best Subsequence

문제

Farmer John has a binary string of length $NN$ $(1\le N\le {10}^9)(1\; \backslash leq\; N\; \backslash leq\; 10^9)$, initially all zeros.

He will first perform $MM$ ($1\le M\le 2\cdot {10}^{5}1\; \backslash leq\; M\; \backslash leq\; 2\; \backslash cdot\; 10^5$) updates on the string, in order. Each update flips every character from $ll$ to $rr$. Specifically, flipping a character changes it from $00$ to $11$, or vice versa.

Then, he asks you $QQ$ ($1\le Q\le 2\cdot {10}^{5}1\; \backslash leq\; Q\; \backslash leq\; 2\; \backslash cdot\; 10^5$) queries. For each query, he asks you to output the lexicographically greatest subsequence of length $kk$ comprised of characters from the substring from $ll$ to $rr$. If your answer is a binary string $s_1{s}_2\dots s_{k}s\_1s\_2\; \backslash dots\; s\_k$, then output ${\sum }_{i=0}^{k-1}{2}^i\cdot s_{k-i}\backslash sum\_\{i=0\}^\{k-1\}\; 2^i\; \backslash cdot\; s\_\{k-i\}$ (that is, its value when interpreted as a binary number) modulo ${10}^9+710^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 $AA$ is lexicographically greater than string $BB$ of equal length if and only if at the first position $ii$, if it exists, where $A_i\mathrm{\ne }{B}_{i}A\_i\; \backslash neq\; B\_i$, we have $A_i>B_{i}A\_i\; >\; B\_i$.

입력

The first line contains $NN$, $MM$, and $QQ$.

The next $MM$ lines contain two integers, $ll$ and $rr$ ($1\le l\le r\le N1\; \backslash leq\; l\; \backslash leq\; r\; \backslash leq\; N$) — the endpoints of each update.

The next $QQ$ lines contain three integers, $ll$, $rr$, and $kk$ ($1\le l\le r\le N,1\le k\le r-l+11\; \backslash leq\; l\; \backslash leq\; r\; \backslash leq\; N,\; 1\; \backslash leq\; k\; \backslash leq\; r\; -\; l\; +\; 1$) — the endpoints of each query and the length of the subsequence.

출력

Output $QQ$ lines. The $ii$th line should contain the answer for the $ii$th query.

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

9 1 1
7 9
1 8 8

3

30 1 1
1 30
1 30 30

73741816