有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行，每行包含一个数，对应每次任务分配的结果。