题目描述

坤坤从小就喜欢打篮球，因此他有一个去 CBA 打篮球的梦想。但他力气很大，训练的时候经常将篮球拍坏，所以他自己开了一家篮球工厂。

篮球工厂有 $n$ 条生产线，第 $i$ 条生产线每小时的生产能力为 $v_i$ 个篮球。现在有一系列生产订单需要分配到各条生产线上，第 $i$ 个订单在 $a_i$ 时刻到达，指定使用 $b_i$ 号生产线，需要连续生产 $c_i$ 小时，且每小时会占用该生产线 $d_i$ 的生产能力。如果订单成功分配，将立即开始生产，在这 $c_i$ 小时内会持续占用 $b_i$ 号生产线 $d_i$ 的生产能力。

如果生产线当前剩余生产能力不足，则输出 -1，并取消这个订单；否则输出分配后该生产线的剩余生产能力。

输入格式

• 第一行两个整数 $n$, $m$，分别表示生产线数量和订单数量。
• 第二行包含 $n$ 个整数 $v$，表示每条生产线的每小时生产能力。
• 接下来 $m$ 行，每行 4 个整数 $a_i$, $b_i$, $c_i$, $d_i$，描述一个订单。保证订单到达时间严格递增（$a_i < a_{i+1}$）。

数据范围：

• $1 \leq n, m \leq 2 \times 10^5$
• $1 \leq a_i, c_i, d_i, v_i \leq 10^9$
• $1 \leq b_i \leq 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

样例解释

1. 第一个订单在时刻 1 到达，分配到生产线 1，占用 3 单位生产能力，剩余 $5 - 3 = 2$，输出 2。
2. 第二个订单在时刻 2 到达，分配到生产线 2，需要占用 6 单位生产能力，但生产线 2 的总能力只有 5，无法分配，输出 -1。
3. 第三个订单在时刻 3 到达，分配到生产线 1，需要占用 3 单位生产能力，但生产线 1 当前剩余能力为 2，无法分配，输出 -1。
4. 第四个订单在时刻 4 到达，分配到生产线 1，占用 1 单位生产能力，剩余 $2 - 1 = 1$，输出 1。
5. 第五个订单在时刻 5 到达，分配到生产线 1，需要占用 3 单位生产能力，但生产线 1 当前剩余能力为 1，无法分配，输出 -1。
6. 第六个订单在时刻 6 到达，分配到生产线 1，需要占用 4 单位生产能力，但生产线 1 当前剩余能力为 1，无法分配，输出 -1。