题目描述

Mayor Adam East wants to improve the public transport network of Harshel city by introducing the network of stations with unicycles. Any person who owns a special card can come to a station and request a unicycle to ride or drop one.

The procedure of requesting a unicycle is simple. The person enters a queue. If there is a unicycle available, then the first person from the queue takes it immediately. Otherwise, people in the queue wait until someone drops a unicycle at the station.

Let the wait time be the time that person spends between the request (entrance to the queue) and obtaining a unicycle. If the person does not receive a unicycle at all, then the wait time is infinity. The total wait time is the sum of wait times for each person.

Adam already knows the schedule of all the people for every day. He knows at what times people request and drop unicycles at the Central Station that can hold any number of unicycles at the same time. The only thing he does not know is how many unicycles should be placed there at the start of each day. He asks you several questions to calculate the total wait time given the starting number of unicycles.

输入格式

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 you. The next $n$ lines describe operations at the Central Station. Each line contains one description of operation:

$`+ t$ k` when $k$ unicycles are dropped at time $t$ ;

$`- t$ k` when $k$ people request unicycles at time $t$ .

For each of the described operations $1 \le t \le 10^{9}$ and $1 \le k \le 10^{4}$ . The last line of the input contains $q$ different integers $b_{i} (0 \le b_{i} \le 10^{9}$ ) -- the number of unicycles at the start of the day.

The operations are given in the strongly increasing order of time.

输出格式

The output shall consist of $q$ lines. The i-th line shall display the total wait time for the case of $b_{i}$ unicycles at the start of the day. If the total wait time is infinite, then the corresponding line shall display the word INFINITY.

题目大意

[NEERC2016] Expect to Wait

题目描述

市长小A想要给H市添加独轮车车站，任何有“特殊的卡片”的人，都可以到车站请求骑车或停放。

申请独轮车很简单，申请骑车的人到车站排队，如果那个站有独轮车停放，那么就让处于队头位置的人先骑，否则，排队的人会等到有人把独轮车送到车站。

定义等待时间为从请求人开始排队到取到车所花的时间，如果一个人取不到独轮车，那么等待的时间是无限（infinity）的。总等待时间是每个人等待时间的总和。

小A已经知道人们每天在什么时候向车站请求和放下独轮车，车站可以同时容纳无限独轮车。他会告诉你每天车站里人们的用车计划，然后对你进行n次询问，每次提问会告诉你一天开始时车站里有的独轮车数，请你来计算每个问题所对应的总等待时间。

输入格式

第一行包含两个正整数 $n$ 和 $q (1 \le n , q \le 10^{5} ),$ $n$代表有n个用车计划, $q$代表小A会问你n个问题 接下来$n$行代表每个用车计划，每个计划包含一个操作说明：

$+tk$ 代表人们在$t$时间要求停放$k$辆车;

$- t k$ 代表人们在$t$时间要求取$k$辆车.

对于每个用车计划： $1 \le t \le 10^{9}$ and $1 \le k \le 10^{4}$ . 输入的最后一行包含 $q$ 个不同的整数 $b_{i} (0 \le b_{i} \le 10^{9}$ ) -- 一天开始时独轮车的数量。

操作的顺序是按时间复杂度从小到大的

输出格式

输出应包括$q$行。第i行应显示当天开始时$b_{i}$独轮车的总等待时间。如果总等待时间是无限的，则相应的行应显示单词INFINITY。

样例 #1

样例输入 #1

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

样例输出 #1

INFINITY
0
8
3

提示

时间限制: 2 s,空间限制: 512 MB.

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

INFINITY
0
8
3

提示

Time limit: 2 s, Memory limit: 512 MB.