Problem Description

R Country has a long history.

R Country has $n$ cities and $C$ political parties, denoted as $1, 2, \dots, C$. Due to the elongated geography of R Country, the positions of these $n$ cities can be approximated as $n$ points on a coordinate axis. Initially, the $i$-th city belongs to party $c_i$ and has an army of size $a_i$.

Throughout its history, R Country has experienced three types of events:

1. Party $y$ conducts a persuasion campaign, causing all cities from city $l$ to city $r$ that belong to party $x$ to now belong to party $y$.

2. Party $x$ conducts a recruitment campaign, increasing the army size by $v$ in all cities from city $l$ to city $r$ that belong to party $x$.

3. A war breaks out among all cities from city $l$ to city $r$. The scale of this war is described as the sum of the army sizes in all cities between $l$ and $r$. Note that wars do not necessarily occur between different parties; internal conflicts within the same party can also happen. Due to R Country's advanced medical system, wars do not reduce the army sizes.

Xiao N, a girl who loves history, wants to organize the war history of R Country, especially the scale of each war. However, due to the long history of R Country, she finds it challenging to calculate manually. Therefore, she seeks your help to write a program that can count the scale of all historical wars.

Input Format

The first line of input contains three positive integers $n, q, C$, representing the number of cities, the number of events, and the number of political parties in R Country, respectively.

The next line contains $n$ positive integers $a_1, a_2, \dots, a_n$, indicating the initial army sizes in each city.

The following line contains $n$ positive integers $c_1, c_2, \dots, c_n$, representing the initial party affiliations of each city.

The next $q$ lines, each containing 3 to 5 positive integers, describe an event:

The first positive integer $\mathit{op}$ indicates the type of event. $\mathit{op} = 1, 2, 3$ correspond to the persuasion, recruitment, and war events described in the problem.

For each persuasion event, there are four positive integers $l, r, x, y$, as described in the problem.

For each recruitment event, there are four positive integers $l, r, x, v$, as described in the problem.

For each war event, there are two positive integers $l, r$, as described in the problem.

Output Format

For each war event, output a single line containing an integer representing the scale of that war.

Sample Input and Output

Input Sample #1

5 7 3
1 2 4 8 16
1 2 3 2 3
2 2 4 2 32
3 1 4
1 1 5 3 1
2 2 5 1 64
3 2 4
2 1 3 3 128
3 3 5

Output Sample #1

79
142
188

Input Sample #2

Sample 2 can be found in the attached file military2.in
This set of data meets the restrictions of test point 4.

Output Sample #2

Sample 2 can be found in the attached file military2.ans

Input Sample #3

Sample 3 can be found in the attached file military3.in
This set of data meets the restrictions of test point 14.

Output Sample #3

Sample 3 can be found in the attached file military3.ans

Input Sample #4

Sample 4 can be found in the attached file military4.in
This set of data meets the restrictions of test point 18.

Output Sample #4

Sample 4 can be found in the attached file military4.ans

Notes/Hints

[Sample 1 Explanation]

Initially, the army sizes in the five cities are $1, 2, 4, 8, 16$, and their party affiliations are $1, 2, 3, 2, 3$.

The events that occur are:
- Party $2$ attempts to recruit in cities $2, 3, 4$, successfully increasing the army sizes in cities $2, 4$ by $32$ each.
- A war breaks out between cities $1$ and $4$, with a scale of $1 + 34 + 4 + 40 = 79$.
- Party $1$ conducts a persuasion campaign in cities $1, 2, 3, 4, 5$, causing cities $3, 5$ originally belonging to party $3$ to now belong to party $1$.
- Party $1$ attempts to recruit in cities $2, 3, 4, 5$, successfully increasing the army sizes in cities $3, 5$ by $64$ each.
- A war breaks out between cities $2$ and $4$, with a scale of $34 + 68 + 40 = 142$.
- Party $3$ attempts to recruit in cities $1, 2, 3$, but since party $3$ no longer owns any cities, no recruitment occurs.
- A war breaks out between cities $3$ and $5$, with a scale of $68 + 40 + 80 = 188$.

Thus, your program should output $79, 142, 188$ in sequence.

[Data Size and Constraints]

For all data, $1 \leq n, q \leq 2.5 \times 10^5$, $1 \leq a_i, v \leq 10^8$, $1 \leq c_i, x, y \leq C$.

Specific data sizes and constraints are detailed in the table below.

见题面 Input 部分

见题面 Output 部分