Sequence and Queries 27

You are given a sequence $A_1, A_2, \ldots, A_N$ of length $N$. There are also two sequences $B$ and $C$ of length $N$, where $B_i = A_i$ and $C_i = A_i$ initially. Write a program that processes the following queries.

• 1 L R X: For every $L \le i \le R$, add $X$ to $A_i$.
• 2 L R Y: For every $L \le i \le R$, set $A_i = \max(A_i, Y)$.
• 3 L R Y: For every $L \le i \le R$, set $A_i = \min(A_i, Y)$.
• 4 L R: Print $\min(A_L, A_{L+1}, \ldots, A_R)$.
• 5 L R: Print $\min(B_L, B_{L+1}, \ldots, B_R)$.
• 6 L R: Print $\max(C_L, C_{L+1}, \ldots, C_R)$.

After each query, for every $1 \le i \le N$, $B_i$ becomes $\min(B_i, A_i)$ and $C_i$ becomes $\max(C_i, A_i)$.

The first line contains $N$, the length of the sequence. ($1 \le N \le 500{,}000$)

The second line contains $A_1, A_2, \ldots, A_N$. ($-10^9 \le A_i \le 10^9$)

The third line contains $M$, the number of queries. ($1 \le M \le 500{,}000$)

Each of the next $M$ lines contains one query. ($1 \le L \le R \le N$, $-2{,}000 \le X \le 2{,}000$, $-10^9 \le Y \le 10^9$) Queries 4, 5, and 6 appear at least once.

Print the results of queries 4, 5, and 6, one per line.