在刚刚结束的水题嘉年华的压轴节目放水大赛中，wyywyy 如愿以偿的得到了最假女选手的奖项。但是作为主办人的 C_SUNSHINE 为了证明 wyywyy 确实在放水，决定出一道基础题考察 wyywyy 的姿势水平。

题目描述

给定一个长度为 $n$ 的序列，要求支持以下 $6$ 种操作：

• 给一个区间 $[l,r]$ 加上一个整数 $x$；
• 把一个区间 $[l,r]$ 内小于 $x$ 的数都变成 $x$；
• 把一个区间 $[l,r]$ 内大于 $x$ 的数都变成 $x$；
• 求区间 $[l,r]$ 的和；
• 求区间 $[l,r]$ 的最大值；
• 求区间 $[l,r]$ 的最小值；

输入格式

第一行一个整数 $n$ 表示序列长度。

第二行 $n$ 个整数 $a_i$ 表示初始序列。

第三行一个整数 $m$ 表示操作个数。

接下来 $m$ 行，每行三或四个整数，表示一个题目中所描述的操作。

输出格式

对于每个 $4,5,6$ 类型的操作输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

2
1 2
2
2 1 2 2
4 1 2

输出 #1

4

说明/提示

数据保证，$1\leq n,m\leq 5\times 10^5$，$|a_i|\leq 10^8$。

当进行 $1$ 操作时，$|x| \leq 1000$；

当进行 $2$ 操作时，$|x| \leq 10^8$。