바이러스 시뮬레이터

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$를 나타내는 두 정수가 공백을 사이에 두고 주어진다. $(1 \le N, Q \le 200\,000)$

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

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

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

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