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

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

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

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