Дан массив \(a\) длины \(n\), состоящий из целых чисел. Далее к нему последовательно \(q\) раз применяют следующую операцию:
- Выбирают индексы \(l\) и \(r\) (\(1 \le l \le r \le n\)) и целое число \(x\);
- Ко всем элементам массива \(a\) на отрезке \([l, r]\) прибавляют \(x\). Более формально, присваивают \(a_i := a_i + x\) для всех \(l \le i \le r\).
Пусть \(b_j\) — массив \(a\), полученный после применения первых \(j\) операций (\(0 \le j \le q\)). Обратите внимание, что \(b_0\) — это массив \(a\) до применения всех операций.
Вам нужно найти лексикографически минимальный\(^{\dagger}\) массив среди всех \(b_j\).
\(^{\dagger}\)Массив \(x\) лексикографически меньше чем массив \(y\), если есть индекс \(i\) такой, что \(x_i < y_i\), и \(x_j = y_j\) для всех \(j < i\). Иными словами, для первого такого индекса \(i\), где массивы различны, \(x_i < y_i\).
Выходные данные
Для каждого набора входных данных выведите лексикографически минимальный массив среди всех \(b_j\).
Примечание
В первом наборе входных данных:
- \(b_0 = [1,2,3,4]\);
- \(b_1 = [1,2,3,4]\);
- \(b_2 = [-99,-98,-97,4]\).
Таким образом, лексикографически минимальным является массив \(b_2\).
Во втором наборе входных данных лексикографически минимальным является массив \(b_0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
1 2 3 4
2
1 4 0
1 3 -100
5
2 1 2 5 4
3
2 4 3
2 5 -2
1 3 1
|
-99 -98 -97 4
2 1 2 5 4
|