Anya 从事针线活。今天她决定用半透明线编织一条围巾。每个线程都由一个整数来表征——透明度系数。
围巾按照以下方案制作:选择透明度系数为$$$a_1、a_2、\ldots、a_n$$$的水平线和透明度系数为$$$b_1、b_2、\ldots、b_m$$$的垂直线。然后它们如下图所示交织在一起,形成一块大小为 $$$n \times m$$$ 的织物,恰好由 $$$nm$$$ 节点组成:
$$$n = m = 4$$$ 的一块织物示例。
当交织紧密并且线之间没有间隙时,编号为$$$i$$$的水平线和编号为$$$j$$$的垂直线形成的每个节点将变成一个单元,我们将其表示为$$$(i,j)$$$。单元格 $$$(i, j)$$$ 的透明度系数为 $$$a_i + b_j$$$。
生成的围巾的有趣之处在于其子方块$$$^{\dagger}$$$的数量,其中不存在具有相同透明度系数的相邻$$$^{\dagger \dagger}$$$单元对。
Anya 尚未决定将哪些线用于围巾,因此您还将收到 $$$q$$$ 查询来增加/减少某些范围内线的系数。在每个查询之后,您需要输出结果围巾的兴趣度。
$$$^{\dagger}$$$一块织物的子正方形被定义为其所有单元$$$(i, j)$$$的集合,使得对于某些整数$$$x_0 \le i \le x_0 + d$$$和$$$y_0 \le j \le y_0 + d$$$, $$$y_0$$$ 和 $$$d$$$($$$1 \le x_0 \le n - d$$$、$$$1 \le y_0 \le m - d$$$、$$$d \ge 0$$$)。
$$$^{\匕首\匕首}$$$。单元格 $$$(i_1, j_1)$$$ 和 $$$(i_2, j_2)$$$ 是相邻的当且仅当 $$$|i_1 - i_2| + |j_1 - j_2| = 1$$$。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$, $$$0 \le q \le 3 \cdot 10^5$$$) — 水平线程数、垂直线程数和更改请求数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) - 水平线程的透明度系数,线程从上到下编号。
第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$-10^9 \le b_i \le 10^9$$$) - 垂直线程的透明度系数,线程从左到右编号。
接下来的 $$$q$$$ 行指定更改请求。每个请求由四元组整数 $$$t$$$、$$$l$$$、$$$r$$$ 和 $$$x$$$ 描述($$$1 \le t \le 2$$$、$$$l \le r$$$、$$$-10^9 \le x \le 10^9$$$)。根据请求中的参数$$$t$$$,需要执行以下操作:
- $$$t=1$$$。 $$$[l, r]$$$ 范围内水平线的透明度系数增加 $$$x$$$(换句话说,对于所有整数 $$$l \le i \le r$$$,$$$a_i$$$ 的值增加 $$$x$$$);
- $$$t=2$$$。 $$$[l, r]$$$ 范围内的垂直线的透明度系数增加 $$$x$$$(换句话说,对于所有整数 $$$l \le i \le r$$$,$$$b_i$$$ 的值增加 $$$x$$$)。
输出
输出 $$$(q+1)$$$ 行。在第 $$$(i + 1)$$$ 行 ($$$0 \le i \le q$$$) 中,输出一个整数 — 应用第一个 $$$i$$$ 请求后围巾的兴趣度。
示例
输入 #1
4 4 0 1 1 2 3 1 2 2 3
输出 #1
20
输入 #2
3 3 2 1 1 1 2 2 8 1 2 3 1 2 2 3 -6
输出 #2
9 10 11
输入 #3
3 2 2 -1000000000 0 1000000000 -1000000000 1000000000 1 1 1 1000000000 2 2 2 -1000000000
输出 #3
8 7 7
注意
在第一个示例中,所得板中单元的透明度系数如下:
2334233434454556
那么有以下子方格不包含具有相同透明度系数的两个相邻单元格:
- 每个 $$$16$$$ 单元格分别;
- 左上角位于单元格 $$$(3, 1)$$$ 且右下角位于单元格 $$$(4, 2)$$$ 的子正方形;
- 左上角位于单元格 $$$(2, 3)$$$ 且右下角位于单元格 $$$(3, 4)$$$ 的子正方形;
- 左上角位于单元格 $$$(2, 1)$$$ 且右下角位于单元格 $$$(3, 2)$$$ 的子正方形;
- 左上角位于单元格 $$$(3, 3)$$$ 且右下角位于单元格 $$$(4, 4)$$$ 的子正方形。
在第二个示例中,在第一次查询之后,水平线程的透明度系数为$$$[1, 2, 2]$$$。第二次查询后,垂直线的透明度系数为$$$[2, -4, 2]$$$。