Serafim y su Raspberry Pi

Serafim está montando el proyecto de su vida: *Camarero*, una aplicación de plataforma full-stack de gestión de restaurantes con un chatbot de recomendaciones personalizado que actúa como un "camarero virtual" y que atiende pedidos mediante un modelo LLM. Y, como todo gran genio con poco presupuesto, ha decidido que el servidor de producción será... su *Raspberry Pi*, esa que tenía criando polvo en un cajón. El modelo LLM se ejecuta por capas, y la *Raspberry Pi* mantiene una secuencia de $n$ enteros $a_1, a_2, \ldots, a_n$, donde $a_i$ representa la memoria libre (en KB, que aquí no sobra nada) del bloque $i$ de la placa. Mientras Serafim conecta el servidor y despliega *Camarero*, la *Raspberry Pi* debe procesar $q$ eventos de tres tipos: - $\textbf{1 $l$ $r$ $x$}$: el LLM carga (o libera, si $x < 0$) tensores en los bloques del $l$ al $r$: sumar $x$ a todos los $a_i$ con $l \le i \le r$. - $\textbf{2 $l$ $r$}$: Serafim, sudando frío, quiere saber cuál es el bloque más saturado del rango: responder el valor mínimo en el intervalo $[l, r]$. - $\textbf{3 $k$}$: hay que colocar una capa del modelo que necesita al menos $k$ KB: responder la posición del primer bloque (de izquierda a derecha) con $a_i \ge k$. Si ningún bloque puede con ella, responder $-1$ (y Serafim tendrá que escuchar el ventilador llorar). Ayuda a Serafim a implementar el gestor de memoria antes de que el primer cliente pida una paella y *Camarero* se quede pensando la respuesta hasta el postre. ## Entrada La primera línea contiene dos enteros $n$ y $q$ ($1 \le n, q \le 2 \cdot 10^5$), que indican el número de bloques de memoria de la *Raspberry Pi* y el número de eventos, respectivamente. La segunda línea contiene $n$ enteros $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$), que indican la memoria libre inicial de cada bloque (sí, puede ser negativa: la *Raspberry Pi* de Serafim hace *swap* con mucho optimismo). Cada una de las siguientes $q$ líneas describe un evento en uno de los formatos anteriores, con $1 \le l \le r \le n$, $-10^9 \le x \le 10^9$ y $-10^{18} \le k \le 10^{18}$. ## Salida Para cada evento de tipo $2$ o $3$, imprime la respuesta en una línea.

5 6
2 -1 4 4 0
2 1 5
3 4
1 2 4 3
2 1 3
3 7
3 100

-1
3
2
3
-1