У Василия есть два массива чисел $$$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$$$). Длиной пути считается сумма всех чисел в клетках, которые посетил Василий, включая стартовую и конечную клетку.
После каждого изменения Василий хочет, чтобы вы помогли ему узнать минимальную длину пути, которую он мог бы пройти.
Первая строка содержит три числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$2 \le n \le 100, 2 \le m \le 10^5$$$, $$$1 \le q \le 10^5$$$) — размеры массивов и количество изменений.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$) — описание массива $$$a$$$.
Третья строка содержит $$$m$$$ целых чисел $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le 10^{12}$$$) — описание массива $$$b$$$.
Следующие $$$q$$$ строк содержат три целых числа $$$type$$$, $$$k$$$ и $$$d$$$ ($$$1 \le type \le 2$$$, если $$$type = 1$$$, то $$$1 \le k \le n$$$ иначе $$$1 \le k \le m$$$, $$$1 \le d \le 10^3$$$).
После каждого изменения выведите одно целое число — минимальную длину пути в построенной матрице.
5 3 4 1 2 4 7 11 5 7 10 1 3 2 2 2 5 1 5 4 2 1 7
98 128 219 229
5 6 7 4 9 22 118 226 7 94 238 395 565 738 2 1 95 1 4 54 1 2 5 1 2 87 2 6 62 2 1 143 1 1 77
3639 5122 5162 5617 7663 7806 7960
