[Neerc2016]Expect to Wait

时间限制:10s      空间限制:128MB

题目描述

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

提示

没有写明提示


题目来源

没有写明来源

Menuappsclose