题目背景

题目描述

琴琴给了你两个长为 $n$ 的序列 $a,b$，请你支持三种操作共 $m$ 次：

1. 1 l r x，将 $a$ 序列的区间 $[l,r]$ 中的所有数修改为 $x$。
2. 2 l r y，将 $b$ 序列的区间 $[l,r]$ 中的所有数修改为 $y$。
3. 3 l r，求 $\sum_{i=l}^r \sum_{j=1}^{b_i} a_j$。答案对 $2^{32}$ 取模。

输入格式

输入均为整数。

第 $1$ 行 $2$ 个数 $n,m$。
第 $2$ 行 $n$ 个数表示序列 $a$。
第 $3$ 行 $n$ 个数表示序列 $b$。
接下来 $m$ 行，每行一个操作，格式见题目描述。

输出格式

对于每个操作 $3$，一行一个整数表示答案。

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

提示

本题采用捆绑测试。

注：原时间限制为 5s，较为卡常所以被管理改为 7s。

对于 $100\%$ 的数据，$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$。