Задача №114217. Винни-Пух и бочки меда
У Винни-Пуха есть \(n\) бочек меда. В \(i\)-й бочке налито \(a_i\) меда, а объем бочки равен \(b_i\) (\(1 \le i \le n\)). Винни-Пух хочет полностью заполнить все свои бочки. Для этого он последовательно делает \(q\) шагов. На \(j\)-м шаге он будет наливать мед в бочки с номерами от \(l_j\) до \(r_j\) (\(1 \le j \le q\)). В бочку с номером \(l_j\) Винни-Пух нальет \(c_j\) меда, в следующую бочку он нальет \(c_j + d_j\) меда, в следующую \(c_j + 2 \cdot d_j\) меда и так далее до бочки с номером \(r_j\).
Для каждой бочки требуется вывести номер шага, после которого она окажется полностью заполненной. Если после выполнения всех шагов бочка так и не заполнится, то для нее необходимо вывести число 0.
В первой строке даны два целых числа \(n\) и \(q\) (\(1 \le n, \ q \le 2 \cdot 10^5\)).
Во второй строке через пробел даны \(n\) целых чисел \(0 \le a_1, \ldots, a_n \le 10^5\).
В третьей строке через пробел даны \(n\) целых чисел \(1 \le b_1, \ldots, b_n \le 10^9\).
В следующих \(q\) строках даны по четыре целых числа \(l_j\), \(r_j\), \(c_j\), \(d_j\) (\(1 \le l_j \le r_j \le n\), \(0 \le c_j, \ d_j \le 10^5\), \(1 \le j \le q\)).
Гарантируется, что \(a_i < b_i\) для всех \(1 \le i \le n\).
В единственной строке выведите \(n\) целых чисел -- ответ для каждой из бочек.
5 3 0 0 0 0 2 7 7 7 7 7 1 5 1 1 2 5 1 1 1 3 4 0
0 3 3 2 1