Guess the weight

"'Guess The Weight', It's turn 2. Well let's play this and see what we can draw'"
**Draws "Innervate"**.
"Wow that's lucky for me! All I need to do is to click "'Greater' then getting a free second draw!"
**Sees another "Innervate"**
"Are you sure you want to uninstall Hearthstone from your computer?" "Yes."

uuzlovetree loves playing Hearthstone, and his favorite class is Druid. In Hearthstone, there's a spell for the Druid class called 'Guess the weight,', as shown below.



uuzlovetree knows the number of cards in the deck and knows the mana cost of each card. He wants to know the probability of getting the second card when he plays the 'Guess the weight' under the optimal guessing strategy.

Formally, assume there are currently $m$ cards in the deck, with a number representing mana cost on each card. Now one randomly shuffles all $m$ cards in the deck(each of the $m!$ possible arrangements of the cards appear with equal probability). When one plays the card 'Guess the weight,' he draws the first card of the deck and chooses one of the following two options:

• Predict that the next(second) card of the deck has a smaller mana cost than the first card, then reveal the next card of the deck. If your prediction is correct, you draw the second card.


• Predict that the next(second) card of the deck has a greater mana cost than the first card, then reveal the next card of the deck. If your prediction is correct, you draw the second card.

Caution: If the second card of the deck has equal mana cost with the first card, then no matter which option you choose, you cannot draw the second card of the deck.

Initially, there are $n\geq 2$ cards in the deck, with mana costs $a_1,a_2,\dots,a_n$ , respectively. Now $q$ events happen to the deck(How can those events happen? Try Hearthstone to find out for yourself!), with each event in one of the following two forms:

• Add $x$ cards with mana cost $w$ into the deck.


• Find out when one applies an optimal strategy, what is the maximum probability that he can draw the second card when he plays 'Guess the weight.'

The first line contains a number $T(1\leq T\leq 10)$, denoting the number of test cases.

The first line of each test case contains two numbers $n(2\leq n\leq 2\cdot 10^5)$ and $q(1\leq q\leq 2\cdot 10^5)$, denoting the initial size of the deck, and the number of events, respectively.

Then one line follow, containing $n$ integers $a_1,a_2,\dots,a_n(1\leq a_i\leq 2\cdot 10^5)$, denoting the mana costs of the $n$ initial cards.

Then $q$ lines follow, with each line in one of the two following forms:

• $1\,\,x\,\,w$, denoting that $x$ cards with mana cost $w$ is added into the deck. $(1\leq x\leq 100, 1\leq w\leq 2\cdot 10^5)$.


• $2$, denoting a query that asks, when playing 'Guess the weight' with the current deck, what is the maximum probability that one can draw the second card.

It is guaranteed that $\sum n \leq 10^6$ and $\sum q \leq 10^6$ over all test cases.

For each event of the second type of each test case, output a fraction in the form of $p/q$ in one line, denoting the maximum probability that one can draw the second card. It is required that $p$ and $q$ are both integers and $gcd(p,q)=1$, where $gcd(p,q)$ denotes the greatest common divisor of $p$ and $q$

2
2 5
1 1
2
1 1 2
2
1 1 2
2
2 5
1 2
2
1 1 3
2
1 100 4
2

0/1
2/3
2/3
1/1
5/6
201/3502

For the first test case of the sample, initially, the deck consists of two cards with mana cost 1. So no matter which choice one picks, he cannot draw the second card.

After adding a card with mana cost 2 into the deck, the optimal strategy one can apply is as follows: If the mana cost of the first card drawn is 1, then he predicts that
the next card has a greater cost, otherwise he predicts that the next card has a smaller mana cost. One can certify that under this strategy the probability of drawing
the second card is 2/3.

After adding another card with mana cost 2 into the deck, the optimal strategy doesn't change. One can certify that under this strategy the probability of drawing the
second card is still 2/3.

2021“MINIEYE杯”中国大学生算法设计超级联赛（9）