원자

반과학 연구 단지 <>의 이상 물질 연구소에서는 최근 개발된 흑연 나노막대를 두고 실험을 진행한다. 흑연 나노막대는 일직선 위에 놓인 $n$개의 탄소 원자가 차례로 이어진 형태다. 각 원자는 전하를 가진다.

실험을 위해 막대를 수직으로 세운다. 원자에 아래에서 위로 1번부터 $n$번까지 번호를 붙인다. 두 원자가 이웃하고 위쪽 원자의 전하가 아래쪽 원자보다 정확히 1만큼 크면 두 원자 사이에 강한 결합이 생긴다. 즉 원자 $a$와 $b$는 $a = b + 1$이고 $q_a = q_b + 1$일 때 강한 결합으로 연결된다. 여기서 $q_i$는 $i$번 원자의 전하다. 원자 사슬이란 강한 결합으로 이어진 연속한 원자 몇 개를 말한다.

어제 또 한 번 실험이 진행되었다. 실험 전에 각 원자에 전하를 지정했는데, $i$번 원자에 전하 $q_i$를 지정했다.

실험 동안 과학자들은 두 종류의 동작을 수행했다.

• 번호가 $l_i$부터 $r_i$까지인 모든 원자의 전하를 $d_i$만큼 바꾼다.
• 번호가 $l_i$부터 $r_i$까지인 원자를 연결하는 강한 결합을 제외한 모든 강한 결합을 일시적으로 끊고, 남은 강한 결합 중 가장 긴 원자 사슬의 길이를 잰다. 그런 다음 일시적으로 끊었던 결합을 모두 복구한다.

동작은 $m$번 수행되었지만, 실험의 부작용으로 측정 결과 기록이 유실되었다는 사실이 밝혀졌다. 흑연 나노막대 연구를 이어가려면 어제의 측정 결과를 복구해야 한다. 다행히 실험 동안 수행한 동작 계획은 남아 있다. 과학자들의 연구를 도와 측정 결과를 복구하자.

첫째 줄에 나노막대의 원자 수 $n$이 주어진다 ($1 \le n \le 100\,000$). 둘째 줄에 $i$번 원자의 초기 전하 $q_i$가 $n$개 주어진다 ($|q_i| \le 10^9$). 셋째 줄에 실험의 동작 수 $m$이 주어진다 ($0 \le m \le 100\,000$). 다음 $m$개 줄에 실험이 주어진다.

줄이 <<+>> 기호로 시작하면 원자 전하를 바꾸는 동작이다. 이때 같은 줄에 이 동작을 나타내는 정수 $l_i$, $r_i$, $d_i$가 주어진다 ($1 \le l_i \le r_i \le n$, $|d_i| \le 10^9$).

줄이 <<?>> 기호로 시작하면 두 번째 종류의 동작이다. 이때 같은 줄에 이 동작을 나타내는 정수 $l_i$, $r_i$가 주어진다 ($1 \le l_i \le r_i \le n$).

두 번째 종류의 동작마다 가장 긴 원자 사슬의 길이를 한 줄에 하나씩 출력한다.

예시 그림. 점선은 두 번째 종류의 동작 동안 끊기는 강한 결합을 나타낸다. 각 두 번째 종류의 동작마다 질의 구간과 가장 긴 원자 사슬이 표시되어 있다.