제38회 국제 자료구조 올림피아드가 곧 개최됩니다! Little Cyan Fish는 출전 자격을 얻고 싶어 하며, 이를 위해 국가대표 선발전을 통과해야 합니다. Fish 팀의 일원으로서, 그는 Fish 팀 선발전에서 다음과 같은 문제를 받았습니다.

3차원 공간에 정수 좌표를 가지는 점 $(x, y, z)$가 무수히 많이 존재합니다. 모든 점의 가중치는 처음에 $0$입니다. Little Cyan Fish는 $q$개의 연산을 순서대로 수행해야 하며, 각 연산은 다음 형태 중 하나입니다:

• 1 x y z d w: $|X - x| < d$, $|Y - y| < d$, 그리고 $|Z - z| < d$를 만족하는 모든 점 $(X, Y, Z)$에 대하여, 그 가중치에 $w \cdot (d - \max(|X - x|, |Y - y|, |Z - z|))$를 더합니다.
• 2 x1 x2 y1 y2 z1 z2: $x_1 \le X \le x_2$, $y_1 \le Y \le y_2$, 그리고 $z_1 \le Z \le z_2$를 만족하는 점 $(X, Y, Z)$들의 가중치 총합을 출력합니다. 총합이 매우 클 수 있으므로, $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, 1]^3$ 내의 다른 $26$개의 점에 각각 가중치 $1$을 부여합니다. 두 번째 업데이트는 점 $(1, 1, 0)$에 $3$을 더합니다.

두 번째 테스트 케이스에서는 모든 가중치가 처음에 다시 $0$이 됩니다.