#include <bits/stdc++.h>
using namespace std;
// start policy based data structures
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// end policy based data structures
// start debugging helpers
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
const char *comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << "\t|";
__f(comma + 1, args...);
}
#define print(x) \
for (auto it : x) \
cout << it << ' '; \
cout << '\n';
// end debugging helpers
#define all(x) x.begin(), x.end()
#define mem1(a) memset(a, -1, sizeof(a))
#define mem0(a) memset(a, 0, sizeof(a))
#define int long long
// typedef long long ll;
typedef unsigned long long ull;
const int N = 505;
int times[N];
int in[N];
vector<int> adj[N];
int do_magic(int node, int priority) {
// calculate indegree
mem0(in);
for (int i = 0; i < N; i++)
for (auto kid : adj[i])
in[kid]++;
// add all nodes with indegree 0 to the queue
priority_queue<pair<int, int>> q;
for (int i = 0; i < N; i++) {
if (in[i] > 0) continue;
if (i == node) q.push({priority, i});
else q.push({0, i});
}
// process queue
int total_time = 0;
while (!q.empty()) {
auto top = q.top();
q.pop();
int cur_node = top.second;
if (cur_node == node) {
return total_time;
}
total_time += times[cur_node];
// relax edges
for (auto kid : adj[cur_node]) {
in[kid]--;
if (!in[kid]) {
if (kid == node) q.push({priority, kid});
else q.push({0, kid});
}
}
}
return total_time;
}
void solve(int V, int E, int case_num) {
//reset
mem0(times);
for (auto v : adj) v.clear();
for (int i = 1; i <= V; i++) cin >> times[i];
for (int i = 0; i < E; i++) {
int x, y;
cin >> x >> y;
adj[x].push_back(y);
}
int Q;
cin >> Q;
vector<int> queries(Q);
for (int i = 0; i < Q; i++) {
cin >> queries[i];
}
cout << "Case #" << case_num << ":\n";
for (int i = 0; i < Q; i++) {
int mini = do_magic(queries[i], INT_MAX);
int maxi = do_magic(queries[i], INT_MIN);
cout << (maxi - mini) << '\n';
}
cout << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;
// while (t--) solve();
int V, E, case_num = 1;
while (cin >> V >> E) {
if (!V) break;
solve(V, E, case_num);
case_num++;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyBzdGFydCBwb2xpY3kgYmFzZWQgZGF0YSBzdHJ1Y3R1cmVzCiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+Cgp1c2luZyBuYW1lc3BhY2UgX19nbnVfcGJkczsKCnRlbXBsYXRlIDxjbGFzcyBUPgp1c2luZyBUcmVlID0gdHJlZTxULCBudWxsX3R5cGUsIGxlc3M8VD4sIHJiX3RyZWVfdGFnLCB0cmVlX29yZGVyX3N0YXRpc3RpY3Nfbm9kZV91cGRhdGU+OwovLyBlbmQgcG9saWN5IGJhc2VkIGRhdGEgc3RydWN0dXJlcwoKLy8gc3RhcnQgZGVidWdnaW5nIGhlbHBlcnMKI2lmZGVmIExPQ0FMCiNkZWZpbmUgdHJhY2UoLi4uKSBfX2YoI19fVkFfQVJHU19fLCBfX1ZBX0FSR1NfXykKI2Vsc2UKI2RlZmluZSB0cmFjZSguLi4pIDQyCiNlbmRpZgp0ZW1wbGF0ZSA8dHlwZW5hbWUgQXJnMT4Kdm9pZCBfX2YoY29uc3QgY2hhciAqbmFtZSwgQXJnMSAmJmFyZzEpIHsKICAgIGNlcnIgPDwgbmFtZSA8PCAiOiAiIDw8IGFyZzEgPDwgZW5kbDsKfQp0ZW1wbGF0ZSA8dHlwZW5hbWUgQXJnMSwgdHlwZW5hbWUuLi4gQXJncz4Kdm9pZCBfX2YoY29uc3QgY2hhciAqbmFtZXMsIEFyZzEgJiZhcmcxLCBBcmdzICYmLi4uIGFyZ3MpIHsKICAgIGNvbnN0IGNoYXIgKmNvbW1hID0gc3RyY2hyKG5hbWVzICsgMSwgJywnKTsKICAgIGNlcnIud3JpdGUobmFtZXMsIGNvbW1hIC0gbmFtZXMpIDw8ICI6ICIgPDwgYXJnMSA8PCAiXHR8IjsKICAgIF9fZihjb21tYSArIDEsIGFyZ3MuLi4pOwp9CgojZGVmaW5lIHByaW50KHgpICAgICAgICAgICBcCiAgICBmb3IgKGF1dG8gaXQgOiB4KSAgICAgIFwKICAgICAgICBjb3V0IDw8IGl0IDw8ICcgJzsgXAogICAgY291dCA8PCAnXG4nOwovLyBlbmQgZGVidWdnaW5nIGhlbHBlcnMKCiNkZWZpbmUgYWxsKHgpIHguYmVnaW4oKSwgeC5lbmQoKQojZGVmaW5lIG1lbTEoYSkgbWVtc2V0KGEsIC0xLCBzaXplb2YoYSkpCiNkZWZpbmUgbWVtMChhKSBtZW1zZXQoYSwgMCwgc2l6ZW9mKGEpKQojZGVmaW5lIGludCBsb25nIGxvbmcKCi8vIHR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIHVuc2lnbmVkIGxvbmcgbG9uZyB1bGw7CmNvbnN0IGludCBOID0gNTA1OwppbnQgdGltZXNbTl07CmludCBpbltOXTsKdmVjdG9yPGludD4gYWRqW05dOwoKaW50IGRvX21hZ2ljKGludCBub2RlLCBpbnQgcHJpb3JpdHkpIHsKICAgIC8vIGNhbGN1bGF0ZSBpbmRlZ3JlZQogICAgbWVtMChpbik7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IE47IGkrKykKICAgICAgICBmb3IgKGF1dG8ga2lkIDogYWRqW2ldKQogICAgICAgICAgICBpbltraWRdKys7CgogICAgLy8gYWRkIGFsbCBub2RlcyB3aXRoIGluZGVncmVlIDAgdG8gdGhlIHF1ZXVlCiAgICBwcmlvcml0eV9xdWV1ZTxwYWlyPGludCwgaW50Pj4gcTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgTjsgaSsrKSB7CiAgICAgICAgaWYgKGluW2ldID4gMCkgY29udGludWU7CiAgICAgICAgaWYgKGkgPT0gbm9kZSkgcS5wdXNoKHtwcmlvcml0eSwgaX0pOwogICAgICAgIGVsc2UgcS5wdXNoKHswLCBpfSk7CiAgICB9CgogICAgLy8gcHJvY2VzcyBxdWV1ZQogICAgaW50IHRvdGFsX3RpbWUgPSAwOwogICAgd2hpbGUgKCFxLmVtcHR5KCkpIHsKICAgICAgICBhdXRvIHRvcCA9IHEudG9wKCk7CiAgICAgICAgcS5wb3AoKTsKICAgICAgICBpbnQgY3VyX25vZGUgPSB0b3Auc2Vjb25kOwogICAgICAgIGlmIChjdXJfbm9kZSA9PSBub2RlKSB7CiAgICAgICAgICAgIHJldHVybiB0b3RhbF90aW1lOwogICAgICAgIH0KICAgICAgICB0b3RhbF90aW1lICs9IHRpbWVzW2N1cl9ub2RlXTsKICAgICAgICAvLyByZWxheCBlZGdlcwogICAgICAgIGZvciAoYXV0byBraWQgOiBhZGpbY3VyX25vZGVdKSB7CiAgICAgICAgICAgIGluW2tpZF0tLTsKICAgICAgICAgICAgaWYgKCFpbltraWRdKSB7CiAgICAgICAgICAgICAgICBpZiAoa2lkID09IG5vZGUpIHEucHVzaCh7cHJpb3JpdHksIGtpZH0pOwogICAgICAgICAgICAgICAgZWxzZSBxLnB1c2goezAsIGtpZH0pOwogICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAKICAgICAgICB9CiAgICB9ICAgIAogICAgcmV0dXJuIHRvdGFsX3RpbWU7Cn0KCnZvaWQgc29sdmUoaW50IFYsIGludCBFLCBpbnQgY2FzZV9udW0pIHsKICAgIC8vcmVzZXQKICAgIG1lbTAodGltZXMpOwogICAgZm9yIChhdXRvIHYgOiBhZGopIHYuY2xlYXIoKTsKCiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBWOyBpKyspIGNpbiA+PiB0aW1lc1tpXTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgRTsgaSsrKSB7CiAgICAgICAgaW50IHgsIHk7CiAgICAgICAgY2luID4+IHggPj4geTsKICAgICAgICBhZGpbeF0ucHVzaF9iYWNrKHkpOwogICAgfQogICAgaW50IFE7CiAgICBjaW4gPj4gUTsKICAgIHZlY3RvcjxpbnQ+IHF1ZXJpZXMoUSk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IFE7IGkrKykgewogICAgICAgIGNpbiA+PiBxdWVyaWVzW2ldOwogICAgfQogICAgY291dCA8PCAiQ2FzZSAjIiA8PCBjYXNlX251bSA8PCAiOlxuIjsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgUTsgaSsrKSB7ICAgICAgICAKICAgICAgICBpbnQgbWluaSA9IGRvX21hZ2ljKHF1ZXJpZXNbaV0sIElOVF9NQVgpOwogICAgICAgIGludCBtYXhpID0gZG9fbWFnaWMocXVlcmllc1tpXSwgSU5UX01JTik7CiAgICAgICAgY291dCA8PCAobWF4aSAtIG1pbmkpIDw8ICdcbic7CiAgICB9CiAgICBjb3V0IDw8ICdcbic7Cn0KCnNpZ25lZCBtYWluKCkgewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgY2luLnRpZSgwKTsKICAgIGludCB0ID0gMTsKICAgIC8vIGNpbiA+PiB0OwogICAgLy8gd2hpbGUgKHQtLSkgc29sdmUoKTsKICAgIGludCBWLCBFLCBjYXNlX251bSA9IDE7CiAgICB3aGlsZSAoY2luID4+IFYgPj4gRSkgewogICAgICAgIGlmICghVikgYnJlYWs7CiAgICAgICAgc29sdmUoViwgRSwgY2FzZV9udW0pOwogICAgICAgIGNhc2VfbnVtKys7CiAgICB9CiAgICByZXR1cm4gMDsKfQ==