#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    vector<queue<ll>>que(3);

    vector<string>S(3);
    rep(i,3){
        char c;
        cin>>S[i];
        rep(j,S[i].size()){
            que[i].push(S[i][j]-'a');
        }
       // cout<<que[i].size()<<endl;
    }
    

    ll now=que[0].front();
    que[0].pop();
    while(1){
        //cout<<now<<" "<<que[now].size()<<endl;
        if(que[now].empty()){
            cout<<(char)(now+'A')<<endl;
            return 0;
        }else{
            //cout<<now<<endl;
            ll tmp;
            tmp=que[now].front();
            que[now].pop();
            now=tmp;
            
            
        }
    }
    


    return 0;
    

}
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#define M 2100000
using namespace std;	
int main(void)
{
	int i,j,n,k,m,a[3001],b[3001],cost[3001],time[3001],kk,pp,bre;
	int p,q,r;
	int kin[101][101],zi[101][101];
	int flg[10001],leng[10001],min;
	int kaku,skin,szi;
	
	while(1) {
		scanf("%d %d",&n,&m);
		if(n==0 && m==0) break;
		for(i=1;i<=n;i++) scanf("%d %d %d %d",&a[i],&b[i],&cost[i],&time[i]);
		//??£??\????????????  ??????
		for(i=1;i<=m;i++) {
			for(j=1;j<=m;j++) {
				kin[i][j]=M;
			}
		}
		for(i=1;i<=m;i++) kin[i][i]=0;
		for(i=1;i<=n;i++)	kin[a[i]][b[i]]=cost[i];
		for(i=1;i<=n;i++)	kin[b[i]][a[i]]=cost[i];
		//??£??\???????????????
		for(i=1;i<=m;i++) {
			for(j=1;j<=m;j++) {
				zi[i][j]=M;
			}
		}
		for(i=1;i<=m;i++) zi[i][i]=0;
		for(i=1;i<=n;i++) zi[a[i]][b[i]]=time[i];
		for(i=1;i<=n;i++) zi[b[i]][a[i]]=time[i];
		scanf("%d",&k);
		for(i=1;i<=k;i++) {
			scanf("%d %d ",&p,&q);
			scanf("%d",&r);
			for(j=1;j<=m;j++) {
				leng[j]=M;
				flg[j]=0;
			}
			leng[p]=0;
			if(r==0) {
				for(j=1;j<=m;j++) {
					min=M;
					for(kk=1;kk<=m;kk++) {
						if(flg[kk]==0 && leng[kk]<min) {
							kaku=kk;
							min=leng[kk];
						}
					}
					flg[kaku]=1;
					for(kk=1;kk<=m;kk++) {
						if((leng[kaku]+kin[kaku][kk])<leng[kk]) leng[kk]=leng[kaku]+kin[kaku][kk];
					}
				}
				printf("%d\n",leng[q]);
			}
			else {
				for(j=1;j<=m;j++) {
					min=M;
					for(kk=1;kk<=m;kk++) {
						if(flg[kk]==0 && leng[kk]<min) {
							kaku=kk;
							min=leng[kk];
						}
					}
					flg[kaku]=1;
					for(kk=1;kk<=m;kk++) {
						if((leng[kaku]+zi[kaku][kk])<leng[kk]) leng[kk]=leng[kaku]+zi[kaku][kk];
					}
				}
				printf("%d\n",leng[q]);
			}
		}
		/*
			//cost
		printf("??????\n");
		printf("      ");
		for(i=1;i<=m;i++) printf("%7d ",i);
		printf("\n");
		printf("\n");
		for(i=1;i<=m;i++) {
			printf("%7d  ",i);
			for(j=1;j<=m;j++) {
				printf("%7d ",kin[i][j]);
			}
			printf("\n");
		}
		printf("\n");
		printf("\n");
		//time
		printf("??????\n");
		printf("      ");
		for(i=1;i<=m;i++) printf("%7d ",i);
		printf("\n");
		printf("\n");
		for(i=1;i<=m;i++) {
			printf("%7d  ",i);
			for(j=1;j<=m;j++) {
				printf("%7d ",zi[i][j]);
			}
			printf("\n");
		}
		printf("\n");*/
	}
		return 0;
}
	