15967번 - 에바쿰 서브태스크

재성이는 현실 세계에서 짱 쎈 친구이다! 너무 쎄서 학교의 학생 모두가 그를 보면 오금이 지릴 정도였는데, 그가 쎄지게 된 계기는 다음과 같다.

원래 재성이는 마법에 천부적인 재능이 있어서 순간적으로 공기의 압력을 증가시키는 에어 프레셔와 바쿰프레스라는 공격기술을, 그리고 이전으로 돌아갈 수 있는 타임머신 기술을 사용할 수 있는 마력을 가지고 있었다. 하지만 그걸 모르고 재혁이한테 뚜까맞던 재성이는 어느 순간 너무 화나서 각성을 했다.

각성 후에, 이때까지 쌓인 한을 풀기 위해 재성이는 재혁이를 i일엔 ai의 충격을 주면서 때렸다. 언제는 한번 변덕이 돋아서 j일부터 m일까지로 돌아가서 각각 l의 충격을 더해서 때리곤 했는데, 타임머신 기술을 활용하는 건 매우 힘든 일이므로 충격이 음수가 되면서 자기가 도리어 역으로 퍼맞을 수도 있다.

재혁이는 계속 뚜까맞다보니 자신이 n일부터 m일까지 얼마나 퍼맞았는지 궁금했다.

처절한 재혁이를 위해 재성이가 n일부터 m일까지 얼마나 때렸는지를 알려주자.

재성이가 재혁이를 때린 날수 N과 재성이가 변덕을 부린 날의 개수 Q1, 재혁이가 얼마나 맞았는지 궁금한 구간의 개수 Q2가 주어진다. (1 ≤ N ≤ 1,000,000, 0 ≤ Q1, Q2 ≤ 10,000)

그 다음줄엔 재혁이가 i번째 날에 맞았던 충격 a_i가 주어진다.(1 ≤ a_i ≤ 1,500,000)

그 다음 Q1+Q2 줄에는 다음과 같은 쿼리가 주어진다.

1. 1 n m : 재혁이가 n일부터 m일까지 맞은 양을 출력한다. 이 1번 쿼리는 Q2개 주어진다.(1 ≤ n, m ≤ N)
2. 2 s e l : 재성이가 s일에서 e일까지로 돌아가서 l의 충격을 더해서 때릴 수 있다. 이 2번 쿼리는 Q1개 주어진다.(-1,000 ≤ l ≤ 1,000, 1 ≤ s, e ≤ N)

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

• 2번쿼리가 존재하지 않으며, N ≤ 5,000

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

• N ≤ 5,000

• 재성이가 항상 첫번째 날부터 m일까지로만 돌아가서 때림이 보장된다. 즉, 2번 쿼리에서 s=1로 고정된다.

• N ≤ 500,000

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