Скоро состоится 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$.