311062: CF1928F. Digital Patterns

F. Digital Patternstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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$.

Input

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$).

Output

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.

ExamplesInput

4 4 0
1 1 2 3
1 2 2 3

Output

20

Input

3 3 2
1 1 1
2 2 8
1 2 3 1
2 2 3 -6

Output

9
10
11

Input

3 2 2
-1000000000 0 1000000000
-1000000000 1000000000
1 1 1 1000000000
2 2 2 -1000000000

Output

8
7
7

Note

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]$.

题目大意：
安雅正在进行刺绣。今天，她决定用半透明线织一条围巾。每根线由一个整数表示透明度系数。

围巾的制作方式如下：选择透明度系数为a1、a2、…、an的水平线和透明度系数为b1、b2、…、bm的垂直线。然后按照下图所示交织，形成一个大小为n×m的布料，由nm个节点组成：

每个节点由编号为i的水平线和编号为j的垂直线组成，记为(i, j)。单元格(i, j)的透明度系数为ai + bj。

结果围巾的有趣性是由其子正方形中没有相邻单元格具有相同透明度系数的数量决定的。

安雅还没有决定用哪些线做围巾，所以你也会得到q个查询来增加/减少一些线范围内的系数。在每次查询后，你需要输出结果围巾的有趣性。

输入数据格式：
第一行包含三个整数n、m和q（1≤n, m≤3×10^5，0≤q≤3×10^5）——水平线的数量、垂直线的数量和更改请求的数量。

第二行包含n个整数a1、a2、…、an（-10^9≤ai≤10^9）——水平线的透明度系数，从上到下编号。

第三行包含m个整数b1、b2、…、bm（-10^9≤bi≤10^9）——垂直线的透明度系数，从左到右编号。

接下来q行指定更改请求。每个请求由四个整数t、l、r和x（1≤t≤2，l≤r，-10^9≤x≤10^9）描述。根据请求中的参数t，执行以下操作：

t=1。将范围[l, r]内水平线的透明度系数增加x（换句话说，对于所有整数l≤i≤r，ai的值增加x）；
t=2。将范围[l, r]内垂直线的透明度系数增加x（换句话说，对于所有整数l≤i≤r，bi的值增加x）。

输出数据格式：
输出(q+1)行。在第(i+1)行（0≤i≤q）中，输出一个整数——应用前i个请求后围巾的有趣性。题目大意： 安雅正在进行刺绣。今天，她决定用半透明线织一条围巾。每根线由一个整数表示透明度系数。 围巾的制作方式如下：选择透明度系数为a1、a2、…、an的水平线和透明度系数为b1、b2、…、bm的垂直线。然后按照下图所示交织，形成一个大小为n×m的布料，由nm个节点组成： 每个节点由编号为i的水平线和编号为j的垂直线组成，记为(i, j)。单元格(i, j)的透明度系数为ai + bj。 结果围巾的有趣性是由其子正方形中没有相邻单元格具有相同透明度系数的数量决定的。 安雅还没有决定用哪些线做围巾，所以你也会得到q个查询来增加/减少一些线范围内的系数。在每次查询后，你需要输出结果围巾的有趣性。 输入数据格式： 第一行包含三个整数n、m和q（1≤n, m≤3×10^5，0≤q≤3×10^5）——水平线的数量、垂直线的数量和更改请求的数量。 第二行包含n个整数a1、a2、…、an（-10^9≤ai≤10^9）——水平线的透明度系数，从上到下编号。 第三行包含m个整数b1、b2、…、bm（-10^9≤bi≤10^9）——垂直线的透明度系数，从左到右编号。 接下来q行指定更改请求。每个请求由四个整数t、l、r和x（1≤t≤2，l≤r，-10^9≤x≤10^9）描述。根据请求中的参数t，执行以下操作： t=1。将范围[l, r]内水平线的透明度系数增加x（换句话说，对于所有整数l≤i≤r，ai的值增加x）； t=2。将范围[l, r]内垂直线的透明度系数增加x（换句话说，对于所有整数l≤i≤r，bi的值增加x）。 输出数据格式： 输出(q+1)行。在第(i+1)行（0≤i≤q）中，输出一个整数——应用前i个请求后围巾的有趣性。