Farmer John has a binary string of length N (1≤N≤109), initially all zeros.
He will first perform M(1≤M≤2⋅105) 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⋅105) 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 s1s2…sk, then output 
(that is, its value when interpreted as a binary number) modulo 109+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 Ai≠Bi, we have Ai>Bi.
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≤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.
OUTPUT FORMAT (print output to the terminal / stdout):
Output Q lines. The ith line should contain the answer for the ith 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⋅24+0⋅23+1⋅22+0⋅21+1⋅20=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⋅23+1⋅22+0⋅21+1⋅20=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 109 +7.
SCORING:
Input 4: N≤10,Q≤1000
Input 5: M≤10
Inputs 6-7: N,Q≤1000
Inputs 8-12: N≤2⋅105
Inputs 13-20: No additional constraints.
Problem credits: Chongtian Ma
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
