CF1928F.Digital Patterns

Anya is engaged in needlework. Today she decided to knit a scarf from semi-transparent threads. Each thread is characterized by a single integer — the transparency coefficient.

The scarf is made according to the following scheme: horizontal threads with transparency coefficients $a_1, a_2, \ldots, a_n$ and vertical threads with transparency coefficients $b_1, b_2, \ldots, b_m$ are selected. Then they are interwoven as shown in the picture below, forming a piece of fabric of size $n \times m$, consisting of exactly $nm$ nodes:

Example of a piece of fabric for $n = m = 4$.

After the interweaving tightens and there are no gaps between the threads, each node formed by a horizontal thread with number $i$ and a vertical thread with number $j$ will turn into a cell, which we will denote as $(i, j)$. Cell $(i, j)$ will have a transparency coefficient of $a_i + b_j$.

The interestingness of the resulting scarf will be the number of its sub-squares$^{\dagger}$ in which there are no pairs of neighboring$^{\dagger \dagger}$ cells with the same transparency coefficients.

Anya has not yet decided which threads to use for the scarf, so you will also be given $q$ queries to increase/decrease the coefficients for the threads on some ranges. After each query of which you need to output the interestingness of the resulting scarf.

$^{\dagger}$A sub-square of a piece of fabric is defined as the set of all its cells $(i, j)$, such that $x_0 \le i \le x_0 + d$ and $y_0 \le j \le y_0 + d$ for some integers $x_0$, $y_0$, and $d$ ($1 \le x_0 \le n - d$, $1 \le y_0 \le m - d$, $d \ge 0$).

$^{\dagger \dagger}$. Cells $(i_1, j_1)$ and $(i_2, j_2)$ are neighboring if and only if $|i_1 - i_2| + |j_1 - j_2| = 1$.

阿尼亚正在从事刺绣。今天，她决定用半透明的纱线编织一条围巾。每根纱线由一个整数表征——即其透明度系数。

围巾的制作方案如下：选取若干水平方向的纱线，其透明度系数为 $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}$单元格具有相同透明度系数”的子正方形的个数。

阿尼亚尚未决定具体选用哪些纱线来编织围巾，因此你还将收到 $q$ 个查询，每个查询将对某一段范围内的纱线透明度系数进行增加或减少操作。每次查询执行后，你需要输出当前围巾的趣味性数值。

$^{\dagger}$ 布料的一个子正方形定义为：所有满足 $x_0 \le i \le x_0 + d$ 且 $y_0 \le j \le y_0 + d$ 的单元格 $(i, j)$ 构成的集合，其中 $x_0$、$y_0$ 和 $d$ 为整数，且满足 $1 \le x_0 \le n - d$、$1 \le y_0 \le m - d$、$d \ge 0$。

$^{\dagger \dagger}$ 单元格 $(i_1, j_1)$ 与 $(i_2, j_2)$ 相邻，当且仅当 $|i_1 - i_2| + |j_1 - j_2| = 1$。

The first line contains three integers $n$, $m$, and $q$ ($1 \le n, m \le 3 \cdot 10^5$, $0 \le q \le 3 \cdot 10^5$) — the number of horizontal threads, the number of vertical threads, and the number of change requests.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — the transparency coefficients for the horizontal threads, with the threads numbered from top to bottom.

The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($-10^9 \le b_i \le 10^9$) — the transparency coefficients for the vertical threads, with the threads numbered from left to right.

The next $q$ lines specify the change requests. Each request is described by a quadruple of integers $t$, $l$, $r$, and $x$ ($1 \le t \le 2$, $l \le r$, $-10^9 \le x \le 10^9$). Depending on the parameter $t$ in the request, the following actions are required:

• $t=1$. The transparency coefficients for the horizontal threads in the range $[l, r]$ are increased by $x$ (in other words, for all integers $l \le i \le r$, the value of $a_i$ is increased by $x$);
• $t=2$. The transparency coefficients for the vertical threads in the range $[l, r]$ are increased by $x$ (in other words, for all integers $l \le i \le r$, the value of $b_i$ is increased by $x$).

第一行包含三个整数 $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$ 的整数 $i$，将 $a_i$ 的值增加 $x$）；
• $t=2$：将区间 $[l, r]$ 内所有垂直线程的透明度系数增加 $x$（即对所有满足 $l \le i \le r$ 的整数 $i$，将 $b_i$ 的值增加 $x$）。

Output $(q+1)$ lines. In the $(i + 1)$-th line ($0 \le i \le q$), output a single integer — the interestingness of the scarf after applying the first $i$ requests.

输出 $(q+1)$ 行。在第 $(i + 1)$ 行（其中 $0 \le i \le q$）中，输出一个整数——即应用前 $i$ 个请求后围巾的“有趣度”。

In the first example, the transparency coefficients of the cells in the resulting plate are as follows:

2

3

3

4

2

3

3

4

3

4

4

5

4

5

5

6

Then there are the following sub-squares that do not contain two neighboring cells with the same transparency coefficient:

• Each of the $16$ cells separately;
• A sub-square with the upper left corner at cell $(3, 1)$ and the lower right corner at cell $(4, 2)$;
• A sub-square with the upper left corner at cell $(2, 3)$ and the lower right corner at cell $(3, 4)$;
• A sub-square with the upper left corner at cell $(2, 1)$ and the lower right corner at cell $(3, 2)$;
• A sub-square with the upper left corner at cell $(3, 3)$ and the lower right corner at cell $(4, 4)$.

In the second example, after the first query, the transparency coefficients of the horizontal threads are $[1, 2, 2]$. After the second query, the transparency coefficients of the vertical threads are $[2, -4, 2]$.

在第一个例子中，最终平板中各单元格的透明度系数如下：

2

3

3

4

2

3

3

4

3

4

4

5

4

5

5

6

满足条件（即不包含两个相邻单元格具有相同透明度系数）的子正方形有以下这些：

• 单独的 $16$ 个单元格各自构成一个子正方形；
• 左上角位于单元格 $(3, 1)$、右下角位于单元格 $(4, 2)$ 的子正方形；
• 左上角位于单元格 $(2, 3)$、右下角位于单元格 $(3, 4)$ 的子正方形；
• 左上角位于单元格 $(2, 1)$、右下角位于单元格 $(3, 2)$ 的子正方形；
• 左上角位于单元格 $(3, 3)$、右下角位于单元格 $(4, 4)$ 的子正方形。

在第二个例子中，第一次查询后，水平线的透明度系数为 $[1, 2, 2]$；第二次查询后，垂直线的透明度系数为 $[2, -4, 2]$。