#include <bits/stdc++.h>

 using namespace std;

 struct Node

 {

     Node *ch[];

     int r;  //优先级

     int v;  //值

     int s;  //结点总数

     Node(int v):v(v)

     {

         ch[] = ch[] = NULL;

         r = rand();

         s = ;

     }

     bool operator < (const Node& rhs) const

     {

         return r < rhs.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;

     }

 };

 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 = ;

         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[];

         }

     }

     else

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

     if(o!=NULL) o->maintain();

 }

 const int maxc =  + ;

 struct Command

 {

     char type;

     int x,p;

 } commands[maxc];

 const int maxn =  + ;

 const int maxm =  + ;

 int n,m;

 int weight[maxn],from[maxm],to[maxm],removed[maxm];

 int pa[maxn];

 int findset(int x)

 {

     return pa[x]!=x ? pa[x] = findset(pa[x]):x;

 }

 Node* root[maxn];   //Treap

 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-);

 }

 void mergeto(Node* &src,Node* &dest)

 {

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

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

     insert(dest,src->v);

     delete src;

     src = NULL;

 }

 void removetree(Node* &x)

 {

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

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

     delete x;

     x = NULL;

 }

 void add_edge(int x)

 {

     int u = findset(from[x]),v=findset(to[x]);

     if(u!=v)

     {

         if(root[u]->s < root[v]->s)

         {

             pa[u] = v;

             mergeto(root[u],root[v]);

         }

         else

         {

             pa[v] = u;

             mergeto(root[v],root[u]);

         }

     }

 }

 int query_cnt;

 long long query_tot;

 void query(int x,int k)

 {

     query_cnt++;

     query_tot +=kth(root[findset(x)],k);

 }

 void change_weight(int x,int v)

 {

     int u = findset(x);

     remove(root[u],weight[x]);

     insert(root[u],v);

     weight[x] = v;

 }

 int main()

 {

     int kase = ;

     while(scanf("%d%d",&n,&m)==&&n)

     {

         for(int i=; i<=n; i++)

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

         for(int i=; i<=m; i++)

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

         memset(removed,,sizeof(removed));

         int c = ;

         for(;;)

         {

             char type;

             int x,p=,v = ;

             scanf(" %c",&type);

             if(type=='E') break;

             scanf("%d",&x);

             if(type=='D') removed[x]= ;    //删掉的边

             if(type=='Q') scanf("%d",&p);

             if(type=='C')

             {

                 scanf("%d",&v);

                 p = weight[x];

                 weight[x] = v;

             }

             commands[c++] = (Command)

             {

                 type,x,p

             };

         }

         //最终的图

         for(int i=; i<=n; i++)

         {

             pa[i] = i;

             if(root[i]!=NULL) removetree(root[i]);

             root[i] = new Node(weight[i]);

         }

         for(int i=; i<=m; i++)

         {

             if(!removed[i]) //id为i这条边没有被删掉

                 add_edge(i);

         }

         query_cnt = query_tot = ;

         for(int i=c-; i>=; i--)

         {

             if(commands[i].type=='D') add_edge(commands[i].x);  //加上边

             if(commands[i].type=='Q') query(commands[i].x,commands[i].p);//第p大

             if(commands[i].type=='C') change_weight(commands[i].x,commands[i].p);

         }

         printf("Case %d: %.6lf\n",++kase,query_tot/(double)query_cnt);

     }

     return ;

 }