長さ $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)$ と更新する。

入力

1 行目には整数 $N$ が含まれる。これは数列の長さである。($1 \le N \le 500{,}000$)

2 行目には $N$ 個の整数 $A_1, A_2, \ldots, A_N$ が含まれる。($-10^9 \le A_i \le 10^9$)

3 行目には整数 $M$ が含まれる。これはクエリの個数である。($1 \le M \le 500{,}000$)

続く $M$ 行には、それぞれ 1 つのクエリが含まれる。($1 \le L \le R \le N$、$-2{,}000 \le X \le 2{,}000$、$-10^9 \le Y \le 10^9$) タイプ $4$, $5$, $6$ のクエリはそれぞれ少なくとも 1 回出現する。

出力

タイプ $4$, $5$, $6$ の各クエリについて、その答えを 1 行ずつ出力せよ。

入出力例

入力例 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