{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\u003ci\u003e\"\u0027Guess The Weight\u0027, It\u0027s turn 2. Well let\u0027s play this and see what we can draw\u0027\"\u003c/i\u003e\u003cbr\u003e\u003ci\u003e**Draws \"Innervate\"**.\u003c/i\u003e\u003cbr\u003e\u003ci\u003e\"Wow that\u0027s lucky for me! All I need to do is to click \"\u0027Greater\u0027 then getting a free second draw!\"\u003c/i\u003e\u003cbr\u003e\u003ci\u003e**Sees another \"Innervate\"**\u003c/i\u003e\u003cbr\u003e\u003ci\u003e\"Are you sure you want to uninstall Hearthstone from your computer?\" \"Yes.\"\u003c/i\u003e\u003cbr\u003e\u003cbr\u003euuzlovetree loves playing Hearthstone, and his favorite class is Druid. In Hearthstone, there\u0027s a spell for the Druid class called \u0027Guess the weight,\u0027, as shown below.\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/898ab2d8eea65597c2203c8013d2170a?v\u003d1715598231\"\u003e\u003c/center\u003e\u003cbr\u003e\u003cbr\u003euuzlovetree 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 \u0027Guess the weight\u0027 under the optimal guessing strategy.\u003cbr\u003e\u003cbr\u003eFormally, 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 \u0027Guess the weight,\u0027 he draws the first card of the deck and chooses one of the following two options:\u003cbr\u003e\u003cul\u003e\u003cli\u003ePredict that the next(second) card of the deck has a \u003cb\u003esmaller\u003c/b\u003e mana cost than the first card, then reveal the next card of the deck. If your prediction is correct, you draw the second card.\u003c/li\u003e\u003cbr\u003e\u003cli\u003e Predict that the next(second) card of the deck has a \u003cb\u003egreater\u003c/b\u003e mana cost than the first card, then reveal the next card of the deck. If your prediction is correct, you draw the second card.\u003c/li\u003e\u003c/ul\u003e\u003cbr\u003e\u003cb\u003eCaution: 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.\u003c/b\u003e\u003cbr\u003e\u003cbr\u003eInitially, 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:\u003cbr\u003e\u003cul\u003e\u003cli\u003e Add $x$ cards with mana cost $w$ into the deck. \u003c/li\u003e\u003cbr\u003e\u003cli\u003eFind out when one applies an optimal strategy, what is the maximum probability that he can draw the second card when he plays \u0027Guess the weight.\u0027 \u003c/li\u003e\u003c/ul\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains a number $T(1\\leq T\\leq 10)$, denoting the number of test cases.\u003cbr\u003e\u003cbr\u003eThe 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.\u003cbr\u003e\u003cbr\u003eThen 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.\u003cbr\u003e\u003cbr\u003eThen $q$ lines follow, with each line in one of the two following forms:\u003cbr\u003e\u003cul\u003e\u003cli\u003e $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)$. \u003c/li\u003e\u003cbr\u003e\u003cli\u003e $2$, denoting a query that asks, when playing \u0027Guess the weight\u0027 with the current deck, what is the maximum probability that one can draw the second card. \u003c/li\u003e\u003c/ul\u003e\u003cbr\u003eIt is guaranteed that $\\sum n \\leq 10^6$ and $\\sum q \\leq 10^6$ over all test cases."}},{"title":"Output","value":{"format":"HTML","content":"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)\u003d1$, where $gcd(p,q)$ denotes the greatest common divisor of $p$ and $q$ "}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n2 5\r\n1 1\r\n2\r\n1 1 2\r\n2\r\n1 1 2\r\n2\r\n2 5\r\n1 2\r\n2\r\n1 1 3\r\n2\r\n1 100 4\r\n2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0/1\r\n2/3\r\n2/3\r\n1/1\r\n5/6\r\n201/3502\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eFor 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.\u003cbr\u003e\u003cbr\u003eAfter 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\u003cbr\u003e 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\u003cbr\u003e the second card is 2/3.\u003cbr\u003e\u003cbr\u003eAfter adding another card with mana cost 2 into the deck, the optimal strategy doesn\u0027t change. One can certify that under this strategy the probability of drawing the \u003cbr\u003esecond card is still 2/3.\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e"}}]}