数组（array）

【题目描述】 有一个长度为 $n(n \leq 100)$ 的数组 $a$ ，和长度为 $m\left(m \leq 10^{5}\right)$ 的数组 $b$ 。这两个数组都满足凸性条件。

什么是凸性条件？如果一个长度为 $l$ 的数组 $c$ 满足凸性条件，则

1． $c_{2}-c_{1}>0$ 2． $c_{i}-c_{i-1}<c_{i+1}-c_{i}(2<i<k-1)$

有 $q$ 次修改，每次修改给定正整数 $t y p e, k, d$ 。小 R 会构造一个长度为 $k$ 等差数列$(d, 2 d, 3 d, \ldots, k d)$ 。

如果 $t y p e=1$ ，则将数组 $a$ 的后缀加上这个等差数列，即 $a_{n-k+1}+=d, a_{n-k+2}+=$ $2 d, \ldots a_{n}+=k d$ ，数据保证此时 $1 \leq k \leq n$ 。

如果 $t y p e=2$ ，则将数组 $a$ 的后缀加上这个等差数列，即 $b_{m-k+1}+=d, b_{m-k+2}+$ $=2 d, \ldots b_{m}+=k d$ ，数据保证此时 $1 \leq k \leq m$ 。

每次操作结束之后，小 R 会构造一个 $n \times m$ 的矩阵 $Z_{i, j}=a_{i}+b_{j}$ 。你需要从这个矩阵的左上角 $(1,1)$ 出发，每次向下或者向右走一格，走到右下角 $(n, m)$ 。路径长度被定义为经过所有格子的数值和。你需要求出每次操作结束后的最短路径长度。

【输入格式】 从文件 array．in 中读入数据。 第一行三个正整数 $n, m, q\left(2 \leq n \leq 100,2 \leq m \leq 10^{5}, 1 \leq q \leq 10^{5}\right)$ ，分别表示数组$a$ 的长度，数组 $b$ 的长度和操作次数。

第二行 $n$ 个整数 $a_{i}\left(1 \leq a_{i} \leq 10^{12}\right)$ 第三行 $m$ 个整数 $b_{i}\left(1 \leq b_{i} \leq 10^{12}\right)$ 接下来 $q$ 行，每行三个整数type，$k, d(1 \leq d \leq 1000$ 。若type $=1,1 \leq k \leq n$ ；若type＝ $2,1 \leq k \leq m$ ），表示一次操作。

【输出格式】 输出到文件 array．out 中。 输出 $q$ 行，分别表示每次修改后的答案。

【样例1输入】

5 3 4
1 2 4 7 11
5 7 10
1 3 2
2 2 5
1 5 4
2 1 7

【样例1输出】

98
128
219
229

【样例 2】 见下发文件的 array／array2．in 与 array／array2．ans。

【样例 3】 见下发文件的 array／array3．in 与array／array3．ans。

【样例 4】 见下发文件的 array／array4．in 与array／array4．ans。

【数据范围与提示】 对于 100％的数据， $2 \leq n \leq 100,2 \leq m \leq 10^{5}, 1 \leq q \leq 10^{5}, 1 \leq a_{i}, b_{i} \leq 10^{12}$

特殊性质 A ：每次修改保证 type $=1, k=n$ 特殊性质 B：每次修改保证 type＝ 1

附加文件