90025 - 负载均衡

有n台计算机,第i台计算机的运算能力为vi。有一系列的任务被指派到各个计算机上,第i个任务在ai时刻分配,指定计算机编号为bi,耗时为ci且算力消耗为di。

 
如果此任务成功分配,将立刻开始运行,期间持续占用bi号计算机di的算力,持续ci秒。对于每次任务分配,如果计算机剩余的运算能力不足则输出-1,并取消这次分配,否则输出分配完这个任务后这台计算机的剩余运算能力。 

输入

输入的第一行包含两个整数n,m,分别表示计算机数目和要分配的任务数。 
第二行包含n个整数v1,v2,v3,...,vn,分别表示每个计算机的运算能力。 
接下来m行每行 4 个整数ai,bi,ci,di,意义如上所述。数据保证ai严格递增。

对于 20% 的评测用例,n,m<=200。 
对于 40% 的评测用例,n,m<=2000。 
对于所有评测用例,1<=n,m<=200000 , 1<=ai,ci,di,vi<=10^9 , 1<=bi<=n。

输出

输出m行,每行包含一个数,对应每次任务分配的结果。

样例

输入

2 6
5 5
1 1 5 3
2 2 2 6
3 1 2 3
4 1 6 1
5 1 3 3
6 1 3 4

输出

2
-1
-1
1
-1
0
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题