#4843. [Neerc2016]Expect to Wait

题目描述

ls最近开了一家图书馆，大家听说是ls开的，纷纷过来借书，自然就会出现供不应求的情况， 并且借书的过程类

似一个队列，每次有人来借书就将它加至队尾，每次有人来还书就把书借给队头的若干个人，定义每个人的等待时

间为拿到书的时刻减去加至队列的时刻，如果一个人根本就拿不到书，则等待时间为inf，现在给出所有时刻借书

还书的情况，和若干个询问，每次询问当图书馆初始有x本书时所有人的等待时间之和是多少（如果存在一个人根

本拿不到书，则输出INFINITY）。

输入格式

第一行两个整数n,q（1<=n,q<=100000),表示有n个时刻有借书还书的情况，以及有q个询问。

接下来n行，每行表示一个操作，操作如下：

1."+ t k" 在t时刻有k本书被还回来。

2."- t k" 在t时刻有k个人来借书。

（1<=t<=1e9,1<=k<=10000）

输入顺序保证t递增。

接下来一行q个数，第i个数bi（1<=bi<=1e9）表示图书馆初始有bi本书，询问所有人的等待时间之和为多少。

输出格式

一共q行，每行一个数表示等待时间之和，如果存在一个人根本拿不到书，则输出INFINITY。

样例

样例输入

5 4  

- 1 1  

- 2 2  

+ 4 1  

- 6 1  

+ 7 2  

0 3 1 2

样例输出

INFINITY  

0  

8  

3

数据范围与提示