题目背景

线段树全家桶。

题目描述

你现在有 $5$ 个序列 $a,b,c,d,e$，长度均为 $n$，初始时所有元素均为 $0$。

你需要依次处理 $q$ 个操作，每个操作可能是 修改（对某个序列的某个区间进行统一变更）或 查询（询问某个序列的某个区间上的某种统计信息）。

特殊约束：

• 序列 $b$ 中的元素 始终只可能是 $\{-1,0,1\}$。所有对 $b$ 的修改均保证不会使其超出该值域。
• 序列 $c$ 中的元素按 32 位无符号整数 处理（即 $0 \le c_i < 2^{32}$）。

输入格式

第一行两个整数 $n,q$。

接下来 $q$ 行，每行描述一个操作。每行首先输入一个整数 $op$，代表操作类型，随后根据 $op$ 的不同输入若干参数。

所有区间操作均为闭区间 $[l,r]$，保证 $1 \le l \le r \le n$。

所有操作中的 $x$ 均在对应序列的值域范围内，且对于序列 $b$ 的加法操作，保证结果仍属于 $\{-1,0,1\}$。

操作列表

当 $op=1$ 时，输入三个正整数 $l,r,x$，表示将序列 $a$ 的区间 $[l,r]$ 增加 $x$，即 $\forall i\in[l,r],\ a_i \gets a_i + x$；

当 $op=2$ 时，输入三个正整数 $l,r,x$，表示将序列 $a$ 的区间 $[l,r]$ 乘上 $x$，即 $\forall i\in[l,r],\ a_i \gets a_i \times x$；

当 $op=3$ 时，输入三个正整数 $l,r,x$，表示让序列 $a$ 的区间 $[l,r]$ 等于 $x$，即 $\forall i\in[l,r],\ a_i \gets x$；

当 $op=4$ 时，输入三个正整数 $l,r,x$，表示将序列 $a$ 的区间 $[l,r]$ 每个元素取最大值（Chmax），即 $\forall i\in[l,r],\ a_i \gets \max(a_i, x)$；

当 $op=5$ 时，输入三个正整数 $l,r,x$，表示将序列 $a$ 的区间 $[l,r]$ 每个元素取最小值（Chmin），即 $\forall i\in[l,r],\ a_i \gets \min(a_i, x)$；

当 $op=6$ 时，输入两个正整数 $l,r$，表示将序列 $a$ 的区间 $[l,r]$ 每个元素向下取整开方，即 $\forall i\in[l,r],\ a_i \gets \lfloor \sqrt{a_i} \rfloor$；

当 $op=7$ 时，输入三个正整数 $l,r,x$（其中 $x\in\{-1,0,1\}$），表示将序列 $b$ 的区间 $[l,r]$ 赋值为 $x$，即 $\forall i\in[l,r],\ b_i \gets x$；

当 $op=8$ 时，输入两个正整数 $l,r$，表示将序列 $b$ 的区间 $[l,r]$ 取反（乘以 $-1$），即 $\forall i\in[l,r],\ b_i \gets -b_i$；

当 $op=9$ 时，输入两个正整数 $l,r$，表示将序列 $b$ 的区间 $[l,r]$ 全部乘以 $0$，即 $\forall i\in[l,r],\ b_i \gets 0$；

当 $op=10$ 时，输入三个正整数 $l,r,x$（其中 $x\in\{-1,0,1\}$），表示将序列 $b$ 的区间 $[l,r]$ 增加 $x$，即 $\forall i\in[l,r],\ b_i \gets b_i + x$；保证操作后所有 $b_i$ 仍属于 $\{-1,0,1\}$；

当 $op=11$ 时，输入三个正整数 $l,r,x$，表示将序列 $c$ 的区间 $[l,r]$ 按位与上 $x$，即 $\forall i\in[l,r],\ c_i \gets c_i \ \&\ x$；

当 $op=12$ 时，输入三个正整数 $l,r,x$，表示将序列 $c$ 的区间 $[l,r]$ 按位或上 $x$，即 $\forall i\in[l,r],\ c_i \gets c_i \ \mid \ x$；

当 $op=13$ 时，输入两个正整数 $l,r$，表示将序列 $c$ 的区间 $[l,r]$ 按位取反（32 位无符号），即 $\forall i\in[l,r],\ c_i \gets \sim c_i$；

当 $op=14$ 时，输入三个正整数 $l,r,x$，表示将序列 $c$ 的区间 $[l,r]$ 赋值为 $x$，即 $\forall i\in[l,r],\ c_i \gets x$；

当 $op=15$ 时，输入三个正整数 $l,r,x$，表示将序列 $d$ 的区间 $[l,r]$ 增加 $x$，即 $\forall i\in[l,r],\ d_i \gets d_i + x$；

当 $op=16$ 时，输入三个正整数 $l,r,x$，表示将序列 $d$ 的区间 $[l,r]$ 乘上 $x$，即 $\forall i\in[l,r],\ d_i \gets d_i \times x$；

当 $op=17$ 时，输入三个正整数 $l,r,x$，表示将序列 $d$ 的区间 $[l,r]$ 赋值为 $x$，即 $\forall i\in[l,r],\ d_i \gets x$；

当 $op=18$ 时，输入三个正整数 $l,r,x$，表示将序列 $e$ 的区间 $[l,r]$ 增加 $x$，即 $\forall i\in[l,r],\ e_i \gets e_i + x$；

当 $op=19$ 时，输入三个正整数 $l,r,x$，表示将序列 $e$ 的区间 $[l,r]$ 乘上 $x$，即 $\forall i\in[l,r],\ e_i \gets e_i \times x$；

当 $op=20$ 时，输入两个正整数 $l,r$，查询序列 $a$ 的区间和 $\sum_{i=l}^r a_i$；

当 $op=21$ 时，输入两个正整数 $l,r$，查询序列 $a$ 的区间平方和 $\sum_{i=l}^r a_i^2$；

当 $op=22$ 时，输入两个正整数 $l,r$，查询序列 $a$ 的区间最大公约数 $\gcd(a_l, a_{l+1}, \dots, a_r)$；

当 $op=23$ 时，输入两个正整数 $l,r$，查询序列 $a$ 的区间最大值 $\max_{i=l}^r a_i$；

当 $op=24$ 时，输入两个正整数 $l,r$，查询序列 $a$ 的区间最小值 $\min_{i=l}^r a_i$；

当 $op=25$ 时，输入两个正整数 $l,r$，查询序列 $b$ 的区间 最大子段和；

当 $op=26$ 时，输入两个正整数 $l,r$，查询序列 $b$ 的区间 最小子段和；

当 $op=27$ 时，输入两个正整数 $l,r$，查询序列 $b$ 的区间 最长连续相等元素段长度，即 $\max\{\text{连续 }-1\text{ 的长度}, \text{连续 }0\text{ 的长度}, \text{连续 }1\text{ 的长度}\}$；

当 $op=28$ 时，输入两个正整数 $l,r$，查询序列 $c$ 的区间异或和 $c_l \oplus c_{l+1} \oplus \dots \oplus c_r$；

当 $op=29$ 时，输入两个正整数 $l,r$，查询序列 $c$ 的区间按位与 $c_l \ \&\ c_{l+1} \ \&\ \dots \ \&\ c_r$；

当 $op=30$ 时，输入两个正整数 $l,r$，查询序列 $c$ 的区间按位或 $c_l \ \mid \ c_{l+1} \ \mid \ \dots \ \mid \ c_r$；

当 $op=31$ 时，输入两个正整数 $l,r$，查询序列 $d$ 的区间和 $\sum_{i=l}^r d_i$；

当 $op=32$ 时，输入两个正整数 $l,r$，查询序列 $e$ 的区间平方和 $\sum_{i=l}^r e_i^2$；

输出格式

对于每个查询操作（$op \in [20,34]$），输出一行一个整数，为对应的答案。

5 32
1 1 5 5
2 1 5 2
3 1 5 0
4 1 5 3
5 1 5 4
6 1 5
7 1 5 1
8 1 5
9 1 5
10 1 5 1
11 1 5 0
12 1 5 1
13 1 5
14 1 5 5
15 1 5 3
16 1 5 2
17 1 5 10
18 1 5 5
19 1 5 2
20 1 5
21 1 5
22 1 5
23 1 5
24 1 5
25 1 5
26 1 5
27 1 5
28 1 5
29 1 5
30 1 5
31 1 5
32 1 5

5
5
1
1
1
5
0
5
5
5
5
50
500

样例解释

经过前 $19$ 个修改操作后，各序列的值如下（长度为 $5$）：

序列	值
$a$	全为 $1$
$b$
$c$	全为 $5$
$d$	全为 $10$
$e$

因此各查询的答案来源如下：

• $op=20$：序列 $a$ 的区间和 $= 1+1+1+1+1 = 5$；
• $op=21$：序列 $a$ 的区间平方和 $= 1^2+1^2+1^2+1^2+1^2 = 5$；
• $op=22$：序列 $a$ 的区间最大公约数 $= \gcd(1,1,1,1,1) = 1$；
• $op=23$：序列 $a$ 的区间最大值 $= 1$；
• $op=24$：序列 $a$ 的区间最小值 $= 1$；
• $op=25$：序列 $b$ 的最大子段和 $= 5$（全为 $1$，取整个区间）；
• $op=26$：序列 $b$ 的最小子段和 $= 0$（取空子段）；
• $op=27$：序列 $b$ 的最长连续相等元素段长度 $= 5$（全为 $1$）；
• $op=28$：序列 $c$ 的区间异或和 $= 5 \oplus 5 \oplus 5 \oplus 5 \oplus 5 = 5$（奇数个相同数异或为其本身）；
• $op=29$：序列 $c$ 的区间按位与 $= 5 \ \& \ 5 \ \& \ 5 \ \& \ 5 \ \& \ 5 = 5$；
• $op=30$：序列 $c$ 的区间按位或 $= 5 \ \mid \ 5 \ \mid \ 5 \ \mid \ 5 \ \mid \ 5 = 5$；
• $op=31$：序列 $d$ 的区间和 $= 10 \times 5 = 50$；
• $op=32$：序列 $e$ 的区间平方和 $= 10^2 \times 5 = 500$；

数据范围与约定

• $1 \le n,q \le 10^5$
• 所有 $x$ 的绝对值 $\le 10^9$（对于序列 $c$，$0 \le x < 2^{32}$）
• 保证所有操作合法（序列 $b$ 的加法和赋值不会使其值超出 $\{-1,0,1\}$）