Whiteking은 지역 꾸미기 게임을 하려고 합니다. 그가 꾸미고자 하는 영역은 $N \times N$ 격자 형태이며, 단위 격자는 $1 \times 1$ 정사각형 타일로 표현됩니다. 왼쪽 상단 타일의 좌표는 $(1, 1)$이고, 오른쪽 하단 타일의 좌표는 $(N, N)$입니다. 따라서 타일의 좌표는 해당 타일의 오른쪽 하단 모서리 좌표를 의미합니다. 이를 통해 $(x, y)$에 위치한 타일은 $[x - 1, x] \times [y - 1, y]$에 해당하는 정사각형 영역을 차지함을 알 수 있습니다. 각 타일은 고유한 아름다움 값을 가지며, 처음에 모든 타일의 아름다움 값은 0입니다.

이 지역 꾸미기 게임은 플레이어가 다음 세 가지 행동을 사용하여 점수를 얻는 게임입니다.

• 수평 또는 수직으로 직선을 그어 격자를 서로 다른 구역으로 나눕니다. 처음에 격자에는 $N \times N$ 크기의 영역이 하나만 존재합니다. 선은 양방향으로 무한히 뻗어 나갑니다. 예를 들어, 수평선 하나와 수직선 하나를 그으면 초기 영역은 총 네 개의 영역으로 나뉩니다.
• 타일 하나를 선택하여 그 타일이 속한 영역을 꾸밉니다. 그 결과, 꾸며진 영역 내 모든 타일의 아름다움 값이 주어진 값만큼 증가합니다.
• 격자 위의 직사각형 하나를 선택하고, 그 안에 있는 가장 아름다운 타일의 아름다움 값만큼 점수를 얻습니다.

Whiteking은 세 번째 유형의 각 행동에 대해 자신이 몇 점을 얻게 될지 미리 알고 싶어 합니다. 그래서 그는 자신이 수행할 행동의 순서 목록을 보여줄 것입니다. 행동은 다음 형식으로 주어집니다.

• “1 a b”: $a$가 0이면 직선 $x = b$를 긋고, $a$가 1이면 직선 $y = b$를 긋습니다.
• “2 a b X”: $(a, b)$에 위치한 타일을 선택하여 그 타일이 속한 영역을 꾸미고, 그 영역 내 모든 타일의 아름다움 값을 $X$만큼 증가시킵니다.
• “3 a b c d”: $(a, b)$를 왼쪽 상단 타일로, $(c, d)$를 오른쪽 하단 타일로 하는 직사각형을 선택하고, 그 안에 있는 가장 아름다운 타일의 아름다움 값만큼 점수를 얻습니다.

Whiteking이 세 번째 유형의 모든 행동에 대해 얻게 될 점수를 구할 수 있도록 도와주세요.

입력

첫 번째 줄에는 두 정수 $N$과 $Q$ ($1 \le N \le 10^5$, $1 \le Q \le 3 \cdot 10^5$)가 주어집니다.

다음 $Q$개의 줄 각각은 문제 설명에 제시된 형식의 행동을 나타냅니다.

1번 유형의 행동에 대해, $0 \le a \le 1$이고 $1 \le b \le N - 1$입니다. 2번 유형의 행동에 대해, $1 \le a, b \le N$이고 $-10^9 \le X \le 10^9$입니다. 3번 유형의 행동에 대해, $1 \le a \le c \le N$이고 $1 \le b \le d \le N$입니다.

2번 유형의 행동은 최대 25,000개이며, 3번 유형의 행동은 최소 1개 이상 존재합니다.

출력

3번 유형의 모든 행동에 대해, Whiteking이 해당 행동으로 얻게 될 점수를 출력하십시오.

예제

입력 1

3 7
3 1 1 3 3
2 1 3 -3
3 1 1 3 3
1 0 1
2 1 1 4
3 2 2 3 3
3 1 1 3 3

출력 1

0
-3
-3
1