31879번 - 바이러스 시뮬레이터

문제

2123년 봄, 드디어 '바이러스 시뮬레이터'가 출시되었다.

바이러스 시뮬레이터는 사람들의 면역력과 바이러스의 생명력 등을 설정하여 직접 시뮬레이션을 진행하는 프로그램으로, 훗날 바이러스가 창궐할 때를 대비하여 만든 프로그램이다.

이 시뮬레이터에는 초기에 $N$명의 사람들이 1ドル$번부터 $N$번까지 번호 순서대로 배치되어 있고, $i$번째 사람의 면역력은 $A_i$이다.

여기에 한 번 이상의 행동을 할 수 있으며, 행동의 종류는 바이러스 침투, 백신 접종, 그룹 면역력 측정 총 3가지가 있다. 각 행동은 입력으로 아래와 같이 주어진다.

• 1ドル$ $i$ $x$: 바이러스 침투 - 생명력이 $x$인 바이러스가 $i$번 사람에게 침투한다. 바이러스는 생명력을 1ドル$만큼 소모하여 감염자의 면역력을 1ドル$ 감소시킨다. 이때 침투한 바이러스가 죽기 전에 감염자의 면역력이 없거나(즉, 면역력이 0ドル$이거나) 없어지게 된다면, 바이러스는 현재 위치한 감염자의 번호보다 큰 번호를 가진 사람 중 가장 면역력이 높은 사람에게 전이되며, 생명력이 0ドル$이 되어 죽거나 더 이상 전이될 사람이 없을 때까지 반복된다. 전이 조건과 일치하는 사람이 여러 명일 경우, 그중 번호가 가장 작은 사람에게 전이된다. $(1 \le i \le N;1 \le x \le 10^{9})$
• 2ドル$ $i$ $x$: 백신 접종 - $i$번 사람에게 효력이 $x$인 백신을 접종하여 면역력이 $x$만큼 오른다. $(1 \le i \le N;1 \le x \le 10^{9})$
• 3ドル$ $l$ $r$: 그룹 면역력 측정 - $l$번부터 $r$번까지의 사람들이 그룹을 형성한다. 그룹은 인접한 사람들끼리 구성할 수 있고, 면역력이 없는 사람들은 없는 사람들끼리, 있는 사람들은 있는 사람들끼리 그룹을 만든다. 이때 구성되는 그룹 중, 그룹 구성원의 면역력의 합의 최댓값을 구한다. $(1 \le l \le r \le N)$

사람의 수 $N$과 $Q$번의 행동 목록이 주어지면, 시뮬레이터를 실행했을 때의 결과를 직접 출력해 보자.

행동은 행동 목록 순서대로 수행되며, 한 번의 행동이 완료될 때까지 그 다음 행동이 수행되지 않는다.

입력

첫 번째 줄에 사람들의 수 $N$과 행동의 횟수 $Q$를 나타내는 두 정수가 공백을 사이에 두고 주어진다. $(1 \le N, Q \le 200,000円)$

두 번째 줄에 각 사람의 면역력을 나타내는 $N$개의 정수 $A_i$가 공백을 사이에 두고 주어진다. $(1 \le A_i \le 10^{9})$

세 번째 줄부터 $Q$개의 줄에 걸쳐 행동 목록이 주어진다.

그룹 면역력 측정 행동이 최소 한 번 이상 주어진다.

출력

그룹 면역력 측정 행동이 주어질 때마다, 그 결과를 한 줄에 하나씩 출력한다.

제한

힌트