지역 꾸미기 게임

Whiteking은 지역 꾸미기 게임을 하려고 한다. 그가 꾸미려는 지역은 1 × 1 정사각형 타일로 이루어진 $N \times N$ 격자판이다. 가장 왼쪽 위 타일의 좌표는 (1, 1)이고, 가장 오른쪽 아래 타일의 좌표는 (N, N)이다. 타일의 좌표는 그 타일의 오른쪽 아래 꼭짓점의 좌표를 뜻한다. 따라서 (x, y)에 있는 타일은 $[x-1, x] \times [y-1, y]$ 영역을 차지한다. 각 타일은 고유한 아름다움 값을 가지며, 처음에는 모든 타일의 아름다움 값이 0이다.

게임은 다음 세 가지 행동으로 점수를 얻는다.

1. 가로 또는 세로로 직선을 그어 격자판을 서로 다른 구역으로 나눈다. 처음에는 $N \times N$ 크기의 구역이 하나만 있다. 가로선 하나와 세로선 하나를 그으면 구역은 네 개가 된다.
2. 타일을 하나 골라 그 타일이 속한 구역을 꾸민다. 꾸며진 구역에 속한 모든 타일의 아름다움이 X만큼 증가한다.
3. 격자판에 포함되는 직사각형을 하나 고른다. 그 안의 타일 중 가장 아름다운 타일의 아름다움만큼 점수를 얻는다.

Whiteking은 3번 행동을 할 때마다 얻을 점수를 미리 알고 싶어 한다. 그래서 자신이 할 행동을 다음 쿼리로 나타낸다.

• 1 a b: a가 0이면 x = b, a가 1이면 y = b인 직선을 긋는다.
• 2 a b X: (a, b)에 있는 타일을 골라 2번 행동을 한다.
• 3 a b c d: 왼쪽 위 타일이 (a, b)이고 오른쪽 아래 타일이 (c, d)인 직사각형을 골라 3번 행동을 한다.

첫째 줄에 양의 정수 N과 Q가 주어진다.

둘째 줄부터 Q개의 줄에 쿼리가 한 줄에 하나씩 주어진다.

3번 쿼리가 주어질 때마다, 그 시점에서 Whiteking이 얻을 수 있는 최대 점수를 출력한다.

• 1 ≤ $N$ ≤ 100,000
• 1 ≤ $Q$ ≤ 300,000
• 모든 1번 쿼리에 대하여 0 ≤ a ≤ 1, 1 ≤ b ≤ N-1
• 모든 2번 쿼리에 대하여 1 ≤ a, b ≤ N, $-10^9$ ≤ X ≤ $10^9$
• 모든 3번 쿼리에 대하여 1 ≤ a ≤ c ≤ N, 1 ≤ b ≤ d ≤ N
• 2번 쿼리는 최대 25,000번 주어진다.
• 3번 쿼리는 하나 이상 주어진다.