시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 1024 MB 133 11 2 13.333%

문제

Whiteking은 지역 꾸미기 게임을 하려고 한다. 그가 꾸미려는 지역은 단위 격자가 1 × 1 정사각형 타일로 표현되는 N × N 격자판 형태이며, 가장 왼쪽 위 타일의 좌표가 (1, 1)이고, 가장 오른쪽 아래 타일의 좌표는 (N, N)이다. 이 때 타일의 좌표란 타일의 오른쪽 아래 꼭짓점의 좌표를 말한다. 이로부터 (xy)에 위치한 타일은 [x-1x]×[y-1y]에 해당하는 정사각형 영역을 차지함을 알 수 있다. 각 타일은 고유한 아름다움 값을 가지는데, 초기에 모든 타일의 아름다움 값은 0이다.

지역 꾸미기 게임은 다음 세 가지 행동을 통해 점수를 얻는 게임이다.

  1. 가로 또는 세로로 직선을 그어 격자판을 서로 다른 구역으로 분할한다. 처음에는 N × 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번 행동을 한다.

Whiteking을 위해 3번 쿼리가 주어질 때마다 얻을 수 있는 점수를 구해보자!

입력

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

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

출력

3번 쿼리가 들어올 때마다 그 시점에서 Whiteking이 얻을 수 있는 최대 점수를 출력해라. 

제한

  • 1 ≤ ≤ 100,000
  • 1 ≤ Q ≤ 300,000
  • 모든 1번 쿼리에 대하여 0 ≤ a ≤ 1, 1 ≤ b ≤ N-1
  • 모든 2번 쿼리에 대하여 1 ≤ a, bN, -109X ≤ 109
  • 모든 3번 쿼리에 대하여 1 ≤ acN, 1 ≤ bdN
  • 2번 쿼리는 최대 25,000번만 주어진다.
  • 3번 쿼리는 하나 이상 주어진다.

예제 입력 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