การแข่งขันโอลิมปิกวิชาการนานาชาติด้านโครงสร้างข้อมูลครั้งที่ 38 กำลังจะจัดขึ้นในเร็ว ๆ นี้! Little Cyan Fish ต้องการผ่านการคัดเลือก ดังนั้นเขาจึงต้องผ่านการแข่งขันคัดเลือกทีมชาติ ในฐานะสมาชิกของทีม Fish เขาได้รับโจทย์ต่อไปนี้ในการแข่งขันคัดเลือกทีม Fish

ในปริภูมิสามมิติ มีจุด $(x, y, z)$ ที่มีพิกัดเป็นจำนวนเต็มอยู่อนันต์จุด น้ำหนักของจุดทั้งหมดเริ่มต้นเป็น $0$ Little Cyan Fish ต้องทำการดำเนินการ $q$ ครั้งตามลำดับ โดยแต่ละครั้งมีรูปแบบดังนี้:

• 1 x y z d w: สำหรับทุกจุด $(X, Y, Z)$ ที่ $|X - x| < d$, $|Y - y| < d$ และ $|Z - z| < d$ ให้บวก $w \cdot (d - \max(|X - x|, |Y - y|, |Z - z|))$ เข้ากับน้ำหนักของจุดนั้น
• 2 x1 x2 y1 y2 z1 z2: แสดงผลรวมของน้ำหนักของจุด $(X, Y, Z)$ ที่ $x_1 \le X \le x_2$, $y_1 \le Y \le y_2$ และ $z_1 \le Z \le z_2$ เนื่องจากผลรวมอาจมีค่ามาก จึงให้ตอบเป็นค่ามอดูโล $2^{28}$

ข้อมูลนำเข้า

มีหลายชุดข้อมูลทดสอบ บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มหนึ่งจำนวนคือ $T$ ($1 \le T$) ซึ่งระบุจำนวนชุดข้อมูลทดสอบ

สำหรับแต่ละชุดข้อมูลทดสอบ บรรทัดแรกประกอบด้วยจำนวนเต็มหนึ่งจำนวนคือ $q$ ($1 \le q \le 5 \times 10^4$) ซึ่งระบุจำนวนการดำเนินการ

แต่ละบรรทัดในอีก $q$ บรรทัดถัดไปประกอบด้วยจำนวนเต็มในรูปแบบใดรูปแบบหนึ่งต่อไปนี้:

• 1 x y z d w ($-10^9 \le x, y, z \le 10^9$, $1 \le d \le 10^9$, $0 \le w < 2^{28}$)
• 2 x1 x2 y1 y2 z1 z2 ($-10^9 \le x_1 \le x_2 \le 10^9$, $-10^9 \le y_1 \le y_2 \le 10^9$, $-10^9 \le z_1 \le z_2 \le 10^9$)

รับประกันว่าผลรวมของ $q$ จากทุกชุดข้อมูลทดสอบจะไม่เกิน $5 \times 10^4$

ข้อมูลส่งออก

สำหรับแต่ละชุดข้อมูลทดสอบ ให้พิมพ์จำนวนเต็มหนึ่งจำนวนในบรรทัดแยกกันสำหรับทุกการดำเนินการประเภทที่ $2$ นั่นคือผลรวมของน้ำหนักของจุดที่ต้องการมอดูโล $2^{28}$ ให้แสดงคำตอบตามลำดับของการดำเนินการ

ตัวอย่าง

ข้อมูลนำเข้า 1

2
7
1 0 0 0 2 1
2 -1 1 -1 1 -1 1
2 0 0 0 0 0 0
1 1 1 0 1 3
2 1 1 1 1 0 0
2 -1 1 -1 1 -1 1
2 2 2 0 0 0 0
1
2 0 0 0 0 0 0

ข้อมูลส่งออก 1

28
2
4
31
0
0

หมายเหตุ

ในชุดข้อมูลทดสอบแรก การอัปเดตครั้งแรกทำให้น้ำหนักที่จุดกำเนิดเป็น $2$ และให้น้ำหนักเป็น $1$ แก่จุดอื่น ๆ อีก $26$ จุดใน $[-1, 1]^3$ การอัปเดตครั้งที่สองบวก $3$ ให้กับจุด $(1, 1, 0)$

ในชุดข้อมูลทดสอบที่สอง น้ำหนักทั้งหมดเริ่มต้นเป็น $0$ อีกครั้ง