#include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <queue>

 #include <vector>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define maxn 210

 #define INF 0x3f3f3f3f

 struct Edge

 {

     int e, w;

     Edge(int e=, int w=):e(e),w(w){}

 };

 vector<Edge>G[maxn];

 int dist[maxn], n;

 bool Cin[maxn];

 void init();

 int spfa ();

 void dfs (int u);

 int main ()

 {

     int m, t, l=, map[maxn];

     scanf ("%d", &t);

     while (t --)

     {

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

         init ();

         scanf ("%d", &n);

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

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

         scanf ("%d", &m);

         while (m --)

         {

             int a, b, num;

             scanf ("%d %d", &b, &a);

             num = (map[a] - map[b]) * (map[a] - map[b]) * (map[a] - map[b]);

             G[b].push_back (Edge(a, num));

         }

         spfa ();

         scanf ("%d", &m);

         while (m --)

         {

             int num;

             scanf ("%d", &num);

             if (Cin[num] || dist[num] <  || dist[num] == INF)

                 printf ("?\n");

             else

                 printf ("%d\n", dist[num]);

         }

     }

 }

 void init()

 {

     int i, j;

     memset (Cin, false, sizeof(Cin));

     for (i=; i<maxn; i++)

     {

         G[i].clear();

         dist[i] = INF;

     }

 }

 int spfa ()

 {

     queue<int>Q;

     bool vis[maxn];

     int cnt[maxn];

     memset (vis, false, sizeof(vis));

     memset (cnt, , sizeof(cnt));

     Q.push ();

     cnt[] = ;

     dist[] = ;

     while (!Q.empty())

     {

         int s = Q.front ();

         Q.pop ();

         vis[s] = false;

         int len = G[s].size();

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

         {

             Edge x = G[s][i];

             if (Cin[x.e])

                 continue;

             if (dist[x.e] > dist[s] + x.w)

             {

                 dist[x.e] = dist[s] + x.w;

                 if (!vis[x.e])

                 {

                     vis[x.e] = true;

                     Q.push (x.e);

                     cnt[x.e] ++;

                     if (cnt[x.e] == n)//只要x.e在负环内，则在负环内的点可以到达的点，都没有最短路径

                         dfs(x.e);

                 }

             }

         }

     }

 }

 void dfs (int u)

 {

     int len = G[u].size();

     Cin[u] = true;

     for (int i=; i<len; i++)//u后面的点都没有最短回路，都应该标记

     {

         if (!Cin[G[u][i].e])

             dfs (G[u][i].e);

     }

 }