The history of the country R is very long. Country R has $n$ cities and $C$ political parties, labeled $1, 2, \dots, C$. Since the territory of country R is very long, the positions of these $n$ cities can be approximated as $n$ points on a coordinate axis. At the beginning of history, the $i$-th city was recorded as belonging to party $c_i$, and the city had $a_i$ troops.

In the history of country R, the following three types of events often occurred: 1. Party $y$ conducted a lobbying campaign, causing all cities belonging to party $x$ in the range from city $l$ to city $r$ to now belong to party $y$. 2. Party $x$ conducted a recruitment drive, causing the number of troops in all cities belonging to party $x$ in the range from city $l$ to city $r$ to increase by $v$. 3. A war broke out among all cities between city $l$ and city $r$. The scale of this war is defined as the sum of the number of troops in all cities between these two locations. Note that wars do not necessarily occur between different parties; civil wars may also occur within cities belonging to the same party. Since the medical system of country R is sufficiently advanced, wars do not cause a reduction in the number of troops.

Little N is a girl who loves history. Recently, she wanted to organize the war history of country R, especially the scale of each war. However, because the history of country R is so long, she found it overwhelming to perform the calculations with pen and paper. Therefore, she found you and hopes you can write a program to calculate the scale of all wars in the history of country R.

Input

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, respectively.

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 party to which each city initially belongs.

The next $q$ lines each contain 3 to 5 positive integers, representing an event: The first positive integer $op$ represents the type of event. $op = 1, 2, 3$ represent the lobbying, recruitment, and war events described in the problem statement, respectively.

For each lobbying event, there are 4 subsequent positive integers $l, r, x, y$, with meanings as described in the problem statement.

For each recruitment event, there are 4 subsequent positive integers $l, r, x, v$, with meanings as described in the problem statement.

For each war event, there are 2 subsequent positive integers $l, r$, with meanings as described in the problem statement.

Output

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

Examples

Input 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 1

79
142
188

Note

Initially, the number of troops in the five cities are $1, 2, 4, 8, 16$, and the parties they belong to 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 increase by $32$ troops. A war breaks out among all cities between city $1$ and $4$. The scale is $1 + 34 + 4 + 40 = 79$. Party 1 conducts a lobbying campaign in cities $1, 2, 3, 4, 5$, causing cities $3$ and $5$, which originally belonged to party 3, to now belong to party 1. Party 1 attempts to recruit in cities $2, 3, 4, 5$. Cities $3$ and $5$, which belong to party 1, each increase by $64$ troops. A war breaks out among all cities between city $2$ and $4$. The scale is $34 + 68 + 40 = 142$. Party 3 attempts to recruit in cities $1, 2, 3$, but party 3 does not currently own any cities, so the recruitment is unsuccessful. * A war breaks out among all cities between city $3$ and $5$. The scale is $68 + 40 + 80 = 188$. Therefore, your program should output $79, 142, 188$ in order.

Constraints

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