Дан массив a  из n  целых чисел. Требуется выполнить q запросов такого вида (1  ≤ l ≤ r ≤ n, 0 ≤ 9 k, b, x ≤ 10 ): +l r x  — прибавить x  ко всем a  i на отрезке i ∈ [l, r] ​ ?l r k  b  — вывести max  l≤i≤r min(ai , k ⋅ i + b) ​ ​ Формат входных данных В первой строке заданы два числа n  , q  (1  ≤n≤2⋅ 105 , 1 ≤ q ≤ 5 ⋅ 105 ). Во второй строке задан массив a  (0  ≤ ai ≤ 109 ). ​ Следующие q  строк содержат запросы в заданном формате. Гарантируется, что

Дан массив a состоящий из n целых чисел. Требуется выполнить q запросов двух видов:
1. Прибавить число x ко всем элементам массива на заданном отрезке l-r.
2. Найти максимальное значение среди минимальных значений элементов массива, учитывая ограничение на каждый элемент (минимальное значение может быть либо ai, либо k*i+b, где k, b – заданные числа).

Алгоритм решения:
1. Считываем n, q и заполняем массив a.
2. Для каждого запроса:
– Считываем его тип.
– Если тип равен “+”:
– Считываем l, r и x.
– Обновляем элементы массива a на отрезке l-r, добавляя x к каждому элементу.
– Если тип равен “?”:
– Считываем l, r, k и b.
– Инициализируем переменную min_val значением бесконечность.
– Проходим по каждому элементу массива от l до r:
– Вычисляем минимальное значение для текущего элемента, используя формулу min(ai, k*i+b) и сохраняем его в переменную curr_min.
– Обновляем min_val, если curr_min меньше min_val.
– Выводим найденное максимальное значение min_val.

Таким образом, после выполнения всех запросов, мы получим ответы на все вопросы второго типа и можем их вывести.