순환도로

도로, Matteo Paganelli 촬영, Unsplash

아이슬란드 도로청은 전국 도로의 유지·보수 비용을 관리하기 위한 새로운 전산 시스템을 구현하고 있다. 첫 번째 과제는 아이슬란드에서 가장 중요한 도로인 순환도로에 이 시스템을 구현하는 것이다. 관리를 단순화하기 위해 먼저 순환도로를 길이가 같은 $N$개의 구간으로 나누고, 이를 $1, 2, \dots, N$로 번호를 매긴다. 여기서 $1$은 Akureyri에서 서쪽으로 뻗은 도로이며, 그 방향을 따라 구간 번호가 증가한다. 따라서 구간 $N$은 Akureyri 동쪽의 도로이다. 시스템은 다음 연산들을 지원해야 한다. 어떤 도로 구간에 속한 각 도로 조각에 $x$만큼의 비용을 기록할 수 있어야 한다. 또한 어떤 도로 구간의 현재까지 누적된 총비용이 얼마인지 질의할 수 있어야 한다. 마지막으로 구간 $1$이 새로운 위치에 오도록 시스템의 번호 매기기를 변경할 수 있어야 한다. 여기서 도로 구간이란 도로 조각들의 연속된 구간을 뜻한다. 구간 $3, 6$은 조각 $3, 4, 5, 6$이다. 반면 전체 조각 수가 $6$개라면 $5, 2$은 조각 $5, 6, 1, 2$이다. $3, 3$은 조각 $3$ 하나뿐이다. 번호를 다시 매긴 뒤에도 시스템의 방향은 그대로 유지된다. 즉, 반시계 방향으로 이동할 때 조각 번호가 증가한다. $1$칸 회전한다는 것은 이전에 $1$번이었던 도로 조각이 이제 $N$번이 되고, 이전에 $2$번이었던 도로 조각이 이제 $1$번이 된다는 뜻이다.

점수

그룹 | 점수 | 제한

1 | 20 | $1 \leq n \leq 1000$

2 | 50 | 모든 도로 구간에서 $l \leq r$이며 회전 명령이 없음

3 | 30 | 추가 제한 없음

첫째 줄에 도로 조각의 수 $n$과 질의의 수 $q$을 나타내는 두 정수가 주어진다. ($1 \leq n \leq 10^6$, $1 \leq q \leq 10^4$). 다음 $q$개 줄에는 각 줄마다 질의 하나가 주어진다. 각 질의는 한 줄이며 숫자 $1, 2$ 또는 $3$로 시작한다. 이 숫자가 $1$이면 이어서 숫자 $t$가 하나 주어진다. ($1 \leq t \leq N$) 이는 번호 매기기를 반시계 방향으로 $t$칸 이동해야 한다는 뜻이다. 이 숫자가 $2$이면 이어서 세 정수 $l, r, x$가 주어진다. ($1 \leq l, r \leq N$, $1 \leq x \leq 10^9$) 이는 $l$부터 $r$까지의 도로 구간에 속한 각 조각의 누적 비용을 $x$만큼 갱신해야 한다는 뜻이다. 마지막으로 이 숫자가 $3$이면 두 정수 $l, r$가 주어진다. ($1 \leq l, r \leq N$) 이때 $l$부터 $r$까지의 도로 구간에 지금까지 누적된 총비용을 출력해야 한다.

$3$로 시작하는 각 질의마다 한 줄을 출력하며, 해당 출력은 위에서 설명한 것과 같다.