האולימפיאדה הבינלאומית ה-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$.