Task Scheduling on Computers

Given (n) computers where the (i)th computer has computing power (v_i). A series of tasks is assigned. The (i)th task is scheduled at time (a_i) to computer (b_i) (1-indexed), runs for (c_i) seconds, and consumes (d_i) computing power. Once a task is assigned, it starts immediately and reserves (d_i) computing power on that computer for (c_i) seconds. If, at the time a task is to be assigned, the remaining computing power of the computer is less than (d_i), output (-1) and cancel the assignment; otherwise, allocate the task, reduce the available computing power by (d_i), and output the remaining computing power of that computer after allocation. When a task completes (i.e. at time (a_i+c_i)), its allocated computing power is restored.

inputFormat

The first line contains two integers (n) and (m), representing the number of computers and the number of tasks, respectively. The second line contains (n) integers (v_1, v_2, \dots, v_n) representing the initial computing power of each computer. Each of the next (m) lines contains four integers (a_i, b_i, c_i, d_i) indicating the assignment time, computer index, duration, and computing power consumption for each task.

outputFormat

For each task, output one line containing the remaining computing power of the specified computer after the task assignment if the task can be successfully assigned, or (-1) if the computer does not have enough available computing power.

sample

2 3
10 5
1 1 5 3
2 1 5 8
6 1 3 5

7
-1
5