#388 A × B (HARD)

Statement

Statement language

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$ : Among the values currently present in slots through , print the product of the maximum and minimum values. If every slot in the range is empty, print nothing.

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

Input

The input is given in the following format.

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

Output

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.

Constraints

$1 \leq T \leq 100\,000$ .
$1 \leq N \leq 100\,000$ .
$1 \leq M$ .

Subtasks

#	Score	Constraints
1	27	The sum of $N$ over all test cases does not exceed $2\,000$ . The sum of $M$ over all test cases does not exceed $5\,000$ .
2	23	Every query is of type `1` or type `2`.

Samples

Input

Output

For the third type 2 query of the first test case, both slots $4$ and $5$ are empty, so nothing is printed.