William 有两个数字数组 $$$a_1, a_2, \dots, a_n$$$ 和 $$$b_1, b_2, \dots, b_m$$$。数组满足凸条件。形式上,如果 $$$c_i - c_{i - 1} < c_{i + 1} - c_i$$$ 对于从 $$$2$$$ 到 $$$k - 1$$$ 的所有 $$$i$$$ 且 $$$c_1 < c_2$$$,则长度为 $$$k$$$ 的数组 $$$c$$$ 被视为凸数组。
在 William 的一生中,他观察到数组发生了两种类型的 $$$q$$$ 变化:
1. 将等差数列 $$$d, d \cdot 2, d \cdot 3, \dots, d \cdot k$$$ 添加到长度为 $$$k$$$ 的数组 $$$a$$$ 的后缀。更改后的数组如下所示:$$$[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$$$ 创建一个矩阵 $$$d$$$,大小为 $$$n \times m$$$,其中 $$$d_{i, j}=a_i + b_j$$$。 William 想要从该矩阵的单元格 ($$$1, 1$$$) 到单元格 ($$$n, m$$$)。从单元格 ($$$x, y$$$) 他只能移动到单元格 ($$$x + 1, y$$$) 和 ($$$x, y + 1$$$)。路径的长度计算为 William 访问过的单元格中的数字之和,包括第一个和最后一个单元格。
在每次改变之后,威廉希望你帮助找出他可以采取的最小路径长度。
输入
第一行包含三个整数 $$$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$$$)。
输出
每次改变后,输出一个整数,即构造矩阵中路径的最小长度。
示例
输入 #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
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
输出 #2
3639 5122 5162 5617 7663 7806 7960