깃발춤

매일 코딩만 하던 상헌이는 두뇌가 코드에만 잠겨 있는 것 같아, 다른 방면으로 머리를 쓰기 위해 깃발춤 공연을 보러 가기로 했다. 깃발춤 공연은 N명의 공연자가 일렬로 서서 깃발을 힘 있게 흔들며 진행된다. 깃발을 든 공연자는 각자 카리스마 ci를 지니고 있어, 몇몇 공연자는 더 절도 있게 깃발을 흔든다.

상헌이는 깃발춤을 보다가 몇몇 연속된 공연자가 깃발을 교대로 흔드는 것을 목격했다. 상헌이는 이를 '교대 깃발춤'이라 이름 붙였다. 교대 깃발춤은 L번째 공연자부터 R번째 공연자까지 각자 깃발을 왼쪽 또는 오른쪽으로 흔드는 동작이다. L번째 공연자를 포함해 L번째 공연자와의 거리가 짝수인 공연자는 깃발을 왼쪽으로 흔들고, 거리가 홀수인 공연자는 오른쪽으로 흔든 뒤, 다시 깃발을 몸 쪽으로 원위치시킨다. 여기서 x번째 공연자와 y번째 공연자 사이의 거리는 |x - y|이다.

문제 해결에서 벗어날 수 없었던 상헌이는 교대 깃발춤에서 왼쪽으로 깃발을 흔든 공연자의 카리스마 합과 오른쪽으로 깃발을 흔든 공연자의 카리스마 합의 차이의 절댓값을 교대 깃발춤의 균일도라고 부르기로 했다. 균일도가 크다는 것은 한쪽이 다른 쪽보다 압도적으로 카리스마가 느껴진다는 뜻이므로 비대칭적으로 보일 수 있다. 상헌이는 교대 깃발춤의 균일도가 중요한 의미를 지닌다고 생각한다. 또 깃발을 흔드는 공연자는 공연의 열기와 순간순간의 실수에 휩쓸리기 때문에 카리스마가 증가하거나 감소할 수 있다. 이런 상황을 모두 고려해 상헌이는 매 교대 깃발춤의 균일도를 구하고 싶어졌다. 상헌이를 도와주자!

첫 번째 줄에는 깃발춤을 진행하는 공연자의 명수인 자연수 N과 상황 변화의 개수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 300,000, 1 ≤ Q ≤ 300,000)
두 번째 줄에는 정수 c1, c2, ..., cN 이 공백으로 구분되어 주어지며, ci 는 i번째 공연자의 카리스마를 의미한다. (-100,000 ≤ ci ≤ 100,000)
세 번째 줄부터 Q개의 줄에 걸쳐 다음 형식 중 하나로 세 정수가 공백으로 구분되어 주어진다.\

• 1 L R : L번째 공연자부터 R번째 공연자까지 구성된 교대 깃발춤이 시연된다. (1 ≤ L ≤ R ≤ N)\
• 2 L x : L번째 공연자의 카리스마가 정수 x만큼 증가한다. (1 ≤ L ≤ N, -100,000 ≤ x ≤ 100,000)
  첫 번째 종류('1 L R' 꼴)의 쿼리는 한 번 이상 주어짐이 보장된다.

첫 번째 종류의 쿼리가 입력될 때마다 매 줄에 해당하는 교대 깃발춤의 균일도를 출력한다.