Невдовзі відбудеться 38-ма Міжнародна олімпіада зі структур даних! Little Cyan Fish хоче кваліфікуватися, тому він повинен пройти відбіркове змагання до національної збірної. Як учаснику команди Fish, на відбірковому змаганні Fish Team Selection йому запропонували таку задачу.

У тривимірному просторі є нескінченно багато точок $(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$.