出题人太菜，暂无测试数据。

题目背景

在幻想乡，琪露诺是以 $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\frac{\sum_{i=L}^{n} a_i}{|[L, R]|}\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}$