18135번 - 겨울나기

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

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

영역은 겹치지 않으며, 각 영역마다 도토리를 저장해 두었다.

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

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

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

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

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

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

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

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

작업의 개수는 200,000 개를 넘지 않으며, 한 번의 작업에서 한 영역을 두 번 방문하는 경우는 없다.

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