Problem Description

Country R has a very long history.

There are $n$ cities in Country R, and there are $C$ political parties in the country, labeled $1,2,\dots,C$. Since Country R is very long geographically, the positions of these $n$ cities can be approximated as $n$ points on a coordinate axis. At the very beginning of history, it is recorded that the $i$-th city belongs to party $c_i$, and there are $a_i$ troops stationed in the city.

In the history of Country R, the following three types of events often occur:

1. Party $y$ carried out a lobbying action, causing all cities from city $l$ to city $r$ that currently belong to party $x$ to change their affiliation to party $y$.

2. Party $x$ carried out a recruitment action, increasing the number of troops by $v$ in all cities from city $l$ to city $r$ that currently belong to party $x$.

3. A war broke out among all cities between city $l$ and city $r$. The scale of the war can be described as the sum of the numbers of troops in all cities in that range. Note that wars do not necessarily happen between different parties; civil wars may also occur within cities belonging to the same party. Since Country R’s medical system is advanced enough, wars do not reduce the number of troops.

Little N is a girl who likes history. Recently, she wants to organize the war history of Country R, especially the scale of each war. However, since the history of Country R is far too long, it is too hard for her to compute everything with pen and paper. So she came to you, hoping you can write a program to compute the scales of all wars in Country R’s history.

Input Format

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

The next line contains $n$ positive integers $a_1,a_2,\dots,a_n$, representing the initial number of troops in each city.

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

The next $q$ lines each contain $3$ to $5$ positive integers, describing an event:

The first integer $\mathit{op}$ indicates the type of the event. $\mathit{op}=1,2,3$ represent the lobbying, recruitment, and war events described in the Description.

For each lobbying event, the next $4$ integers are $l,r,x,y$, with meanings as in the Description.

For each recruitment event, the next $4$ integers are $l,r,x,v$, with meanings as in the Description.

For each war event, the next $2$ integers are $l,r$, with meanings as in the Description.

Output Format

For each war event, output one integer per line, indicating the scale of this war.

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

79
142
188

样例 2 见附件 military2.in
本组数据满足测试点 4 的限制。

样例 2 见附件 military2.ans

样例 3 见附件 military3.in
本组数据满足测试点 14 的限制。

样例 3 见附件 military3.ans

样例 4 见附件 military4.in
本组数据满足测试点 18 的限制。

样例 4 见附件 military4.ans

Hint

Sample 1 Explanation

Initially, the numbers of troops in the five cities are $1, 2, 4, 8, 16$, and their party affiliations are $1, 2, 3, 2, 3$.

The events occur in the following order:

• Party $2$ attempts to recruit in cities $2, 3, 4$. Cities $2$ and $4$, which belong to party $2$, each gain $32$ troops.
• A war breaks out among all cities between cities $1$ and $4$, with scale $1 + 34 + 4 + 40 = 79$.
• Party $1$ carries out a lobbying action in cities $1, 2, 3, 4, 5$, causing cities $3$ and $5$, which originally belong to party $3$, to change their affiliation to party $1$.
• Party $1$ attempts to recruit in cities $2, 3, 4, 5$. Cities $3$ and $5$, which belong to party $1$, each gain $64$ troops.
• A war breaks out among all cities between cities $2$ and $4$, with scale $34 + 68 + 40 = 142$.
• Party $3$ attempts to recruit in cities $1, 2, 3$, but party $3$ currently owns no cities, so the recruitment does not succeed.
• A war breaks out among all cities between cities $3$ and $5$, with scale $68 + 40 + 80 = 188$.

Therefore, your program should output $79, 142, 188$ in order.

Constraints

For all testdata, $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$.

The detailed constraints and special conditions are shown in the table below.

Translated by ChatGPT 5