#388 A × B (HARD)

Statement

알파카는 $1$ 번부터 $N$ 번까지 번호가 매겨진 $N$ 개의 칸을 관리한다. 처음에는 모든 칸에 정수가 하나씩 들어 있으며, $i$ 번 칸의 값은 $A_i$ 이다.

알파카는 다음 세 종류의 쿼리를 처리한다.

1 $k$ $v$ : $k$ 번 칸의 값을 $v$ 로 바꾼다. $k$ 번 칸이 비어 있다면 $v$ 를 새로 넣는다.
2 $s$ $e$ : $s$ 번 칸부터 $e$ 번 칸까지 들어 있는 값의 최댓값과 최솟값을 곱한 값을 출력한다. 해당 구간의 모든 칸이 비어 있다면 아무것도 출력하지 않는다.
3 $k$ : $k$ 번 칸의 값을 삭제하여 빈 칸으로 만든다. 이미 비어 있다면 아무 일도 일어나지 않는다.

값을 삭제해도 다른 값의 번호는 변하지 않는다. 모든 쿼리를 순서대로 처리하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N\ M$ $A_1\ A_2\ \cdots\ A_N$ $\text{query}_1$ $\text{query}_2$ $\vdots$ $\text{query}_M$

각 쿼리는 다음 중 하나의 형식으로 주어진다.

$1\ k\ v$ $2\ s\ e$ $3\ k$

각 테스트 케이스의 2번 쿼리에 대해, 쿼리 구간에 값이 하나 이상 존재한다면 최댓값과 최솟값을 곱한 값을 한 줄에 하나씩 출력한다.

쿼리 구간의 모든 칸이 비어 있다면 그 쿼리에 대해서는 아무것도 출력하지 않는다.

#	Score	Constraints
1	27	모든 테스트 케이스에 대한 $N$ 의 합은 $2\,000$ 이하이다. 모든 테스트 케이스에 대한 $M$ 의 합은 $5\,000$ 이하이다.
2	23	모든 쿼리의 종류는 `1` 또는 `2`이다.
3	50	추가적인 제약이 없다.

Input

Output

첫 번째 테스트 케이스의 세 번째 2번 쿼리에서는 $4$ 번 칸과 $5$ 번 칸이 모두 비어 있으므로 아무것도 출력하지 않는다.