/*  */

 #include <iostream>

 #include <string>

 #include <map>

 #include <queue>

 #include <set>

 #include <stack>

 #include <vector>

 #include <deque>

 #include <algorithm>

 #include <cstdio>

 #include <cmath>

 #include <ctime>

 #include <cstring>

 #include <climits>

 #include <cctype>

 #include <cassert>

 #include <functional>

 #include <iterator>

 #include <iomanip>

 using namespace std;

 //#pragma comment(linker,"/STACK:102400000,1024000")

 #define sti                set<int>

 #define stpii            set<pair<int, int> >

 #define mpii            map<int,int>

 #define vi                vector<int>

 #define pii                pair<int,int>

 #define vpii            vector<pair<int,int> >

 #define rep(i, a, n)     for (int i=a;i<n;++i)

 #define per(i, a, n)     for (int i=n-1;i>=a;--i)

 #define clr                clear

 #define pb                 push_back

 #define mp                 make_pair

 #define fir                first

 #define sec                second

 #define all(x)             (x).begin(),(x).end()

 #define SZ(x)             ((int)(x).size())

 #define lson            l, mid, rt<<1

 #define rson            mid+1, r, rt<<1|1

 typedef struct {

     char c;

     int x, y;

 } Cmd;

 typedef struct Node {

     Node* ch[];

     int r, v, s;

     Node() {}

     Node(int v_) {

         ch[] = ch[] = NULL;

         r = rand();

         v = v_;

         s = ;

     }

     friend bool operator<(const Node& a, const Node& b) {

         return a.r < b.r;

     }

     int cmp(int x) const {

         if (x == v)    return -;

         return x<v ? :;

     }

     void maintain() {

         s = ;

         if (ch[] != NULL)    s += ch[]->s;

         if (ch[] != NULL)    s += ch[]->s;

     }

 } Node;

 void rotate(Node*& o, int d) {

     Node* k = o->ch[d^];

     o->ch[d^] = k->ch[d];

     k->ch[d] = o;

     o->maintain();

     k->maintain();

     o = k;

 }

 void insert(Node*& o, int x) {

     if (o == NULL) {

         o = new Node(x);

     } else {

         int d = x<o->v ? :;

         insert(o->ch[d], x);

         if (o->ch[d]->r > o->r)

             rotate(o, d^);

     }

     o->maintain();

 }

 void remove(Node*& o, int x) {

     int d = o->cmp(x);

     if (d == -) {

         Node* u = o;

         if (o->ch[]!=NULL && o->ch[]!=NULL) {

             int d2 = o->ch[]->r > o->ch[]->r ? :;

             rotate(o, d2);

             remove(o->ch[d2], x);

         } else {

             if (o->ch[] == NULL)

                 o = o->ch[];

             else

                 o = o->ch[];

             delete u;

         }

     } else {

         remove(o->ch[d], x);

     }

     if (o != NULL)

         o->maintain();

 }

 const int maxc = 5e5+;

 const int maxn = 2e4+;

 const int maxm = 6e4+;

 Cmd cmd[maxc];

 Node* rt[maxn];

 int W[maxn], pre[maxn];

 int U[maxm], V[maxm];

 bool mark[maxm];

 int find(int x) {

     if (x == pre[x])

         return x;

     return pre[x] = find(pre[x]);

 }

 void removetree(Node*& x) {

     if (x->ch[] != NULL)    removetree(x->ch[]);

     if (x->ch[] != NULL)    removetree(x->ch[]);

     delete x;

     x = NULL;

 }

 void mergeto(Node*& src, Node*& des) {

     if (src->ch[] != NULL)    mergeto(src->ch[], des);

     if (src->ch[] != NULL)    mergeto(src->ch[], des);

     insert(des, src->v);

     delete src;

     src = NULL;

 }

 void addEdge(int k) {

     int u = U[k], v = V[k];

     int fu = find(u), fv = find(v);

     if (fu != fv) {

         if (rt[fu]->s < rt[fv]->s) {

             pre[fu] = fv;

             mergeto(rt[fu], rt[fv]);

         } else {

             pre[fv] = fu;

             mergeto(rt[fv], rt[fu]);

         }

     }

 }

 int kth(Node* o, int k) {

     if (o==NULL || k<= || k>o->s)

         return ;

     int s = o->ch[]==NULL ? :o->ch[]->s;

     if (k == s+)

         return o->v;

     else if (k <= s)

         return kth(o->ch[], k);

     else

         return kth(o->ch[], k-s-);

 }

 int main() {

     ios::sync_with_stdio(false);

     #ifndef ONLINE_JUDGE

         freopen("data.in", "r", stdin);

         freopen("data.out", "w", stdout);

     #endif

     int tt = ;

     int n, m, nc;

     int x, y;

     char s[];

     __int64 tot, ans;

     while (scanf("%d %d",&n,&m)!=EOF && (n||m)) {

         rep(i, , n+)

             scanf("%d", &W[i]);

         rep(i, , m+)

             scanf("%d %d", &U[i], &V[i]);

         memset(mark, false, sizeof(mark));

         nc = ;

         while (scanf("%s", s)!=EOF && s[]!='E') {

             cmd[nc].c = s[];

             if (s[] == 'D') {

                 scanf("%d", &x);

                 cmd[nc].x = x;

                 mark[x] = true;

             } else if (s[] == 'Q') {

                 scanf("%d %d", &x, &y);

                 cmd[nc].x = x;

                 cmd[nc].y = y;

             } else if (s[] == 'C') {

                 scanf("%d %d", &x, &y);

                 cmd[nc].x = x;

                 cmd[nc].y = W[x];

                 W[x] = y;

             }

             ++nc;

         }

         rep(i, , n+) {

             pre[i] = i;

             if (rt[i] != NULL)

                 removetree(rt[i]);

             rt[i] = new Node(W[i]);

         }

         rep(i, , m+) {

             if (!mark[i])

                 addEdge(i);

         }

         ans = tot = ;

         per(i, , nc) {

             if (cmd[i].c == 'D') {

                 addEdge(cmd[i].x);

             } else if (cmd[i].c == 'Q') {

                 int fx = find(cmd[i].x);

                 ++tot;

                 ans += kth(rt[fx], cmd[i].y);

             } else if (cmd[i].c == 'C') {

                 int fx = find(cmd[i].x);

                 remove(rt[fx], W[cmd[i].x]);

                 insert(rt[fx], cmd[i].y);

                 W[cmd[i].x] = cmd[i].y;

             }

         }

         printf("Case %d: %.06lf\n", ++tt, 1.0*ans/tot);

     }

     #ifndef ONLINE_JUDGE

         printf("time = %d.\n", (int)clock());

     #endif

     return ;

 }