CF1609G.A Stroll Around the Matrix

William has two arrays of numbers $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_m$. The arrays satisfy the conditions of being convex. Formally an array $c$ of length $k$ is considered convex if $c_i - c_{i - 1} \lt c_{i + 1} - c_i$ for all $i$ from $2$ to $k - 1$ and $c_1 \lt c_2$.

Throughout William's life he observed $q$ changes of two types happening to the arrays:

1. Add the arithmetic progression $d, d \cdot 2, d \cdot 3, \dots, d \cdot k$ to the suffix of the array $a$ of length $k$. The array after the change looks like this: $[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]$.
2. The same operation, but for array $b$.

After each change a matrix $d$ is created from arrays $a$ and $b$, of size $n \times m$, where $d_{i, j}=a_i + b_j$. William wants to get from cell ($1, 1$) to cell ($n, m$) of this matrix. From cell ($x, y$) he can only move to cells ($x + 1, y$) and ($x, y + 1$). The length of a path is calculated as the sum of numbers in cells visited by William, including the first and the last cells.

After each change William wants you to help find out the minimal length of the path he could take.

威廉拥有两个数字数组 $a_1, a_2, \dots, a_n$ 和 $b_1, b_2, \dots, b_m$。这两个数组均满足凸性条件。形式化地，一个长度为 $k$ 的数组 $c$ 被称为凸数组，当且仅当对所有 $i$ 满足 $2 \le i \le k-1$，有 $c_i - c_{i - 1} < c_{i + 1} - c_i$，且 $c_1 < c_2$。

在威廉的一生中，他观察到共 $q$ 次对这两个数组的修改，每次修改属于以下两种类型之一：

1. 向数组 $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]$。
2. 对数组 $b$ 执行完全相同的上述操作。

每次修改后，由数组 $a$ 和 $b$ 构造一个大小为 $n \times m$ 的矩阵 $d$，其中元素定义为 $d_{i, j} = a_i + b_j$。威廉希望从该矩阵的单元格 $(1, 1)$ 出发，到达单元格 $(n, m)$。从单元格 $(x, y)$ 出发时，他只能移动至 $(x + 1, y)$ 或 $(x, y + 1)$。一条路径的长度定义为威廉所经过的所有单元格（包括起点和终点）中数值之和。

每次修改后，威廉希望你帮他求出他所能选择的路径的最小可能长度。

The first line contains three integers $n$, $m$ and $q$ ($2 \le n \le 100, 2 \le m \le 10^5$, $1 \le q \le 10^5$), the sizes of the arrays and the number of changes.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{12}$), the contents of array $a$.

The third line contains $m$ integers $b_1, b_2, \dots, b_m$ ($1 \le b_i \le 10^{12}$), the contents of array $b$.

Each of the next $q$ lines contains three integers $type$, $k$ and $d$ ($1 \le type \le 2$, if $type = 1$, then $1 \le k \le n$ otherwise $1 \le k \le m$, $1 \le d \le 10^3$).

第一行包含三个整数 $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$）。

After each change, output one integer, the minimum length of the path in the constructed matrix.

每次修改后，输出一个整数，即所构造矩阵中路径的最短长度。