Облыстық команда іріктеуінен кейін White ұзақ уақыт бойы көңілсіздікке салынды. Ол өз нәтижелерінен ешқандай үміт таба алмады. Соған қарамастан, White NOI алдындағы соңғы дайындығын жалғастырды. Күнделікті жаттығулармен қатар, ол OI кезінде үйренуге мүмкіндігі болмаған тақырыптарды да зерттей бастады — қоштасар алдында ешқандай өкініш қалмасын деп үміттенді.

Шашыраңқы ойларын серпіп тастап, White кенеттен алдындағы есепке — қарапайым әрі зеріктіретін деректер құрылымы есебіне назар аударды —

White-та $n$ бүтін саннан тұратын $a_1, a_2, \dots, a_n$ тізбегі бар. Ол осы тізбекке $q$ амал орындайды. Әрбір амал келесі үш түрдің біріне жатады:

• 1 l r v — $[l, r]$ кесіндісіндегі әрбір элементке $v$ санын қосу.
• 2 l r v — $[l, r]$ кесіндісіндегі әрбір элементке $v$ мәнін меншіктеу.
• 3 l r — $\sum_{i=l}^r (\min_{j=l}^i a_j) \times (\max_{j=l}^i a_j)$ өрнегінің $2^{64}$ модулі бойынша мәнін сұрау.

Сіздің міндетіңіз — барлық амалдарды модельдеп, барлық сұраныстардың нәтижелерін шығару.

Кіріс деректер

Кірістің бірінші жолында элементтер саны мен амалдар санын білдіретін екі бүтін сан $n, q$ ($1 \le n, q \le 2 \times 10^5$) берілген.

Екінші жолда бастапқы элементтерді білдіретін $n$ бүтін сан $a_1, a_2, \cdots, a_n$ ($0 \le a_i \le 10^9$) берілген.

Келесі $q$ жолдың әрқайсысы үш пішімнің бірінде бір амалды сипаттайды:

• 1 l r v ($1 \le l \le r \le n, -10^9 \le v \le 10^9$), қосу амалын білдіреді.
• 2 l r v ($1 \le l \le r \le n, 1 \le v \le 10^9$), меншіктеу амалын білдіреді.
• 3 l r ($1 \le l \le r \le n$), сұраныс амалын білдіреді.

Бүкіл процесс барысында әрбір $1 \le i \le n$ үшін $0 \le a_i \le 10^9$ болатынына кепілдік беріледі.

Шығыс деректер

Әрбір сұраныс амалы үшін жеке жолға бір бүтін санды — сұраныс нәтижесінің $2^{64}$ модулі бойынша мәнін шығарыңыз.

Мысалдар

Кіріс

5 8
2 3 5 4 1
3 1 5
3 2 4
2 4 5 2
3 1 5
3 2 4
1 1 2 5
3 1 5
3 2 4

Шығыс

35
39
40
34
177
120

Кіріс

10 20
1 2 3 4 5 6 7 8 9 10
1 1 10 1
3 1 5
3 2 9
3 8 10
1 2 5 10
3 1 5
3 2 9
3 8 10
1 5 9 -5
3 1 5
3 2 9
3 8 10
1 2 5 -10
3 1 5
3 2 9
3 8 10
1 5 9 5
3 1 5
3 2 9
3 8 10

Шығыс

40
156
270
120
1202
270
118
831
80
33
61
80
40
156
270

Ескертпе

Бірінші тестте:

Бастапқы тізбек: 2 3 5 4 1. Үшінші амалдан кейін ол 2 3 2 2 1 болады, ал алтыншы амалдан кейін 7 8 7 7 6 болады.

Бірінші сұраныс үшін жауап: $\sum_{i=1}^5 (\min_{j=1}^i a_j) \times (\max_{j=1}^i a_j) = 2 \times 2 + 2 \times 3 + 2 \times 5 + 2 \times 5 + 1 \times 5 = 35$.

Екінші сұраныс үшін жауап: $\sum_{i=2}^4 (\min_{j=2}^i a_j) \times (\max_{j=2}^i a_j) = 3 \times 3 + 3 \times 5 + 3 \times 5 = 39$.