Masala D

Xotira 512 MB Vaqt 3000 ms

ReLU

Uzunligi $n$ ga teng ikkita $A$ va $B$ massivi bor. Massivlar hozir 0 lar bilan to'ldirilgan.

Sizga jami $Q$ ta 3 xil turgagi so'rov beriladi, siz ularni bajarishingiz lozim.

$1 \ l \ r \ c$ : barcha $l \leq i \leq r$ uchun oldin $a[i] \leftarrow a[i] + c$ qiling, so'ngra $b[i] \leftarrow max(b[i], a[i])$ qiling.
$2 \ l \ r \ d$ : barcha $l \leq i \leq r$ uchun oldin $a[i] \leftarrow max(a[i], d)$ qiling, so'ngra $b[i] \leftarrow max(b[i], a[i])$ qiling.
$3 \ l \ r$ : ekranga yangi qatordan $max(b[l], b[l+1], \dots b[r])$ ni chiqaring.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son, $n$ va $q(1 \leq n,q \leq 5 * 10^5)$ kiritiladi.

Keyingi $q$ ta qatorning har birida so'rovlar masala shartida ko'rsatilgan formatda kiritiladi. Bunda $1 \leq l \leq r \leq n$ , $c \leq |10^6|$ va $d \leq |10^{12}|$ .

Chiquvchi ma'lumotlar:

Har bir qatordan alohida 3-turdagi so'rovlarning natijasini chiqaring.

Misollar

#	input.txt	output.txt
1	13 10 1 1 2 2 3 3 4 2 1 11 1 3 7 12 1 1 6 -100 2 2 6 100 3 3 13 3 6 10 2 2 7 144 3 4 8	0 1 100 100 144