El granjero John tiene una cadena binaria de longitud ~N~, inicialmente compuesta solo por ceros.

Primero, realizará ~M~ actualizaciones en la cadena, en orden. Cada actualización invierte el valor de cada carácter de ~l~ a ~r~. Específicamente, invertir un carácter lo cambia de 0 a 1, o viceversa.

Luego, te hará ~Q~ consultas. Para cada consulta, te pedirá que muestres la subsecuencia lexicográficamente más grande de longitud ~k~, compuesta por los caracteres de la subcadena desde ~l~ hasta ~r~. Si su respuesta es una cadena binaria ~s_1s_2 \ldots s_k~, entonces imprima ~\sum_{i=0}^{k-1} 2^i \cdot s_{k-i}~ (es decir, su valor interpretado como un número binario) módulo ~10^9+7~.

Una subsecuencia es una cadena que se puede derivar de otra eliminando algunos o ningún carácter sin cambiar el orden de los caracteres restantes.

Recuerde que la cadena ~A~ es lexicográficamente mayor que la cadena ~B~ de igual longitud si y solo si en la primera posición ~i~, si existe, donde ~A_i \neq B_i~, se cumple ~A_i > B_i~.

Entrada

• La primera línea contiene ~N~, ~M~ y ~Q~.
• Las siguientes ~M~ líneas contienen dos enteros, ~l~ y ~r~, que representan los extremos de cada actualización.
• Las siguientes ~Q~ líneas contienen tres enteros: ~l~, ~r~ y ~k~, que representan los extremos de cada consulta y la longitud de la subsecuencia.

Salida

Imprimir ~Q~ líneas. La i-ésima línea debe contener la respuesta a la i-ésima consulta.

Restricciones

• ~1 \leq N \leq 10^9~
• ~1 \leq M \leq 2 \cdot 10^5~
• ~1 \leq Q \leq 2 \cdot 10^5~
• ~1 \leq l \leq r \leq N~
• ~1 \leq l \leq r \leq N~
• ~1 \leq k \leq r-l + 1~

Puntuación

Entradas	Restricciones adicionales
4	~N \leq 10~, ~Q \leq 1000~
5	~M \leq 10~
6-7	~N, Q \leq 1000~
8-12	~N \leq 2 \cdot 10^5~
13-20	Sin restricciones adicionales

Ejempo #1 de Entrada

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

Ejempo #1 de Salida

21
13
7
3
1
5
5
3
1

Tras realizar las operaciones ~M~, la cadena resultante es ~10101~.

Para la primera consulta, solo existe una subsecuencia de longitud 5, ~10101~, que se interpreta como ~1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 0\cdot2^1 + 1 \cdot 2^0 = 21~.

Para la segunda consulta, hay 5 subsecuencias únicas de longitud 4: ~0101, 1101, 1001, 1011, 1010~. La subsecuencia lexicográficamente más larga es ~1101~, que se interpreta como ~1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 13~.

Para la tercera consulta, la secuencia lexicográficamente más larga es ~111~, que se interpreta como 7.

Ejempo #2 de Entrada

9 1 1
7 9
1 8 8

Ejempo #2 de Salida

3

Ejempo #3 de Entrada

30 1 1
1 30
1 30 30

Ejempo #3 de Salida

73741816

Asegúrese de mostrar la respuesta módulo ~10^9 + 7~.

USACO 2025 February Contest, Gold Problem 2. The Best Subsequence.