3726：Graph and Queries

You 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're also given a sequence of operations and you need to process them as requested. Here's a list of the possible operations that you might encounter:
1)  Deletes an edge from the graph.
The 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.
2)  Queries the weight of the vertex with K-th maximum value among all vertexes currently connected with vertex X (including X itself).
The 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.
3)  Changes the weight of a vertex.
The format is [C X V], where X is an integer from 1 to N, and V is an integer within the range [-10⁶, 10⁶].

The operations end with one single character, E, which indicates that the current case has ended.
For simplicity, you only need to output one real number - the average answer of all queries.

There are multiple test cases in the input file. Each case starts with two integers N and M (1 <= N <= 2 * 10⁴, 0 <= M <= 6 * 10⁴), the number of vertexes in the graph. The next N lines describes the initial weight of each vertex (-106 <= weight[i] <= 10⁶). 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⁵], and there will be no more than 2 * 10⁵ operations that change the values of the vertexes [C X V].

There will be a blank line between two successive cases. A case with N = 0, M = 0 indicates the end of the input file and this case should not be processed by your program.

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.