#include<bits/stdc++.h>

 using namespace std;

 #define inf 0x3f3f3f3f

 struct Edge

 {

     int to,w,next;

 }e[];

 int cnt,first[],c[];

 void add(int u,int v,int w)

 {

     e[cnt].to=v;

     e[cnt].w=w;

     e[cnt].next=first[u];

     first[u]=cnt++;

 }

 int d[];

 bool spfa(int N)

 {

     int inq[];

     bool vis[];

     queue<int>Q;

     memset(vis,,sizeof(vis));

     memset(inq,,sizeof(inq));

     memset(d,inf,sizeof(d));

     Q.push();

     vis[]=inq[]=;

     d[]=;

     while(!Q.empty()){

         int u=Q.front(); Q.pop();

         vis[u]=;

         for(int i=first[u];i+;i=e[i].next){

             Edge x=e[i];

             if(inq[x.to]>N) continue;

             if(d[x.to]>d[u]+x.w){

                 d[x.to]=d[u]+x.w;

                 if(!vis[x.to]){

                     Q.push(x.to);

                     inq[x.to]++;

                 }

             }

         }

     }

     return ;

 }

 int main()

 {

     int T,N,M,Q,i,j,k=;

     int u,v,w;

     cin>>T;

     while(T--){cnt=;

         memset(first,-,sizeof(first));

         cin>>N;

         for(i=;i<=N;++i) cin>>c[i];

         cin>>M;

         while(M--){

             cin>>u>>v;

             add(u,v,(c[v]-c[u])*(c[v]-c[u])*(c[v]-c[u]));

         }

         cin>>Q;

         printf("Case %d:\n",++k);

         bool ok=spfa(N);

         while(Q--){

             cin>>u;

             if(d[u]<||d[u]==inf) puts("?");

             else cout<<d[u]<<endl;

         }

     }

     return ;

 }