수열의 구간 갱신과 탐색

길이가 $N$인 정수 수열 $A_0, A_1, \cdots, A_{N-1}$이 주어진다. 다음 $Q$개의 쿼리를 순서대로 처리해 보자. 각 쿼리에서 $l$, $r$은 구간의 양 끝 인덱스이며, 구간 $[l, r]$은 양 끝을 포함한다.

• $1\ l\ r\ x$: $l \le i \le r$인 모든 $A_i$에 $x$를 더한다.
• $2\ l\ r\ x$: $l \le i \le r$인 모든 $A_i$를 $\min(A_i, x)$로 바꾼다.
• $3\ l\ r\ x$: $l \le i \le r$인 모든 $A_i$를 $\max(A_i, x)$로 바꾼다.
• $4\ l\ r$: $A_l + A_{l+1} + \cdots + A_r$을 구한다.
• $5\ l\ r$: $A_l, A_{l+1}, \cdots, A_r$의 최솟값을 구한다.
• $6\ l\ r$: $A_l, A_{l+1}, \cdots, A_r$의 최댓값을 구한다.
• $7\ l\ r\ x$: $l \le i \le r$이고 $A_i \ge x$인 가장 작은 인덱스 $i$를 구한다.

$7$번 쿼리에서 조건을 만족하는 인덱스가 없다면 답은 $-1$이다.

첫 번째 줄에 두 정수 $N$, $Q$가 공백으로 구분되어 주어진다. $(1 \le N, Q \le 200\,000)$

두 번째 줄에 수열의 원소 $A_0, A_1, \cdots, A_{N-1}$이 공백으로 구분되어 주어진다. $(-10^{12} \le A_i \le 10^{12})$

세 번째 줄부터 $Q$개의 줄에 걸쳐 본문에 설명된 형식의 쿼리가 주어진다. 각 쿼리에는 구간의 양 끝을 나타내는 두 정수 $l$, $r$이 주어지며, 한 줄의 값은 공백으로 구분되어 주어진다. $(0 \le l \le r < N)$

$1$번, $2$번, $3$번 쿼리에는 정수 $x$가 주어진다. $(-10^{12} \le x \le 10^{12})$

$7$번 쿼리에는 정수 $x$가 주어진다. $(-10^{18} \le x \le 10^{18})$

$4$번, $5$번, $6$번, $7$번 쿼리의 답을 쿼리가 주어진 순서대로 한 줄에 하나씩 출력한다.