Background

Problem Description

Qinqin gives you two sequences $a$ and $b$ of length $n$. You need to support a total of $m$ operations of three types:

1. 1 l r x: Set all numbers in the interval $[l,r]$ of sequence $a$ to $x$.
2. 2 l r y: Set all numbers in the interval $[l,r]$ of sequence $b$ to $y$.
3. 3 l r: Compute $\sum_{i=l}^r \sum_{j=1}^{b_i} a_j$. The answer is taken modulo $2^{32}$.

Input Format

All inputs are integers.

Line $1$ contains two numbers $n,m$.
Line $2$ contains $n$ numbers representing sequence $a$.
Line $3$ contains $n$ numbers representing sequence $b$.
The next $m$ lines each contain one operation. The format is the same as in the problem description.

Output Format

For each operation of type $3$, output one integer per line as the answer.

4 5
5 5 4 5
3 4 4 1
2 3 3 2
2 2 3 4
3 1 4
1 3 3 2
3 2 4

57
39

5 5
1 7 5 2 5
2 1 5 3 2
1 5 5 3
1 3 5 2
3 1 4
2 1 4 2
3 1 3

33
24

10 10
27 29 12 16 16 6 20 22 17 1
2 6 1 10 4 1 3 10 9 6
2 3 5 6
3 2 10
2 5 10 9
3 5 9
1 1 5 24
1 6 10 12
3 2 3
1 4 6 14
1 4 8 14
3 5 10

956
825
264
924

Hint

This problem uses bundled judging.

Note: The original time limit was 5 s. Since it was rather strict on constant factors, it was changed by the admins to 7 s.

For $100\%$ of the data, $1\le n\le 5\times 10^5$, $1\le m\le 3\times 10^5$, $1\le a_i,x\le 10^9$, $1\le b_i,y\le n$.

Translated by ChatGPT 5