หลังจากการคัดเลือกตัวแทนมณฑล 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$) แทนการดำเนินการบวก (Add)
• 2 l r v ($1 \le l \le r \le n, 1 \le v \le 10^9$) แทนการดำเนินการกำหนดค่า (Assign)
• 3 l r ($1 \le l \le r \le n$) แทนการดำเนินการสอบถาม (Query)

รับประกันว่า $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$