시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 33 19 15 62.500%

문제

지안지아는 똑같은 크기의 벽돌을 쌓아서 벽을 만들고 있다. 이 벽은 n열의 벽돌로 되어 있는데, 각 열은 왼쪽부터 오른쪽으로 차례대로 0부터 n-1까지 번호가 매겨져 있다. 각 열의 높이는 서로 다를 수 있다. 열의 높이는 이 열에 쌓인 벽돌의 수이다.

지안지아는 다음과 같이 벽을 만든다. 처음에는 어느 열에도 벽돌이 없다. 다음, 지안지아는 k 단계에 걸쳐 벽돌을 더하거나 또는 빼거나 한다. k 단계가 다 끝나면 벽을 다 쌓은 것이다. 매 단계마다 지안지아는 연속된 벽돌 열의 범위와 높이 h를 받고, 다음과 같은 절차에 따라 정해진 일을 한다.

  • 벽돌을 더하는 단계에서는, 지안지아는 주어진 범위에 해당하는 열들 중 h장 미만의 벽돌이 쌓인 열들에 벽돌을 더해서 정확히 벽돌 h장이 쌓이게 한다. h장 이상 벽돌이 있는 열에는 아무 일도 하지 않는다.
  • 벽돌을 빼는 단계에는, 지안지아는 주어진 범위에 해당하는 열들 중 h장 초과의 벽돌이 쌓인 열들에서 벽돌을 빼서 정확히 벽돌 h장이 쌓이게 한다. h장 이하 벽돌이 있는 열에는 아무 일도 하지 않는다.

당신이 할 일은 벽의 최종 모양을 결정하는 것이다.

10열의 벽돌이 있고 6단계를 거쳐 벽을 만든다고 가정하자. 아래 표의 모든 범위는 양 끝을 포함한다. 각 단계가 끝났을 때 벽의 모양은 아래 그림과 같다.

단계 하는 일 범위 높이
0 더하기 1열부터 8열까지 4
1 빼기 4열부터 9열까지 1
2 빼기 3열부터 6열까지 5
3 더하기 0열부터 5열까지 3
4 더하기 2열 5
5 빼기 6열부터 7열까지 0

처음에 모든 열에는 벽돌이 없기 때문에, 단계 0이 끝나면 1열부터 8열까지는 모두 4장의 벽돌이 있다. 0열과 9열은 비어 있다. 단계 1에서는, 4열부터 8열까지는 벽돌이 빠져서 모든 열에 각각 벽돌이 1장이 있고, 9열은 계속 비어 있다. 주어진 범위 밖인 0열부터 3열은 아무 변화가 없다. 단계 2는 아무 변화가 없는데, 3열부터 6열까지 5장을 초과하여 벽돌이 있는 열이 없기 때문이다. 단계 3이 끝나면 0, 4, 5열의 벽돌은 3장으로 늘어난다. 단계 4가 끝나면 2열에는 벽돌이 5장 있다. 단계 5는 6열과 7열의 모든 벽돌을 없앤다.

각 단계에서 하는 일이 주어졌을 때, 모든 단계가 끝난 다음 각 열에 남아 있는 벽돌의 수를 계산하시오.

입력

첫째 줄에 벽에 있는 열의 수 n과 단계의 수 k가 주어진다. (1 ≤ n ≤ 2,000,000, 1 ≤ k ≤ 500,000)

둘째 줄부터 총 k개의 줄에 걸쳐서 단계 i에서 하는 일이 주어진다. op, left, right, height로 이루어져 있으며, 아래와 같은 의미를 갖는다.

  • op: 1이면 더하는 단계, 2이면 빼는 단계이다.
  • left와 right: 각 단계에 해당하는 열의 범위이다. left 열에서 시작하고, right 열에서 끝난다. (양 끝점 left와 right도 포함된다) 항상 left ≤ right이다.
  • height: 각 단계에서 주어지는 높이이다. (0 ≤ height ≤ 100,000)

출력

모든 단계가 끝난 다음 각 열에 남아 있는 벽돌의 수를 한 줄에 하나씩 순서대로 출력한다.

예제 입력

10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0

예제 출력

3
4
5
4
3
3
0
0
1
0

힌트