{"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\"\u003eYou are given an undirected graph with N vertexes and M edges. Every vertex in this graph has an integer value assigned to it at the beginning. You\u0027re also given a sequence of operations and you need to process them as requested. Here\u0027s a list of the possible operations that you might encounter:\u003cbr\u003e1)\u0026nbsp;\u0026nbsp;Deletes an edge from the graph.\u003cbr\u003eThe format is [D X], where X is an integer from 1 to M, indicating the ID of the edge that you should delete. It is guaranteed that no edge will be deleted more than once.\u003cbr\u003e2)\u0026nbsp;\u0026nbsp;Queries the weight of the vertex with K-th maximum value among all vertexes currently connected with vertex X (including X itself).\u003cbr\u003eThe format is [Q X K], where X is an integer from 1 to N, indicating the id of the vertex, and you may assume that K will always fit into a 32-bit signed integer. In case K is illegal, the value for that query will be considered as undefined, and you should return 0 as the answer to that query.\u003cbr\u003e3)\u0026nbsp;\u0026nbsp;Changes the weight of a vertex.\u003cbr\u003eThe format is [C X V], where X is an integer from 1 to N, and V is an integer within the range [-10\u003csup\u003e6\u003c/sup\u003e, 10\u003csup\u003e6\u003c/sup\u003e].\u003cbr\u003e\u003cbr\u003eThe operations end with one single character, E, which indicates that the current case has ended.\u003cbr\u003eFor simplicity, you only need to output one real number - the average answer of all queries.\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"There are multiple test cases in the input file. Each case starts with two integers N and M (1 \u0026lt;\u003d N \u0026lt;\u003d 2 * 10\u003csup\u003e4\u003c/sup\u003e, 0 \u0026lt;\u003d M \u0026lt;\u003d 6 * 10\u003csup\u003e4\u003c/sup\u003e), the number of vertexes in the graph. The next N lines describes the initial weight of each vertex (-106 \u0026lt;\u003d weight[i] \u0026lt;\u003d 10\u003csup\u003e6\u003c/sup\u003e). The next part of each test case describes the edges in the graph at the beginning. Vertexes are numbered from 1 to N. The last part of each test case describes the operations to be performed on the graph. It is guaranteed that the number of query operations [Q X K] in each case will be in the range [1, 2 * 10\u003csup\u003e5\u003c/sup\u003e], and there will be no more than 2 * 10\u003csup\u003e5\u003c/sup\u003e operations that change the values of the vertexes [C X V].\u003cbr\u003e\u003cbr\u003eThere will be a blank line between two successive cases. A case with N \u003d 0, M \u003d 0 indicates the end of the input file and this case should not be processed by your program.\u003cbr\u003e\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output one real number – the average answer of all queries, in the format as indicated in the sample output. Please note that the result is rounded to six decimal places."}},{"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\u003e3 3\r\n10\r\n20\r\n30\r\n1 2\r\n2 3\r\n1 3\r\nD 3\r\nQ 1 2\r\nQ 2 1\r\nD 2\r\nQ 3 2\r\nC 1 50\r\nQ 1 1\r\nE\r\n\r\n3 3\r\n10\r\n20\r\n20\r\n1 2\r\n2 3\r\n1 3\r\nQ 1 1\r\nQ 1 2\r\nQ 1 3\r\nE\r\n\r\n0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 25.000000\r\nCase 2: 16.666667\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":"For the first sample:\u003cbr\u003eD 3 -- deletes the 3rd edge in the graph (the remaining edges are (1, 2) and (2, 3))\u003cbr\u003eQ 1 2 -- finds the vertex with the second largest value among all vertexes connected with 1. The answer is 20.\u003cbr\u003eQ 2 1 -- finds the vertex with the largest value among all vertexes connected with 2. The answer is 30.\u003cbr\u003eD 2 -- deletes the 2nd edge in the graph (the only edge left after this operation is (1, 2))\u003cbr\u003eQ 3 2 -- finds the vertex with the second largest value among all vertexes connected with 3. The answer is 0 (Undefined).\u003cbr\u003eC 1 50 -- changes the value of vertex 1 to 50.\u003cbr\u003eQ 1 1 -- finds the vertex with the largest value among all vertex connected with 1. The answer is 50.\u003cbr\u003eE -- This is the end of the current test case. Four queries have been evaluated, and the answer to this case is (20 + 30 + 0 + 50) / 4 \u003d 25.000.\u003cbr\u003e\u003cbr\u003eFor the second sample, caution about the vertex with same weight:\u003cbr\u003e\u0026nbsp;\u0026nbsp;Q 1 1 – the answer is 20\u003cbr\u003e\u0026nbsp;\u0026nbsp;Q 1 2 – the answer is 20\u003cbr\u003e\u0026nbsp;\u0026nbsp;Q 1 3 – the answer is 10\u003cbr\u003e\u003cbr\u003e"}}]}