ستُقام الدورة الثامنة والثلاثون للأولمبياد الدولي في هياكل البيانات قريبًا! يريد 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$ في البداية مرة أخرى.