题目描述

有n台计算机，第i台计算机的运算能力为$v_i$。

有一系列的任务被指派到各个计算机上，第i个任务在$a_i$时刻分配，指定计算机编号为$b_i$，耗时为$c_i$且算力消耗为$d_i$。

如果此任务成功分配，将立刻开始运行，期间持续占用$b_i$号计算机$d_i$的算力，持续$c_i$秒。

对于每次任务分配，如果计算机剩余的运算能力不足则输出−1，并取消这次分配，否则输出分配完这个任务后这台计算机的剩余运算能力。

输入格式

输入的第一行包含两个整数n,m，分别表示计算机数目和要分配的任务数。

第二行包含n个整数$v_1,v_2,⋅⋅⋅v_n$，分别表示每个计算机的运算能力。

接下来m行每行4个整数$a_i,b_i,c_i,d_i$，意义如上所述。数据保证$a_i$严格递增，即$a_i<a_{i+1}$。

输出格式

输出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

提示

数据范围

对于20%的评测用例，n,m≤200。
对于40%的评测用例，n,m≤2000。
对于所有评测用例，1≤n,m≤200000，1≤$a_i,c_i,d_i,v_i$≤${10}^9$，1≤$b_i$≤n。

样例解释

时刻1，第1个任务被分配到第1台计算机，耗时为5，这个任务时刻6会结束，占用计算机1的算力3。

时刻2，第2个任务需要的算力不足，所以分配失败了。

时刻3，第1个计算机仍然正在计算第1个任务，剩余算力不足3，所以失败。

时刻4，第1个计算机仍然正在计算第1个任务，但剩余算力足够，分配后剩余算力1。

时刻5，第1个计算机仍然正在计算第1,4个任务，剩余算力不足4，失败。

时刻6，第1个计算机仍然正在计算第4个任务，剩余算力足够，且恰好用完。