Exclusión de subsegmentos de bits#13086
Se te da un arreglo binario de longitud , donde cada elemento a_i \in \{0, 1\}.
Debes responder consultas independientes. En cada consulta se te da un rango [l, r] (1 \le l \le r \le n).
Para cualquier secuencia binaria b = [b_1, b_2, \dots, b_k] de longitud k \ge 1, su valor numérico se define anteponiendo implícitamente un bit '1' a la secuencia. Formalmente, el valor se calcula como:
Por ejemplo:
[0] \rightarrow 10_2 = 2
[1] \rightarrow 11_2 = 3
[0, 0] \rightarrow 100_2 = 4
[0, 1] \rightarrow 101_2 = 5
Para cada consulta [l, r], tu tarea es encontrar una secuencia binaria que NO aparezca como subsegmento contiguo en el subarreglo a[l \dots r], de modo que val(b) sea estrictamente mínimo.
Imprime este valor mínimo módulo .
La primera línea contiene un único entero (1 \le t \le 10^4) — el número de casos de prueba.
La primera línea de cada caso de prueba contiene dos enteros y (1 \le n, q \le 2 \cdot 10^5) — la longitud del arreglo binario y el número de consultas.
La segunda línea de cada caso de prueba contiene enteros separados por espacios a_1, a_2, \dots, a_n (a_i \in \{0, 1\}) — los elementos del arreglo.
Las siguientes líneas describen las consultas. Cada línea contiene dos enteros y (1 \le l \le r \le n) — los límites del rango de la consulta.
Se garantiza que tanto la suma de como la suma de sobre todos los casos de prueba no exceden 2 \cdot 10^5.
Para cada consulta, imprime un único entero en una nueva línea — el mínimo valor numérico de una secuencia binaria que no aparece como subsegmento contiguo en a[l \dots r], módulo .
Ejemplo 1
En el primer caso de prueba, el arreglo es a = [0, 1, 0].
En la primera consulta , los subsegmentos contiguos presentes son [0], [1], [0, 1], [1, 0] y [0, 1, 0]. Sus valores decimales respectivos son 2, 3, 5, 6 y . El menor valor que no se forma es , que corresponde a la secuencia .
En la segunda consulta , el subarreglo es . Los subsegmentos presentes son y . El menor valor ausente es de nuevo (secuencia ).
En la tercera consulta , el subarreglo es . El único subsegmento presente es (valor ). El menor valor ausente es (secuencia ).
En el segundo caso de prueba, el arreglo es a = [1, 1, 1, 1]. Para la consulta , la secuencia (valor ) nunca aparece, por lo que la respuesta es .
En el tercer caso de prueba, el arreglo es a = [1, 0, 0, 1].
Para la consulta , el subarreglo es [1, 0, 0]. Contiene [0], [1], [0, 0], [1, 0] (valores 2, 3, 4, 6). El menor valor ausente es (secuencia ).
Para la consulta , el subarreglo es [0, 0, 1]. Contiene [0], [1], [0, 0], [0, 1] (valores 2, 3, 4, 5). El menor valor ausente es (secuencia ).
Para la consulta , el subarreglo contiene los valores 2, 3, 4, 5 y . El menor valor ausente es (secuencia ).
Subtarea 1 (100 puntos): \sum n \le 2000 y \sum q \le 2000.
Subtarea 2 (150 puntos): \sum n \le 40000 y \sum q \le 40000.
Subtarea 3 (250 puntos): Sin restricciones adicionales.