1 #include "iostream"
  2 #include "cstdio"
  3 #include "cstring"
  4 #include "algorithm"
  5 #include "vector"
  6 #include "queue"
  7 #include "cmath"
  8 #include "string"
  9 #include "cctype"
 10 #include "map"
 11 #include "iomanip"
 12 using namespace std;
 13 #define pb push_back
 14 #define mp make_pair
 15 #define fi first
 16 #define se second
 17 #define lc(x) (x << 1)
 18 #define rc(x) (x << 1 | 1)
 19 #define lowbit(x) (x & (-x))
 20 #define ll long long
 21 #define maxn 10050
 22 #define maxm 500000
 23 const int inf = 1 << 29;
 24 struct Edge {
 25     int u, v, cost, next;
 26 } et[maxm];
 27 
 28 int eh[maxn], tot, dist[maxn], cnt[maxn];
 29 bool visit[maxn];
 30 int n, m;
 31 int val[maxn];
 32 int s;
 33 
 34 void init() {
 35     tot = 0;
 36     memset(eh, -1, sizeof (eh));
 37 }
 38 
 39 void addedge(int u, int v, int cost) {
 40     Edge e = {u, v, cost, eh[u]};
 41     et[tot] = e;
 42     eh[u] = tot++;
 43 }
 44 
 45 bool spfa(int s) {
 46     for (int i = 0; i <= n; i++) visit[i] = false, dist[i] = -inf, cnt[i] = 0;
 47     dist[s] = 0, visit[s] = true, cnt[s]++;
 48     queue<int> que;
 49     que.push(s);
 50     while (!que.empty()) {
 51         int u = que.front();
 52         que.pop(), visit[u] = false;
 53         for (int i = eh[u]; i != -1; i = et[i].next) {
 54           int v = et[i].v, cost = et[i].cost;
 55             if (dist[v] < cost + dist[u]) {
 56                 dist[v] = cost + dist[u];
 57                 if (!visit[v]) {
 58                     visit[v] = true;
 59                     que.push(v);
 60                     cnt[v]++;
 61                     if (cnt[v] >= n + 1) return false; 
 62                 }
 63             }
 64         }
 65     }
 66     return true;
 67 }
 68 
 69 int main() {
 70     string s;
 71     int Case = 1;
 72     while(~scanf("%d", &n)) {
 73         if(!n) break;
 74         init();
 75         for(int i = 1; i <= n; i++) {
 76             scanf("%d", &val[i]);
 77             addedge(0, i, 0);
 78         }
 79         addedge(1, 0, 0);
 80         int a, b;
 81         while(1) {
 82             cin >> s;
 83             if(s == "#") break;
 84             scanf("%d%d", &a, &b);
 85             if(s == "SAF") addedge(b, a, val[b]);
 86             else if(s == "FAF") addedge(b, a, val[b] - val[a]);
 87             else if(s == "SAS") addedge(b, a, 0);
 88             else if(s == "FAS") addedge(b, a, -val[a]);
 89         }
 90         printf("Case %d:\n", Case++);
 91         if(spfa(0)) {
 92             for(int i = 1; i <= n; i++) {
 93                 printf("%d %d\n", i, dist[i]);
 94             }
 95         } else printf("impossible\n");
 96         printf("\n");
 97     }
 98     return 0;
 99 }
100