27322번 - 한별이의 퍼펙트 수열과 쿼리 교실

한별이의 수열과 쿼리 교실은 언제나 완벽한 강의로 유명하다. 하지만 사실 한별이는 바보기 때문에 수열과 쿼리 문제가 주어져도 스스로 프로그램을 작성할 수 없고 매번 여러분에게 대신 프로그램 작성을 맡긴다. 한별이를 대신해 아래 문제를 풀어주자!

길이가 $N$인 수열 $A_1, A_2, \cdots A_N$이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• $1$ $L$ $R$ $X$: 모든 $L \leq i \leq R$에 대해서 $A_i = \min{(A_i, X)}$ 를 적용한다.
• $2$ $L$ $R$ $X$: 모든 $L \leq i \leq R$에 대해서 $A_i = \max{(A_i, X)}$ 를 적용한다.
• $3$ $L$ $R$ $X$: 모든 $L \leq i \leq R$에 대해서 $A_i = A_i + X$를 적용한다.
• $4$ $L$ $R$: $\min{(A_L, A_{L+1}, \cdots, A_R)}$을 출력한다.
• $5$ $L$ $R$: $\max{(A_L, A_{L+1}, \cdots, A_R)}$을 출력한다.
• $6$ $L$ $R$: $A_L + A_{L+1} + \cdots + A_R$을 출력한다.

$X$의 범위가 일반적이지 않은 점에 유의한다.

첫 번째 줄에 수열의 크기 $N$이 주어진다. ($1 \leq N \leq 500\,000$)

두 번째 줄에 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($1 \leq A_i \leq 10^{9}$)

세 번째 줄에 쿼리의 개수 $M$이 주어진다. ($1 \leq M \leq 300\,000$)

다음 $M$개의 줄에 쿼리가 한 줄에 하나씩 주어진다. $X$는 정수이다. ($1 \leq L \leq R \leq N$, $1 \leq X \leq \mathbf{10}$)

4, 5, 6번 쿼리의 결과를 한 줄에 하나씩 출력한다.

이 문제의 지문은 한별이의 원래 설정과 다를 수 있다