bobo 有一个数组 $a[1], a[2], \dots, a[n]$。

他随后提出了 $q$ 个问题，类型如下：

• $1 \ l_i \ r_i \ c_i$ - 对于所有 $l_i \le k \le r_i$，将 $a[k]$ 更新为 $a[k] + c_i$；
• $2 \ l_i \ r_i \ c_i$ - 对于所有 $l_i \le k \le r_i$，将 $a[k]$ 更新为 $\min\{a[k], c_i\}$；
• $3 \ l_i \ r_i \ c_i$ - 对于所有 $l_i \le k \le r_i$，将 $a[k]$ 更新为 $\max\{a[k], c_i\}$；
• $4 \ l_i \ r_i$ - 查询 $\min\{a[k] : l_i \le k \le r_i\}$ 和 $\max\{a[k] : l_i \le k \le r_i\}$。

输入格式

第一行包含两个整数 $n, q$ ($1 \le n, q \le 200000$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组的初始值 ($|a_i| \le 10^9$)。

接下来的 $q$ 行，每行包含一个整数 $t_i$，表示第 $i$ 个问题的类型。如果 $t_i = 1, 2, 3$，则后面跟着 3 个整数 $l_i, r_i, c_i$。如果 $t_i = 4$，则后面跟着 2 个整数 $l_i, r_i$。($1 \le t_i \le 4, 1 \le l_i \le r_i \le n$)

• 若 $t_i = 1$，则 $|c_i| \le 2000$；
• 若 $t_i = 2, 3$，则 $|c_i| \le 10^9$。

输出格式

对于每个类型为 4 的问题，输出两个整数，分别表示最小值和最大值。

样例

输入 1

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

输出 1

1 3
2 2