C. Biggest Field (Hard Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are a farmer and you want to create the biggest field possible to make your farm.

You are given certain side lengths, you need to find what is the largest square field and the largest rectangle field you can make using the side lengths.

You have q queries to answer

  • Type 1: val; Add val to your dataset of side lengths
  • Type 2: val; Remove val from your dataset of side lengths if it is present in your data, else do nothing
  • Type 3: Calculate the biggest square field and biggest rectangle field you can create.

Print $$$-1$$$ if making a particular field is not possible.

A Square field cannot be a Rectangular Field

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 500$$$) — the number of testcases

  • The first line contains two integers $$$n$$$ ($$$1 \leq n \leq 2*10^5$$$) — the size of the array and $$$q$$$ ($$$1 \leq q \leq 2*10^5$$$) — the number of queries
  • The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the initial values of the array.
  • Then comes $$$q$$$ lines, describing the queries
It is guaranteed that the sum of all $$$n + q$$$ across all test cases does not exceed $$$4 * 10^5$$$.
Output

For each type 3 query, print two integers, the biggest square area and biggest rectangle area possible

Example
Input
1
5 9
1 1 2 2 3
3
1 3
3
2 3
2 2
3
2 1
2 1
3
Output
-1 2
-1 6
-1 -1
-1 -1