Little L은 정삼각형 격자를 가지고 있습니다. 여기서 각 격자선은 인접한 변들의 대응하는 $n$등분점을 잇는 선분입니다. 이 격자선들은 정삼각형을 합동인 여러 개의 작은 정삼각형으로 나눕니다.
그림에서 격자선의 각 교점을 좌표 $(x, y)$로 나타냅니다. 위에서 아래로 $x$좌표의 범위는 $1$부터 $n + 1$까지입니다. $x = 1$은 가장 위쪽 점을 나타내고, $x = n + 1$은 맨 아래쪽 직선을 나타냅니다. $i$번째 행에서 왼쪽에서 오른쪽으로 격자점들의 $y$좌표 범위는 $1$부터 $i$까지입니다.
삼각형 격자 안에는 여러 개의 정삼각형이 있으며, 방향은 똑바로 선 방향(위쪽을 향함)이거나 뒤집힌 방향(아래쪽을 향함)일 수 있습니다. 각 방향의 삼각형을 세 수 $x, y, d$로 나타냅니다. 여기서 $(x, y)$는 격자의 밑변에 평행한 변의 맞은편 꼭짓점의 좌표를 나타내고, $d$는 한 변의 길이(선분의 길이)를 나타냅니다.
예를 들어, 아래 그림에서 파란색 정삼각형은 똑바로 선 삼각형이며 $(x, y, d) = (4, 2, 3)$입니다. 노란색 정삼각형은 뒤집힌 삼각형이며 $(x, y, d) = (6, 3, 2)$입니다.

이제 각 단위 작은 정삼각형 격자(방향에 관계없이 한 변의 길이가 $1$인 정삼각형)마다 수가 하나씩 적혀 있습니다. 처음에 격자 위의 모든 수는 $0$입니다. Little L은 다음 연산들을 수행합니다:
- 정삼각형을 하나 선택하여 그 안에 있는 모든 격자의 수에 $w$를 더합니다.
- 정삼각형을 하나 선택하여 그 안에 있는 모든 격자의 수의 합을 질의합니다.
그는 여러분이 각 질의 연산에 대한 답을 계산해 주기를 바랍니다. Little L은 큰 수를 좋아하지 않으므로, 답을 $2^{32}$로 나눈 나머지만 출력하면 됩니다.
입력
입력의 첫째 줄에 두 정수 $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$)가 주어집니다.
다음 $q$개의 줄은 각각 하나의 연산을 나타냅니다.
각 줄은 다섯 개의 수 $opt, type, x, y, d$ ($opt \in \{1, 2\}, type \in \{0, 1\}, 1 \le x \le n + 1, 1 \le y \le x, 1 \le d \le n$)로 시작합니다. $opt$는 연산의 종류를 나타내며, $opt = 1$은 수정 연산이고 $opt = 2$는 질의 연산입니다. $type$은 이 연산에서 삼각형의 종류를 나타내며, $type = 0$은 똑바로 선 삼각형이고 $type = 1$은 뒤집힌 삼각형입니다. $x, y, d$는 이 삼각형을 설명합니다. 만약 $opt = 1$이면, 이 수정 연산 동안 더해지는 수를 나타내는 추가적인 수 $w$ ($0 \le w < 2^{32}$)가 주어집니다.
입력으로 주어지는 모든 삼각형은 넓이가 $0$이 아니며 큰 삼각형 내부에 완전히 포함되는 유효한 삼각형임이 보장됩니다.
출력
$opt = 2$인 각 질의마다 영역 내의 합을 $2^{32}$로 나눈 나머지를 나타내는 수 하나를 새 줄에 출력합니다.
예제
입력 1
5 5 1 0 3 3 2 2 1 1 6 4 2 3 2 0 1 1 5 2 0 3 2 3 2 1 5 3 2
출력 1
20 11 3
입력 2
10 10 1 0 1 1 5 2 1 1 3 2 1 6 1 1 6 4 2 1 2 0 10 3 1 2 1 5 2 1 2 1 6 4 2 1 0 7 7 1 7 1 1 9 3 1 3 1 0 9 5 2 4 2 0 6 1 2
출력 2
0 2 12 0