24915번 - 센터가 돋보여야 해 서브태스크

나코더 39기 부원인 정후는 2022년 솔대제에 나코더의 무대를 선보이려고 한다. 무대의 이름은 '수열과 쿼리 333'으로, 1 번부터 N 번까지 일렬로 서 있는 학생들이 정후가 만든 Q 가지 동작을 보여 줄 것이다. 각 동작은 두 종류 중 하나이고, 각 학생은 하나의 정수로 나타내어지는 매력을 가지고 있다.

• 첫 번째 종류의 동작은 x_i번 학생의 매력을 y_i로 바꾼다.
• 두 번째 종류의 동작은 l_i번 학생과 r_i번 학생 사이에서 서로 다른 학생 세 명이 나와 무대를 펼친다. 즉, l_i ≤ a < b < c ≤ r_i일 때 a 번, b 번, c 번 학생이 나와 주어진 동작을 마친다.

센터가 가진 매력이 독보적일수록 무대의 매력이 증가한다. i번 학생이 가진 매력을 A_i라고 말할 때 무대의 매력을 A_b - A_a - A_c로 계산한다.

정후는 열심히 준비한 만큼 완벽한 무대가 되기를 바란다. 정후를 위해 각 동작마다 세 명을 골라 무대의 매력의 최댓값을 알려 주자.

첫째 줄에 학생의 수를 나타내는 정수 N과 동작의 수를 나타내는 정수 Q가 공백으로 구분되어 주어진다. 둘째 줄에 N 개의 정수가 공백으로 구분되어 주어진다. i 번째로 주어지는 수는 i 번 학생의 매력 A_i를 나타낸다. 셋째 줄부터 Q + 2째 줄까지 동작의 정보를 나타내는 세 정수가 공백으로 구분되어 주어진다. 각 행의 첫 번째 수는 동작의 종류를 의미한다. 첫 번째 종류의 동작에서는 이어 x_i와 y_i가 주어지고, 두 번째 종류의 동작에서는 이어 l_i와 r_i가 주어진다.

두 번째 종류의 동작이 주어질 때마다 무대의 매력의 최댓값을 한 줄에 하나씩 출력한다.

• 3 ≤ N ≤ 333,333
• 1 ≤ Q ≤ 333,333
• 1 ≤ x_i ≤ N
• -33,333,333 ≤ A_i, y_i ≤ 33,333,333
• 1 ≤ l_i, r_i ≤ N
• l_i + 2 ≤ r_i
• 주어지는 모든 수는 정수이다.
• 두 번째 종류의 동작이 적어도 하나 주어진다.

• N = 3
• Q = 1

• 3 ≤ N ≤ 3,000
• 1 ≤ Q ≤ 3,000

• 초기와 각 쿼리 이후에 i < j이면 A_i ≤ A_j이다.

 추가 제한 조건이 없다.