题目描述

有 $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}, \cdots 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

提示

【样例说明】

时刻 $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$ 个任务，剩余算力足够，且恰好用完。

【评测用例规模与约定】

对于 $20 \%$ 的评测用例, $n, m \leq 200$。

对于 $40 \%$ 的评测用例, $n, m \leq 2000$。

对于所有评测用例, $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$。

蓝桥杯 2021 第二轮省赛 A 组 H 题（B 组 I 题）。