var
T:array[1..100]of char;
f,l,r:char;
n,p,i,j,len:integer;
begin
for i:=1to 100 do T[i]:='0';
readln(n,p);
   len:=1;
    for i:=1 to n do len:=len*2;
    len:=len-1;
    readln(T[1],T[2],T[3]);
    for i:= 1 to (p-1) do begin
    readln(f,l,r);
     for j:=1 to len do
     if T[j]=f then break;
    T[2*j]:=l;
    T[2*j+1]:=r;
      end;
   for i:=1 to len do write(T[i],' ')
end.