Tiempo de espera


Submit solution


Points: 100 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Prolog, Python, Swift, VB

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 n y q (1 \leq n, q \leq 10 ^ 5), donde n es el número total de solicitudes de monociclo y descargas de monociclo en la Estación Central, y q es el número de preguntas que te hace Adam. Las siguientes líneas de n describen las operaciones en la estación central. Cada línea contiene una descripción de la operación:

  • + t k cuando k monociclos se dejan en la estación en el momento t;
  • - t k cuando k personas solicitan monociclos en el momento t;

Para cada una de las operaciones descritas 1 \leq t \leq 10 ^ 9 y 1 \leq k \leq 10 ^ 4. La última línea de la entrada contiene q enteros diferentes b_i (0 \leq b_i \leq 10 ^ 9) el número de monociclos al comienzo del día i.

Las operaciones se dan en el orden de tiempo estrictamente creciente.

Salida

La salida constará de q líneas. La línea i-ésima mostrará el tiempo total de espera para el caso de b_i monociclos al comienzo del día. Si el tiempo total de espera es infinito, entonces la línea correspondiente mostrará la palabra "INFINITY".

Puntuación

En un 40% de los casos de prueba se tiene que 1 \leq n, q \leq 10, 1 \leq t, k \leq 50 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

There are no comments at the moment.