1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 100005

 4 struct ji{

 5     int nex,to;

 6 }edge[N<<2];

 7 int E,n,m,flag,x[N],y[N],cx[N],cy[N],head[N<<1],vis[N],a[N],bl[N];

 8 char s1[11],s2[11],s[N];

 9 int id(char c,int p){

10     if (p==c-'a')return -1;

11     return (2*p>3-(c-'a'));

12 }

13 void add(int x,int y){

14     edge[E].nex=head[x];

15     edge[E].to=y;

16     head[x]=E++;

17     if (E&1)add(y+2*n,x);

18 }

19 void dfs1(int k){

20     if (vis[k])return;

21     vis[k]=1;

22     for(int i=head[k];i!=-1;i=edge[i].nex)dfs1(edge[i].to);

23     a[++a[0]]=k;

24 }

25 void dfs2(int k,int s){

26     if (!vis[k])return;

27     vis[k]=0;

28     bl[k]=s;

29     for(int i=head[k];i!=-1;i=edge[i].nex)dfs2(edge[i].to,s);

30 }

31 void dfs(int k){

32     if (flag)return;

33     int nex=n+1;

34     for(int i=n;i>k;i--)

35         if (s[i]=='x')nex=i;

36     if (nex>n){

37         int scc=E=a[0]=0;

38         memset(head,-1,sizeof(head));

39         for(int i=1;i<=m;i++){

40             int xx=id(s[x[i]],cx[i]),yy=id(s[y[i]],cy[i]);

41             if (xx<0)continue;

42             if (yy>=0){

43                 add(2*y[i]+yy-1,2*x[i]+xx-1);

44                 add(2*x[i]+(xx^1)-1,2*y[i]+(yy^1)-1);

45             }

46             else

47                 for(int j=0;j<3;j++)

48                     if (id(s[x[i]],j)==(xx^1))add(2*x[i]+(xx^1)-1,2*x[i]+xx-1);

49         }

50         for(int i=1;i<=n;i++)dfs1(2*i-1);

51         for(int i=1;i<=n;i++)dfs1(2*i);

52         for(int i=1;i<=2*n;i++)head[i]=head[i+2*n];

53         for(int i=2*n;i;i--)dfs2(a[i],++scc);

54         for(int i=1;i<2*n;i+=2)

55             if (bl[i]==bl[i+1])return;

56         flag=1;

57         for(int i=1;i<=n;i++)

58             for(int j=0;j<3;j++)

59                 if (id(s[i],j)==(bl[2*i-1]>bl[2*i]))printf("%c",'A'+j);

60         return;

61     }

62     s[nex]='a';

63     dfs(nex);

64     s[nex]='b';

65     dfs(nex);

66     s[nex]='x';

67 }

68 int main(){

69     scanf("%d%*d%s%d",&n,s+1,&m);

70     for(int i=1;i<=m;i++){

71         scanf("%d%s%d%s",&x[i],s1,&y[i],s2);

72         cx[i]=s1[0]-'A';

73         cy[i]=s2[0]-'A';

74     }

75     dfs(0);

76     if (!flag)printf("-1");

77 }