P8755 [Lanqiao Cup 2021 NOI Qualifier AB2] Load Balancing.

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.

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}

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

**[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