给定一个长度为 $N$ 的序列 $A_1, A_2, \ldots, A_N$，以及两个长度为 $N$ 的序列 $B$ 和 $C$，初始时满足 $B_i = A_i$，$C_i = A_i$。请编写一个程序执行以下查询：

• 1 L R X：对于所有 $L \le i \le R$，执行 $A_i = A_i + X$。
• 2 L R Y：对于所有 $L \le i \le R$，执行 $A_i = \max(A_i, Y)$。
• 3 L R Y：对于所有 $L \le i \le R$，执行 $A_i = \min(A_i, Y)$。
• 4 L R：输出 $\min(A_L, A_{L+1}, \ldots, A_R)$。
• 5 L R：输出 $\min(B_L, B_{L+1}, \ldots, B_R)$。
• 6 L R：输出 $\max(C_L, C_{L+1}, \ldots, C_R)$。

在每个查询执行之后，对于所有 $1 \le i \le N$，更新 $B_i = \min(B_i, A_i)$，$C_i = \max(C_i, A_i)$。

输入格式

第一行包含一个整数 $N$，表示序列的长度。（$1 \le N \le 500{,}000$）

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$。（$-10^9 \le A_i \le 10^9$）

第三行包含一个整数 $M$，表示查询的个数。（$1 \le M \le 500{,}000$）

接下来 $M$ 行，每行包含一个查询。（$1 \le L \le R \le N$，$-2{,}000 \le X \le 2{,}000$，$-10^9 \le Y \le 10^9$）其中第 $4$、$5$、$6$ 类查询至少出现一次。

输出格式

对于每个第 $4$、$5$、$6$ 类查询，输出其答案，每个答案占一行。

样例

输入格式 1

3
1 2 3
6
5 3 3
1 2 3 -2
3 1 3 0
5 3 3
2 2 3 4
5 1 3

输出格式 1

3
0
0