Expect to Wait

Interview

Time limit2sMemory limit512 MB

Summary

Given a time-ordered schedule of unicycle drops and grouped requests, compute the total wait time of all requesters for each of several starting unicycle counts, or report infinity if anyone is left waiting.

Level: Medium7 of 10
Topics: Prefix sum, Binary search, Array, Implementation
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples6

Example 1

Input

Expected output

INFINITY
0
8
3

Example 2
Input
```
1 2
- 1 1
1 0
```
Expected output
```
0
INFINITY
```

Example 3

Input

3 3
+ 1 5
+ 500 3
+ 1000000000 10000
0 1 1000000000

Expected output

0
0
0

Example 4

Input

4 5
- 1 3
- 5 2
- 9 4
- 100 1
0 3 9 10 1000000000

Expected output

INFINITY
INFINITY
INFINITY
0
0

Example 5

Input

2 4
- 1 10000
+ 1000000000 10000
0 1 5000 10000

Expected output

9999999990000
9998999990001
4999999995000
0

Example 6

Input

8 6
- 1 2
+ 3 1
- 4 3
+ 10 2
+ 11 5
- 12 4
- 20 1
+ 30 3
0 1 2 3 4 5

Expected output