Tiempo de espera
El alcalde Adam East quiere mejorar la red de transporte público de la ciudad de Harshel introduciendo la red de estaciones con monociclos. Cualquier persona que posea una tarjeta especial puede it a una estación y solicitar un monociclo para montar o dejar uno.
El procedimiento para solicitar un monociclo es sencillo. La persona entra en una cola. Si hay un monociclo disponible, la primera persona de la cola lo toma inmediatamente. De lo contrario, las personas en la cola esperan hasta que alguien deje caer un monociclo en la estación.
Sea el tiempo de espera el tiempo que la persona pasa entre la solicitud (entrada al cola) y la obtención de un monociclo. Si la persona no recibe un monociclo, entonces el tiempo de espera es infinito. El tiempo de espera total es la suma de los tiempos de espera de cada persona.
Adam ya conoce el horario de todas las personas para todos los días. Él sabe en qué momentos la gente solicita y deja monociclos en la Estación central que puede contener cualquier número de monociclos al mismo tiempo. Lo único que no sabe es cuántos monociclos deben colocarse allí al comienzo de cada día. Te hace varias preguntas para calcular el tiempo total de espera dado el número inicial de monociclos.
Entrada
La primera línea contiene y (), donde es el número total de solicitudes de monociclo y descargas de monociclo en la Estación Central, y es el número de preguntas que te hace Adam. Las siguientes líneas de describen las operaciones en la estación central. Cada línea contiene una descripción de la operación:
- cuando monociclos se dejan en la estación en el momento ;
- cuando personas solicitan monociclos en el momento ;
Para cada una de las operaciones descritas y . La última línea de la entrada contiene enteros diferentes () el número de monociclos al comienzo del día .
Las operaciones se dan en el orden de tiempo estrictamente creciente.
Salida
La salida constará de líneas. La línea -ésima mostrará el tiempo total de espera para el caso de monociclos al comienzo del día. Si el tiempo total de espera es infinito, entonces la línea correspondiente mostrará la palabra "".
Puntuación
En un 40% de los casos de prueba se tiene que , para todas las operaciones
Ejemplo de entrada
5 4
- 1 1
- 2 2
+ 4 1
- 6 1
+ 7 2
0 3 1 2
Ejemplo de salida
INFINITY
0
8
3
Comments