Étant donné une séquence $A_1, A_2, \ldots, A_N$ de longueur $N$, et deux séquences $B$ et $C$ de longueur $N$, satisfaisant initialement $B_i = A_i$ et $C_i = A_i$. Écrivez un programme pour traiter les requêtes suivantes :

• 1 L R X : Pour tout $L \le i \le R$, poser $A_i = A_i + X$.
• 2 L R Y : Pour tout $L \le i \le R$, poser $A_i = \max(A_i, Y)$.
• 3 L R Y : Pour tout $L \le i \le R$, poser $A_i = \min(A_i, Y)$.
• 4 L R : Afficher $\min(A_L, A_{L+1}, \ldots, A_R)$.
• 5 L R : Afficher $\min(B_L, B_{L+1}, \ldots, B_R)$.
• 6 L R : Afficher $\max(C_L, C_{L+1}, \ldots, C_R)$.

Après chaque requête, pour tout $1 \le i \le N$, mettez à jour $B_i = \min(B_i, A_i)$ et $C_i = \max(C_i, A_i)$.

Entrée

La première ligne contient un entier $N$, la longueur de la séquence. ($1 \le N \le 500\,000$)

La deuxième ligne contient $N$ entiers $A_1, A_2, \ldots, A_N$. ($-10^9 \le A_i \le 10^9$)

La troisième ligne contient un entier $M$, le nombre de requêtes. ($1 \le M \le 500\,000$)

Les $M$ lignes suivantes contiennent chacune une requête. ($1 \le L \le R \le N$, $-2\,000 \le X \le 2\,000$, $-10^9 \le Y \le 10^9$) Les requêtes de types $4$, $5$ et $6$ apparaissent chacune au moins une fois.

Sortie

Pour chaque requête de types $4$, $5$ et $6$, affichez la réponse, chacune sur une ligne séparée.

Exemples

Entrée 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

Sortie 1

3
0
0