El jurado ha seleccionado un número entero $x$ del intervalo $[1, n]$. Tu tarea es adivinarlo. Para que no tengas que hacerlo completamente a ciegas, puedes realizar consultas. En cada consulta, puedes proporcionar un número entero $y$ del intervalo $[0, c]$, y nosotros te revelaremos el número de divisores de $x + y$.

Para complicar un poco la tarea, durante una única ejecución del programa deberás resolver $t$ casos de prueba. El número total de consultas que puedes realizar en ellos está limitado por $q$.

Interacción

Este es un problema interactivo. Debes escribir un programa que se comunique con el jurado utilizando la biblioteca proporcionada. Para usar la biblioteca, debes incluir lo siguiente en tu programa:

• C++: #include "dzilib.h"
• Python: from dzilib import GetT, GetN, GetQ, GetC, Ask, Answer

La biblioteca proporciona las siguientes funciones:

• GetT() – Devuelve el parámetro $t$, el número de casos de prueba a resolver.
• GetN() – Devuelve el parámetro $n$, el límite superior para los valores ocultos $x$.
• GetQ() – Devuelve el parámetro $q$, el límite para el número total de consultas que puedes realizar en todos los $t$ casos de prueba.
• GetC() – Devuelve el parámetro $c$, el límite para los valores $y$ que puedes proporcionar.
• Ask(y) – Devuelve el número de divisores positivos del número oculto $x$ incrementado en $y$. Debe cumplirse que $0 \le y \le c$.
• Answer(z) – Informa a la biblioteca que, en tu opinión, el valor oculto $x$ es $z$. No devuelve nada (en C++, la función es de tipo void).

En Python, todos los parámetros de las funciones de la biblioteca y los valores que devuelven son de tipo entero. En C++, los tipos aceptados y devueltos por las funciones son los mismos que en la biblioteca de ejemplo proporcionada, sobre la cual hay más información en la sección de Detalles de implementación.

En cualquier momento de la ejecución del programa (excepto al final), habrá un caso de prueba activo. El primer caso de prueba se activa inmediatamente después de iniciar el programa. Cuando un caso de prueba está activo, puedes realizar consultas usando la función Ask. Cuando consideres que conoces el valor oculto $x$, puedes indicarlo mediante la función Answer, y la biblioteca lo verificará. Si el valor proporcionado es incorrecto, la biblioteca finalizará la ejecución del programa con el veredicto "respuesta incorrecta". Si el valor del parámetro es correcto, la función terminará; si el caso de prueba resuelto no era el último, se activará el siguiente inmediatamente. Después de responder al último caso de prueba, debes finalizar la ejecución del programa. Si no lo haces e intentas usar la función Ask o Answer, recibirás el veredicto "respuesta incorrecta".

Puedes usar las funciones GetT, GetN, GetQ y GetC en cualquier momento de la ejecución del programa y los valores devueltos por ellas no cambiarán. Estas funciones no cuentan para el límite de consultas, pero consumen tiempo de procesador. El valor $q$ limita únicamente el número de llamadas a la función Ask. En el momento en que excedas el número total permitido de consultas, la biblioteca finalizará la ejecución del programa y recibirás el veredicto "respuesta incorrecta".

No debes leer datos de la entrada estándar ni escribir nada en la salida estándar. Los intentos deliberados de influir en el funcionamiento interno de la biblioteca de evaluación están prohibidos.

Los valores ocultos $x$ en todas las pruebas y su orden están predeterminados. Esto significa que la biblioteca con la que se comunica tu programa no será malintencionada y no adaptará su comportamiento a las acciones de tu programa.

Los límites indicados en el enunciado del problema se refieren únicamente al tiempo y la memoria que consumirá tu programa. Sin embargo, el tiempo de ejecución de la biblioteca y la memoria que utilice pueden depender de la prueba y del comportamiento exacto de tu programa. Por esta razón, los límites de tiempo y memoria en SIO2 son ligeramente superiores a los indicados en el enunciado.

Ejemplos

Entrada 1

2
1000000
10000
1000000000000000
1000
1

Salida 1

GetT()
GetN()
GetQ()
GetC()
Ask(1)
Ask(24)
Answer(1000)
GetT()
Answer(1)

Nota

En la prueba de ejemplo se cumple $t = 2$, $n = 10^6$, $q = 10^4$, $c = 10^{15}$, los valores ocultos son sucesivamente $1000$ y $1$. Se realizaron $2$ consultas Ask, lo cual está dentro del límite de $10\,000$ consultas. Recuerda que se cuenta el número total de consultas para todos los casos de prueba en una misma prueba.

Subtareas

Dentro de un grupo de pruebas, todas las pruebas tienen los mismos valores de $t$, $n$, $q$ y $c$, que se presentan en la siguiente tabla:

La prueba de ejemplo no pertenece a ningún grupo. Puedes resolverla, pero ten en cuenta que es posible obtener la puntuación completa sin resolverla.

Detalles de implementación

Las soluciones incorrectas de ejemplo y las bibliotecas de ejemplo en C++ y Python se encuentran en los archivos de la sección Pliki en SIO2. Estas soluciones y bibliotecas ilustran los tipos devueltos y aceptados por todas las funciones. Las bibliotecas de ejemplo pueden diferir en comportamiento de la que se utilizará para evaluar las soluciones, y pueden no cumplir con los supuestos del problema. Solo sirven para mostrar la forma de interactuar con el programa.

La solución dzi.cpp en C++ se puede compilar de la siguiente manera:

g++ -O3 -static -o dzi dzi.cpp dzilib.cpp -std=c++20

Debes asegurarte de que los archivos dzilib.h y dzilib.cpp se encuentren en la misma carpeta que la solución.

La solución dzi.py se puede ejecutar con el comando:

python dzi.py

Debes asegurarte de que el archivo dzilib.py se encuentre en la misma carpeta que la solución.

Tras la ejecución, al comienzo del funcionamiento del programa, la biblioteca recibe en la entrada estándar sucesivamente los valores $t$, $n$, $q$ y $c$, y luego los valores ocultos $x$ sucesivos. El archivo de entrada correspondiente a la prueba de ejemplo se encuentra en ambos archivos bajo el nombre dzi0.in.