시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 11 4 3 50.000%

문제

가톨릭대학교 텔레토비 동산에는 겨울을 준비하는 다람쥐 다다가 살고 있다. 다다는 교내에서 자신만의 원형의 산책로를 가지고 있다.

다다는 원형의 산책로를 N (1 ≤ N ≤ 2,000,000)개의 칸으로 구분하고 1번부터 N번 까지 번호가 매겼고, 한 개의 칸 혹은 연속된 여러 칸을 M (1 ≤ M ≤ 1,000,000)개의 영역으로 지정했으며, 1번부터 M번까지 번호를 매겼다. 한 영역은 꽃밭, 건물 등 학교에서의 한 장소나 시설을 의미 한다. 1번 칸은 무조건 1번 영역에 속하며, 칸과 영역의 번호는 시계방향으로 매겨진다. 다다의 이동 방향도 시계방향으로만 움직인다.

영역은 겹치지 않는다.

다다는 영역마다 도토리를 저장해 두었다.

겨울이 오기 전 산책로를 따라걸으며 어떤 영역에 포함되는 칸을 지나면 그 영역에 저장된 도토리의 수량을 합하며 점검하고, 산책 중에 학생들에게 받은 도토리들을 저장하려고 한다. 겨울잠이 끝나고 다람쥐 다다가 눈을 뜰 수 있도록 다다를 도와주자.

입력

첫 줄에 산책로의 칸수 N, 영역 수 M이 주어진다.

두 번째 줄부터 M개의 줄에 세 개의 정수 a, b, c가 주어지고 영역의 시작 칸의 번호, 끝 칸의 번호, 그 영역에 저장되어있는 도토리의 개수(0 ≤ c ≤ 1,000,000)를 뜻한다.

이어서 M+2번째 줄부터 다다의 작업들이 주어지는데, 3개의 정수 혹은 4개의 정수가 주어진다.

첫 번째 정수가 1인 경우는 이어서 x, y가 2인 경우에는 이어서 x, y, z (1 ≤ z ≤ 1,000,000)가 입력으로 주어진다.x는 산책을 시작하는 칸번호, y는 산책을 종료하는 칸번호, z는 추가로 저장할 도토리의 개수를 의미한다.

0 0 0을 입력받은 경우는 작업입력을 종료한다.

첫 번째 정수가 1인 경우 다다가 x번째 칸부터 y번째 칸까지 산책을 하며 지나가는 영역에 저장된 토토리 개수를 체크하는 작업이고, 첫 번째 정수가 2인 경우 다다가 x번째 칸부터 y번 째 칸에 도토리를 z개씩 저장하는 작업을 의미 한다.

주어지는 xy보다 큰 경우도 존재한다. 다다는 시계방향으로만 산책을 하기 때문에 xy보다 큰 경우 xx+1 ➝ … ➝ N ➝ 1 ➝ 2 ➝ … ➝ y 의 순서로 칸을 이동하는 점을 유의하라

합을 출력하는 쿼리의 개수와 변경되는 영역의 전체 개수의 합은 1,000,000 을 넘지 않는다.

출력

다다의 작업입력 중 첫 번째 정수가 1인경우 이어 입력받은 x부터 y칸에 해당하는 영역에 저장된 도토리 개수의 합을 출력한다.

예제 입력 1

12 6
1 2 1
3 3 1
4 5 1
6 8 1
9 11 1
12 12 1
1 1 2
2 1 2 2
1 1 2
1 3 1
2 3 3 2
1 3 1
0 0 0

예제 출력 1

1
3
8
10