// 题目描述：
一个项目被分成几个部分，每部分必须在连续的天数完成。也就是说，如果某部分需要3天
才能完成，则必须花费连续的3天来完成它。对项目的这些部分工作中，
有4种类型的约束：FAS, FAF, SAF和SAS。两部分工作之间存在一个
FAS约束的含义是：第一部分工作必须在第二部分工作开始之后完成； Xa+Ta>=Xb
FAF约束的含义是：第一部分工作必须在第二部分工作完成之后完成； Xa+Ta>=Xb+Tb
SAF的含义是：第一部分工作必须在第二部分工作完成之后开始； Xa>=Xb+Tb
SAS的含义是：第一部分工作必须在第二部分工作开始之后开始。 Xa>=Xb
假定参与项目的人数足够多，也就是说可以同时作任意多的部分工作。
你的任务是编写程序，对给定的项目设计一个进度表，使得项目完成时间最短。
// 由上面的4条建立不等式建边 Xi表示i开始的时间
// 然后新建一个点 0 ，表示在所有任务完成后开始的点 那么有 X0>=Xi+T[i]
#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 1010
struct 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){ // s表示起点 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]++; //printf("%d ",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);
}
}
}
}
// printf("
");
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];// printf("a=%d b=%d %d ",a,b,E[num].val);
E[num].next=V[a];
V[a]=num++;
}else if(strcmp(str,"SAF")==0){
E[num].to=b;
E[num].val=-T[b];// printf("a=%d b=%d %d ",a,b,E[num].val);
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;
// printf("%s
",str);
add(str,i,j);
}
}
for(i=1;i<=n;i++){
//if(in[i])continue;
E[num].to=i;
E[num].val=-T[i];
E[num].next=V[0];
V[0]=num++;
}
int Min=MOD;
printf("Case %d:
",Case++);
if(!sfpa(0,n+1))
printf("impossible
");
else{
for(i=1;i<=n;i++)
Min=min(Min,d[i]);//,printf("%d ",d[i]);
// if(Min==MOD){printf("impossible
"); continue;}
for(i=1;i<=n;i++)
printf("%d %d
",i,d[i]-Min);
}
printf("
");
}
}