测试数据来自 system/1049

题目背景

在幻想乡，琪露诺是以 \(baka\) 闻名的冰之妖精。

题目描述

现在，\(baka\) 老师给了你一个长度为 \(n\) 的数列，现在你要根据 \(baka\) 的指令进行以下行动:
1. 1 L R 表示输出 \([L,R]\) 区间内的最大值。
2. 2 L R 表示输出 \([L,R]\) 区间内的最小值。
3. 3 L R 表示对 \([L,R]\) 区间内的每一个元素加该区间的最大值减区间的最小值。
4. 4 L R 表示输出 \(\bar{x}\) (注: \(\bar{x} = \lfloor\sum_{i=L}^{n} a_i / n \rfloor\))。

输入输出格式

第一行两个正整数 \(n,m\)，分别表示数列的长度 \(n\) 和 指令的个数 \(m\)。

第二行包含 \(n\) 个用空格分隔的整数，其中第 \(i\) 个数字表示数列第 \(i\) 项的初始值。

接下来 \(m\) 行，每行包含 \(3\) 个整数，表示对应的操作。

样例

输入

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

输出

5
2
5
1

数据范围

对于 \(30\%\) 的数据: \(n \le 8,m \le 10\)。

对于 \(70\%\) 的数据: \(n \le 10^3,m \le 10^4\)

对于 \(100\%\) 的数据: \(1 \le n,m \le 10^5\)

保证任意时刻数列中所有元素的绝对值之和 \(\le 10^{18}\)