Expect to Wait

Mayor Adam East wants to improve the public transport network of Harshel city by building stations that lend out unicycles. Anyone who owns a special card can come to a station and request a unicycle or drop one off.

Requesting a unicycle is simple. The person joins a queue. If a unicycle is available, the person at the front of the queue takes one immediately. If no unicycle is available, the people in the queue wait until someone drops a unicycle at the station.

The wait time of a person is the time between the request, that is the moment of joining the queue, and the moment of obtaining a unicycle. A person who never obtains a unicycle has an infinite wait time. The total wait time is the sum of the wait times of all people.

Adam already knows the entire schedule for one day. He knows at which times people request unicycles at the Central Station and at which times they drop them off. The Central Station holds any number of unicycles at the same time. The only thing Adam does not know is how many unicycles to place there at the start of the day, so he gives you several starting counts and asks for the total wait time of each.

Nothing happens after the last operation. If anyone is still in the queue once the last operation has been processed, that person never obtains a unicycle and the total wait time is infinite.

The first line contains $n$ and $q$ ($1 \le n, q \le 10^5$), where $n$ is the total number of unicycle requests and unicycle drops at the Central Station and $q$ is the number of questions Adam asks.

Each of the next $n$ lines describes one operation at the Central Station.

• + t k: $k$ unicycles are dropped at time $t$.
• - t k: $k$ people request unicycles at time $t$.

Every operation satisfies $1 \le t \le 10^9$ and $1 \le k \le 10^4$. The operations are given in increasing order of time, so no two operations share a time.

The last line contains $q$ different integers $b_1, b_2, \dots, b_q$ ($0 \le b_i \le 10^9$), the number of unicycles placed at the Central Station at the start of the day.

Print $q$ lines. The $i$-th line contains the total wait time for a day that starts with $b_i$ unicycles. If that total wait time is infinite, print INFINITY on the line instead.