Problem Description

There are $n$ computers. The computing capacity of the $i$-th computer is $v_{i}$.

A series of tasks are assigned to computers. The $i$-th task is assigned at time $a_{i}$, to the computer with index $b_{i}$, with duration $c_{i}$, and computing power consumption $d_{i}$. If the task is assigned successfully, it starts running immediately. During its execution, it continuously occupies $d_{i}$ computing capacity of computer $b_{i}$ for $c_{i}$ seconds.

For each task assignment, if the remaining computing capacity of the computer is not enough, output $-1$ and cancel this assignment. Otherwise, output the remaining computing capacity of this computer after assigning this task.

Input Format

The first line contains two integers $n, m$, representing the number of computers and the number of tasks to be assigned.

The second line contains $n$ integers $v_{1}, v_{2}, \cdots v_{n}$, representing the computing capacity of each computer.

The next $m$ lines each contain $4$ integers $a_{i}, b_{i}, c_{i}, d_{i}$, with the meanings described above. The testdata guarantees that $a_{i}$ is strictly increasing, i.e., $a_{i}<a_{i+1}$.

Output Format

Output $m$ lines. Each line contains one number, corresponding to the result of each task assignment.

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

Hint

[Sample Explanation]

At time $1$, task $1$ is assigned to computer $1$, with duration $5$. This task will end at time $6$, and it occupies computing capacity $3$ of computer $1$.

At time $2$, task $2$ does not have enough required computing capacity, so the assignment fails.

At time $3$, computer $1$ is still running task $1$, and its remaining computing capacity is less than $3$, so it fails.

At time $4$, computer $1$ is still running task $1$, but its remaining computing capacity is enough. After assignment, the remaining computing capacity is $1$.

At time $5$, computer $1$ is still running tasks $1$ and $4$, and its remaining computing capacity is less than $4$, so it fails.

At time $6$, computer $1$ is still running task $4$. Its remaining computing capacity is enough, and it is used up exactly.

[Constraints and Conventions for Test Cases]

For $20\%$ of the test cases, $n, m \leq 200$.

For $40\%$ of the test cases, $n, m \leq 2000$.

For all test cases, $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$.

Lanqiao Cup 2021, Round 2, Provincial Contest, Group A Problem H (Group B Problem I).

Translated by ChatGPT 5