לאחר מבחני המיון לנבחרת המחוזית, White שקעה בתקופה ארוכה של אכזבה. היא לא הצליחה למצוא שום תקווה בתוצאות שלה. אף על פי כן, White המשיכה באימונים האחרונים שלה לקראת ה-NOI. מלבד האימונים הרגילים שלה, היא החלה לחקור גם נושאים שמעולם לא הזדמן לה ללמוד במהלך ימיה ב-OI — בתקווה שלפני הפרידה, לא יישארו עוד חרטות.

כשהיא מנערת מעליה את מחשבותיה הנודדות, White התמקדה לפתע בבעיה שלפניה, בעיית מבני נתונים פשוטה ומשעממת —

ל-White יש סדרה של $n$ מספרים שלמים $a_1, a_2, \dots, a_n$. היא תבצע $q$ פעולות על סדרה זו. כל פעולה היא מאחד משלושת הסוגים הבאים:

• 1 l r v — הוסף $v$ לכל איבר בקטע $[l, r]$.
• 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$), המייצגת את פעולת השאילתה.

מובטח כי $0 \le a_i \le 10^9$ עבור כל $1 \le i \le n$ לאורך כל התהליך.

פלט

עבור כל פעולת שאילתה, הדפס מספר שלם בשורה בודדת — תוצאת השאילתה מודולו $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$.