Little L มีตารางรูปสามเหลี่ยมด้านเท่า ซึ่งเส้นตารางแต่ละเส้นคือส่วนของเส้นตรงที่เชื่อมจุดแบ่ง $n$ ส่วนที่สมนัยกันของด้านที่อยู่ติดกัน เส้นตารางเหล่านี้แบ่งรูปสามเหลี่ยมด้านเท่าออกเป็นรูปสามเหลี่ยมด้านเท่าขนาดเล็กที่เท่ากันทุกประการหลายรูป
สำหรับจุดตัดแต่ละจุดของเส้นตารางในรูป เราแทนด้วยพิกัด $(x, y)$ โดยพิกัด $x$ จากบนลงล่างมีค่าตั้งแต่ $1$ ถึง $n + 1$ ซึ่ง $x = 1$ แทนจุดบนสุด ในขณะที่ $x = n + 1$ แทนเส้นฐานด้านล่าง สำหรับแถวที่ $i$ พิกัด $y$ ของจุดตารางจากซ้ายไปขวามีค่าตั้งแต่ $1$ ถึง $i$
ในตารางสามเหลี่ยมมีรูปสามเหลี่ยมด้านเท่าอยู่หลายรูป ซึ่งอาจวางตัวในแนวตั้ง (หัวชี้ขึ้น) หรือแนวกลับหัว (หัวชี้ลง) สำหรับแต่ละทิศทางของรูปสามเหลี่ยม เราแทนด้วยตัวเลขสามตัวคือ $x, y, d$ โดยที่ $(x, y)$ แทนพิกัดของจุดยอดที่อยู่ตรงข้ามกับด้านที่ขนานกับเส้นฐานของตาราง และ $d$ แทนความยาวด้านของรูปสามเหลี่ยมนั้น (ความยาวของส่วนของเส้นตรง)
ตัวอย่างเช่น ในรูปด้านล่าง รูปสามเหลี่ยมด้านเท่าสีน้ำเงินเป็นรูปสามเหลี่ยมแนวตั้ง ซึ่งมี $(x, y, d) = (4, 2, 3)$ ส่วนรูปสามเหลี่ยมด้านเท่าสีเหลืองเป็นรูปสามเหลี่ยมแนวกลับหัว ซึ่งมี $(x, y, d) = (6, 3, 2)$

ตอนนี้ สำหรับแต่ละช่องตารางสามเหลี่ยมด้านเท่าขนาดเล็กหนึ่งหน่วย (รูปสามเหลี่ยมด้านเท่าที่มีความยาวด้านเป็น $1$ ไม่ว่าจะอยู่ในทิศทางใด) จะมีตัวเลขเขียนอยู่หนึ่งตัว เริ่มต้นตัวเลขทั้งหมดบนตารางเป็น $0$ Little L จะทำการดำเนินการต่อไปนี้:
- เลือกรูปสามเหลี่ยมด้านเท่าหนึ่งรูป แล้วบวก $w$ ให้กับตัวเลขทั้งหมดบนช่องตารางที่อยู่ภายในรูปสามเหลี่ยมนั้น
- เลือกรูปสามเหลี่ยมด้านเท่าหนึ่งรูป แล้วสอบถามผลรวมของตัวเลขทั้งหมดบนช่องตารางที่อยู่ภายในรูปสามเหลี่ยมนั้น
เขาหวังว่าคุณจะสามารถคำนวณคำตอบสำหรับการดำเนินการสอบถามแต่ละครั้งได้ เนื่องจาก Little L ไม่ชอบตัวเลขขนาดใหญ่ คุณจึงต้องแสดงผลลัพธ์ของคำตอบมอดูโล $2^{32}$ เท่านั้น
ข้อมูลนำเข้า
บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มสองตัว $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$)
อีก $q$ บรรทัดถัดไป แต่ละบรรทัดแทนการดำเนินการหนึ่งครั้ง
แต่ละบรรทัดเริ่มต้นด้วยตัวเลขห้าตัวคือ $opt, type, x, y, d$ ($opt \in \{1, 2\}, type \in \{0, 1\}, 1 \le x \le n + 1, 1 \le y \le x, 1 \le d \le n$) โดย $opt$ แทนชนิดของการดำเนินการ ซึ่ง $opt = 1$ คือการดำเนินการแก้ไข และ $opt = 2$ คือการดำเนินการสอบถาม ส่วน $type$ ระบุชนิดของรูปสามเหลี่ยมสำหรับการดำเนินการนี้ ซึ่ง $type = 0$ สำหรับรูปสามเหลี่ยมแนวตั้ง และ $type = 1$ สำหรับรูปสามเหลี่ยมแนวกลับหัว และ $x, y, d$ อธิบายรูปสามเหลี่ยมนี้ หาก $opt = 1$ จะมีตัวเลขเพิ่มเติมอีกหนึ่งตัวคือ $w$ ($0 \le w < 2^{32}$) ซึ่งระบุจำนวนที่บวกเพิ่มในการดำเนินการแก้ไขครั้งนี้
รับประกันว่ารูปสามเหลี่ยมในข้อมูลนำเข้าทั้งหมดมีพื้นที่ไม่เป็นศูนย์ และเป็นรูปสามเหลี่ยมที่ถูกต้องซึ่งอยู่ภายในรูปสามเหลี่ยมใหญ่ทั้งหมด
ข้อมูลส่งออก
สำหรับแต่ละการสอบถามที่มี $opt = 2$ ให้พิมพ์ตัวเลขหนึ่งตัวในบรรทัดใหม่ แทนผลรวมภายในพื้นที่นั้นมอดูโล $2^{32}$
ตัวอย่าง
ข้อมูลนำเข้า 1
5 5 1 0 3 3 2 2 1 1 6 4 2 3 2 0 1 1 5 2 0 3 2 3 2 1 5 3 2
ข้อมูลส่งออก 1
20 11 3
ข้อมูลนำเข้า 2
10 10 1 0 1 1 5 2 1 1 3 2 1 6 1 1 6 4 2 1 2 0 10 3 1 2 1 5 2 1 2 1 6 4 2 1 0 7 7 1 7 1 1 9 3 1 3 1 0 9 5 2 4 2 0 6 1 2
ข้อมูลส่งออก 2
0 2 12 0