A × B (HARD)

Alpaca manages $N$ slots numbered from $1$ to $N$. Initially, every slot contains one integer, and slot $i$ contains $A_i$.

Process the following queries.

• 1 $k$ $v$: Set the value in slot $k$ to $v$. If the slot is empty, insert $v$ into it.
• 2 $s$ $e$: Among the values currently present in slots $s$ through $e$, print the product of the maximum and minimum values. If every slot in the range is empty, print nothing.
• 3 $k$: Delete the value in slot $k$. If the slot is already empty, do nothing.

Deleting a value does not change the indices of any other value. Process all queries in order.

The input is given in the following format.

$T$ case$_1$ case$_2$ $\vdots$ case$_T$

Each case is given in the following format.

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

Each query has one of the following forms.

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

For every type 2 query in every test case, if the queried range contains at least one value, print the product of its maximum and minimum values on its own line.

If every slot in the queried range is empty, print nothing for that query.

• $1 \leq T \leq 100\,000$.
• $1 \leq N \leq 100\,000$.
• $1 \leq M \leq 300\,000$.
• $-10^9 \leq A_i \leq 10^9$ ($1 \leq i \leq N$).
• In a type 1 query, $1 \leq k \leq N$ and $-10^9 \leq v \leq 10^9$.
• In a type 2 query, $1 \leq s \leq e \leq N$.
• In a type 3 query, $1 \leq k \leq N$.
• The sum of $N$ over all test cases does not exceed $100\,000$.
• The sum of $M$ over all test cases does not exceed $300\,000$.