Olimpiade Internasional Struktur Data ke-38 akan segera berlangsung! Little Cyan Fish ingin lolos kualifikasi, sehingga ia harus melewati kontes seleksi tim nasional. Sebagai anggota tim Fish, ia diberikan soal berikut dalam kontes Seleksi Tim Fish.

Di dalam ruang tiga dimensi, terdapat tak hingga banyaknya titik $(x, y, z)$ dengan koordinat bilangan bulat. Semua bobot titik awalnya adalah $0$. Little Cyan Fish harus melakukan $q$ operasi secara berurutan, masing-masing berbentuk:

• 1 x y z d w: Untuk setiap titik $(X, Y, Z)$ dengan $|X - x| < d$, $|Y - y| < d$, dan $|Z - z| < d$, tambahkan $w \cdot (d - \max(|X - x|, |Y - y|, |Z - z|))$ ke bobotnya.
• 2 x1 x2 y1 y2 z1 z2: Keluarkan total bobot dari titik-titik $(X, Y, Z)$ dengan $x_1 \le X \le x_2$, $y_1 \le Y \le y_2$, dan $z_1 \le Z \le z_2$. Totalnya bisa sangat besar, jadi berikan hasilnya modulo $2^{28}$.

Masukan

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat $T$ ($1 \le T$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi sebuah bilangan bulat $q$ ($1 \le q \le 5 \times 10^4$), yang menyatakan banyaknya operasi.

Masing-masing dari $q$ baris berikutnya berisi bilangan-bilangan bulat dalam salah satu bentuk berikut:

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

Dijamin bahwa jumlah dari $q$ di seluruh kasus uji tidak melebihi $5 \times 10^4$.

Keluaran

Untuk setiap kasus uji, cetak satu bilangan bulat pada baris terpisah untuk setiap operasi bertipe $2$: jumlah bobot titik yang diminta modulo $2^{28}$. Berikan jawaban sesuai urutan operasi.

Contoh

Masukan 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

Keluaran 1

28
2
4
31
0
0

Catatan

Pada kasus uji pertama, pembaruan pertama memberikan bobot $2$ pada titik asal dan bobot $1$ pada masing-masing dari $26$ titik lainnya di $[-1, 1]^3$. Pembaruan kedua menambahkan $3$ pada titik $(1, 1, 0)$.

Pada kasus uji kedua, semua bobot awalnya kembali bernilai $0$.