All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Carlson has N jars of jam. They are numbered from 1 to N while ith jar contains Ai
units of jam. Carslon believes that ith jar should contain at least Bi units of jam. Unfourtunetly, it happens that Ai is less than Bi. To fix this issue Carlson adds jam by doing M operations. Each operation is defined by four numbers l, r, x and y. It means that Carlson adds x units of jam to the lth, x + y units of jam to the (l + 1)th jar, x + 2y units of jam to the (l + 2)th jar,..., x + (r - l)y units of jam to the rth jar. After it, Carlson would like to know for each jar i when it starts to contain at least Bi units of jam, i.e. the minimal number of adding operation that ith jar contained less than Bi units of jam before it, but then started to contain at least Bi units of jam after the operation was applied. Have a look at the examples for better understanding.
The first line of input contains single integer number N. Following line contains N numbers Ai — initial amount of jam in each jar. The next line contains integer number M — number of adding operations. Then M lines follow describing adding operations in chronological order. Every operation is defined by four numbers l, r, x and y.
You should output the answer for each jar separated by space. If it already contains enough jam you should output 0 as the answer, in case it doesn't even after all the operations output -1 instead.
1 ≤ N ≤ 105
1 ≤ M ≤ 105
0 ≤ Ai ≤ 2*109
0 ≤ Bi ≤ 2*109
0 ≤ x, y ≤ 105
0 ≤ l ≤ r ≤ N
Input: 5 5 4 4 2 1 7 7 4 7 7 3 1 2 2 0 2 5 1 1 3 4 2 2 Output: 1 2 0 3 -1
|Tags||Rubanenko, cook53, hard, sqrt-decomp|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.