#include <iostream>#include <map>#include <algorithm>#include <queue>#include <math.h>#include <stdio.h>#include <string.h>#include <vector>using namespace std;#define MOD 1000000007#define maxn 21010#define maxm 1010struct node{ int to; int next; int val;}E[maxn];int num;int in[maxm];int V[maxm];int T[maxm];int d[maxm],cnt[maxm];bool f[maxm];bool sfpa(int s,int n){ queue <int> Q; int u,v; int e; Q.push(s); d[s]=0; f[s]=true; while(!Q.empty()){ u=Q.front(); Q.pop(); cnt[u]++; if(cnt[u]>n) return false; f[u]=false; for(e=V[u];e!=-1;e=E[e].next){ v=E[e].to; if(d[u]+E[e].val<d[v]){ d[v]=d[u]+E[e].val; if(!f[v]) { f[v]=true; Q.push(v); } } } } return true;}void add(char *str,int a,int b){ if(strcmp(str,"FAS")==0){ E[num].to=b; E[num].val=T[a]; E[num].next=V[a]; V[a]=num++; }else if(strcmp(str,"FAF")==0){ E[num].to=b; E[num].val=T[a]-T[b]; E[num].next=V[a]; V[a]=num++; }else if(strcmp(str,"SAF")==0){ E[num].to=b; E[num].val=-T[b]; E[num].next=V[a]; V[a]=num++; }else { E[num].to=b; E[num].val=0; E[num].next=V[a]; V[a]=num++; }}int main(){ int i,j,k; int n; char str[20]; int Case=1; while(scanf("%d",&n),n){ for(i=1;i<=n;i++) { scanf("%d",&T[i]); V[i]=-1; d[i]=MOD; cnt[i]=0; f[i]=false; in[i]=0; } i=0; V[i]=-1; d[i]=MOD; cnt[i]=0; f[i]=false; num=0; while(scanf("%s",str)){ if(strcmp(str,"#")==0) break; else { scanf("%d %d",&i,&j); in[j]=1; add(str,i,j); } } for(i=1;i<=n;i++){ E[num].to=i; E[num].val=-T[i]; E[num].next=V[0]; V[0]=num++; } int Min=MOD; printf("Case %d:n",Case++); if(!sfpa(0,n+1)) printf("impossiblen"); else{ for(i=1;i<=n;i++) Min=min(Min,d[i]); for(i=1;i<=n;i++) printf("%d %dn",i,d[i]-Min); } printf("n"); }}
