#include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef unsigned long long ull;

 typedef long long ll;

 const int inf = 0x3f3f3f3f;

 const double eps = 1e-;

 const int maxn = 2e4+;

 int n, m, val[maxn];

 int pa[maxn];

 void init()

 {

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

     {

         pa[i] = i;

     }

 }

 int find(int x)

 {

     return pa[x] = (pa[x] == x ? x : find(pa[x]));

 }

 struct Node

 {

     Node* ch[];

     int key, r, siz;

     Node (int x)

     {

         key = x;

         siz = ;

         ch[] = ch[] = NULL;

         r = rand();

     }

     bool operator < (const Node &rhs)const

     {

         return r < rhs.r;

     }

     int cmp(int x)

     {

         if (x == key)

             return -;

         return x < key ?  : ;

     }

     void maintain()

     {

         siz = ;

         if (ch[] != NULL)

             siz += ch[] -> siz;

         if (ch[] != NULL)

             siz += ch[] -> siz;

     }

 };

 void rotate(Node* &root, int d)

 {

     Node* tmp = root -> ch[d^];

     root -> ch[d^] = tmp -> ch[d];

     tmp -> ch[d] = root;

     root -> maintain();

     tmp -> maintain();

     root = tmp;

 }

 void insert(Node* &root, int x)

 {

     if (root == NULL)

         root = new Node (x);

     else

     {

         int d = x < root -> key ?  : ;

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

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

             rotate(root, d^);

     }

     root -> maintain();

 }

 void dele(Node* &root, int x)

 {

     int d = root -> cmp(x);

     if (d == -)

     {

         Node* tmp = root;

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

         {

             int d1 = (root -> ch[] -> r > root -> ch[] -> r ?  : );

             rotate(root, d1^);

             dele(root -> ch[d1^], x);

         }

         else

         {

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

                 root = root -> ch[];

             else

                 root = root -> ch[];

             delete tmp;

         }

     }

     else

         dele(root->ch[d], x);

     if (root != NULL)

         root -> maintain();

 }

 int Get_kth(Node* root, int k)

 {

     if (root == NULL || k <=  || root -> siz < k)

         return ;

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

     if (s +  == k)

         return root -> key;

     if (s +  > k)

         return Get_kth(root -> ch[], k);

     else

         return Get_kth(root -> ch[], k-s-);

 }

 Node* root[maxn];

 void merge_tree(Node* &src, Node* &fa)

 {

     if (src -> ch[] != NULL)

         merge_tree(src -> ch[], fa);

     if (src -> ch[] != NULL)

         merge_tree(src -> ch[], fa);

     insert(fa, src -> key);

     delete src;

     src = NULL;

 }

 void remove_tree(Node* &root)

 {

     if (root -> ch[] != NULL)

         remove_tree(root -> ch[]);

     if (root -> ch[] != NULL)

         remove_tree(root -> ch[]);

     delete root;

     root = NULL;

 }

 struct

 {

     int x, y;

     bool is_del;

 } e[ * maxn];

 struct

 {

     int type, x, p;

 } Q[maxn*];

 void add_edge(int idx)

 {

     int fx = find(e[idx].x);

     int fy = find(e[idx].y);

     if (fx != fy)

     {

         if (root[fx] -> siz > root[fy] -> siz)

         {

             pa[fy] = fx;

             merge_tree(root[fy], root[fx]);

         }

         else

         {

             pa[fx] = fy;

             merge_tree(root[fx], root[fy]);

         }

     }

 }

 int main(void)

 {

 #ifndef ONLINE_JUDGE

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

 #endif

     int cas = ;

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

     {

         if (n ==  && m == )

             break;

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

         {

             scanf ("%d", val +  + i);

         }

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

         {

             scanf ("%d%d", &e[i].x, &e[i].y);

             e[i].is_del = false;

         }

         char op[];

         int tot = ;

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

         {

             if (op[] == 'D')

             {

                 scanf ("%d", &Q[tot].x);

                 Q[tot++].type = ;

                 e[Q[tot-].x].is_del = true;

             }

             if (op[] == 'Q')

             {

                 scanf ("%d%d", &Q[tot].x, &Q[tot].p);

                 Q[tot++].type = ;

             }

             if (op[] == 'C')

             {

                 int v;

                 scanf ("%d%d", &Q[tot].x, &v);

                 Q[tot].p = val[Q[tot].x];

                 val[Q[tot].x] = v;

                 Q[tot++].type = ;

             }

         }

         init();

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

         {

             if (root[i+] != NULL)

                 remove_tree(root[i+]);

             root[i+] = new Node (val[i+]);

         }

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

         {

             if (e[i+].is_del == false)

                 add_edge(i+);

         }

         ll ans1 = , ans2 = ;

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

         {

             if (Q[i].type == )

             {

                 add_edge(Q[i].x);

             }

             if (Q[i].type == )

             {

                 ans1 += Get_kth(root[find(Q[i].x)], Q[i].p);

                 ans2 ++;

             }

             if (Q[i].type == )

             {

                int father = find(Q[i].x);

                 dele (root[father], val[Q[i].x]);

                 insert (root[father], Q[i].p);

                 val[Q[i].x] = Q[i].p;

             }

         }

         printf("Case %d: %.6f\n", cas++, 1.0*ans1 / ans2);

     }

     return ;

 }