У Василия есть два массива чисел \(a_1, a_2, \dots, a_n\) и \(b_1, b_2, \dots, b_m\). Для этих массивов выполняется свойство выпуклости. Формально массив \(c\) длины \(k\) называется выпуклым, если \(c_i - c_{i - 1} < c_{i + 1} - c_i\) для всех \(i\) от \(2\) до \(k - 1\) и \(c_1 < c_2\).
За жизнь Василия с этими массивами происходило \(q\) изменений одного из двух типов:
- Прибавить к суффиксу массива \(a\) длины \(k\) арифметическую прогрессию \(d, d \cdot 2, d \cdot 3, \dots, d \cdot k\). Массив после изменения выглядит следующим образом: \([a_1, a_2, \dots, a_{n - k}, a_{n - k + 1} + d, a_{n - k + 2} + d \cdot 2, \dots, a_n + d \cdot k]\).
- Такая же операция, но для массива \(b\).
После каждого изменения из массивов \(a\) и \(b\) создается матрица \(d\) размера \(n \times m\), где \(d_{i, j}=a_i + b_j\). Василий хочет дойти от клетки (\(1, 1\)) до клетки (\(n, m\)) этой матрицы. От клетки (\(x, y\)) он может перейти только в клетки (\(x + 1, y\)) и (\(x, y + 1\)). Длиной пути считается сумма всех чисел в клетках, которые посетил Василий, включая стартовую и конечную клетку.
После каждого изменения Василий хочет, чтобы вы помогли ему узнать минимальную длину пути, которую он мог бы пройти.