بعد اختيار فريق المقاطعة، دخلت 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$.