지문의 소재가 바람직하지 않고, 가독성도 떨어지기에 지문을 다시 작성해 보았습니다. 오역이 있다면 알려주세요.

문제

재성이는 아주 센 캐릭터를 가진 게이머이다! 너무 세서 학교의 학생 모두가 그를 이기지 못했는데, 그가 세지게 된 계기는 다음과 같다.

원래 재성이의 캐릭터는 마법에 천부적인 재능이 있어서 순간적으로 공기의 압력을 증가시키는 에어 프레셔와 바쿰프레스라는 공격 기술을, 그리고 이전으로 돌아갈 수 있는 타임머신 기술을 사용할 수 있는 마력을 가지고 있었다. 하지만 그걸 몰랐던 재성이는 캐릭터의 재능을 제대로 써먹지 못해 게임에서 계속해서 졌고, 어느 순간 각성하기로 결심했다.

각성을 위해 재성이는 캐릭터를 강화하기 시작했다. $i$일째에는 $a_i$만큼 강화했고, 때때로 변덕이 돋아서 $s$일부터 $e$일까지로 돌아가서 각각 $l$만큼 더 강화하곤 했는데, 타임머신 기술을 활용하는 건 매우 힘든 일이므로 강화한 양이 음수가 되면서 캐릭터가 약해질 수도 있다.

어느 날 재성이는 자신이 $n$일부터 $m$일까지 캐릭터를 얼마나 강화했는지 궁금해졌다.

재성이를 위해 $n$일부터 $m$일까지 캐릭터가 얼마나 강해졌는지 알려주자.

입력

재성이가 캐릭터를 강화한 날의 수 $N$ 과 재성이가 변덕을 부린 날의 수 $Q_1$, 캐릭터가 얼마나 강해졌는지 궁금한 구간의 개수 $Q_2$가 입력된다. ($1 \le N \le 10^6, 0 \le Q_1, Q_2 \le 10^4$)

그 다음줄엔 재성이가 $i$번째 날에 캐릭터를 강화한 양 $a_i$가 공백으로 구분되어 입력된다.($1 \le a_i \le 1.5 \times 10^6$)

그 다음 ($Q_1 + Q_2$)줄에는 다음과 같은 쿼리가 주어진다.

1.  $1$ $n$ $m$: 재성이가 $n$일부터 $m$일까지 캐릭터를 강화한 양을 출력한다. 이 1번 쿼리는 $Q_2$개 주어진다. ($1 \le n \le m \le N$)
2.  $2$ $s$ $e$ $l$ : 재성이가 $s$일에서 $e$일까지로 돌아가서 각각 $l$만큼 더 강화한다. 이 2번 쿼리는 $Q_1$개 주어진다. ($-10^3 \le l \le 10^3, 1 \le s \le e \le N$)

출력

1번 쿼리에 대한 답을 $Q_2$줄에 걸쳐 차례대로 출력한다.

서브태스크 1 (15점)

• 2번 쿼리가 존재하지 않으며, $N \le 5 \times 10^3$을 만족한다.

서브태스크 2 (10점)

• 2번 쿼리가 존재하지 않는다.

서브태스크 3 (30점)

•  $N \le 5 \times 10^3$을 만족한다.

서브태스크 4 (25점)

• 2번 쿼리에서 $s = 1$ 로 고정된다.

서브태스크 5 (15점)

•  $N \le 5 \times 10^5$을 만족한다.

서브태스크 6 (5점)

• 문제에서 주어진 제약 조건 외 다른 조건은 없다.