Kỳ thi Olympic Quốc tế về Cấu trúc Dữ liệu lần thứ 38 sẽ sớm diễn ra! Little Cyan Fish muốn giành quyền tham dự, vì vậy cậu phải vượt qua kỳ thi tuyển chọn đội tuyển quốc gia. Là một thành viên của đội Fish, cậu đã được giao bài toán sau đây trong kỳ thi Tuyển chọn Đội tuyển Fish.

Trong không gian ba chiều, có vô số điểm $(x, y, z)$ với tọa độ nguyên. Trọng số của tất cả các điểm ban đầu đều bằng $0$. Little Cyan Fish phải thực hiện lần lượt $q$ thao tác theo thứ tự, mỗi thao tác có dạng:

• 1 x y z d w: Với mọi điểm $(X, Y, Z)$ thỏa mãn $|X - x| < d$, $|Y - y| < d$, và $|Z - z| < d$, cộng thêm $w \cdot (d - \max(|X - x|, |Y - y|, |Z - z|))$ vào trọng số của nó.
• 2 x1 x2 y1 y2 z1 z2: In ra tổng trọng số của các điểm $(X, Y, Z)$ thỏa mãn $x_1 \le X \le x_2$, $y_1 \le Y \le y_2$, và $z_1 \le Z \le z_2$. Tổng này có thể rất lớn, vì vậy hãy đưa ra kết quả theo modulo $2^{28}$.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $T$ ($1 \le T$), cho biết số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu, dòng đầu tiên chứa một số nguyên duy nhất $q$ ($1 \le q \le 5 \times 10^4$), cho biết số lượng thao tác.

Mỗi dòng trong $q$ dòng tiếp theo chứa các số nguyên theo một trong các dạng sau:

• 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$).

Dữ liệu đảm bảo rằng tổng của $q$ trên tất cả các bộ dữ liệu không vượt quá $5 \times 10^4$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, hãy in ra một số nguyên trên một dòng riêng biệt cho mỗi thao tác loại $2$: tổng trọng số các điểm cần tìm theo modulo $2^{28}$. Hãy đưa ra các câu trả lời theo đúng thứ tự của các thao tác.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

28
2
4
31
0
0

Ghi chú

Trong bộ dữ liệu đầu tiên, thao tác cập nhật đầu tiên gán trọng số $2$ cho gốc tọa độ và trọng số $1$ cho mỗi điểm trong $26$ điểm còn lại thuộc $[-1, 1]^3$. Thao tác cập nhật thứ hai cộng thêm $3$ vào điểm $(1, 1, 0)$.

Trong bộ dữ liệu thứ hai, tất cả các trọng số ban đầu lại bằng $0$.