模拟

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<string,int> pp;

int n,m,t;
string ans,xx,yy;

string get(char w)
{
    string tmp="";
    if(w=='0')
        tmp += "0000";
    if(w=='1')
        tmp += "0001";
    if(w=='2')
        tmp += "0010";
    if(w=='3')
        tmp += "0011";
    if(w=='4')
        tmp += "0100";
    if(w=='5')
        tmp += "0101";
    if(w=='6')
        tmp += "0110";
    if(w=='7')
        tmp += "0111";
    if(w=='8')
        tmp += "1000";
    if(w=='9')
        tmp += "1001";
    if(w=='a')
        tmp += "1010";
    if(w=='b')
        tmp += "1011";
    if(w=='c')
        tmp += "1100";
    if(w=='d')
        tmp += "1101";
    if(w=='e')
        tmp += "1110";
    if(w=='f')
        tmp += "1111";
    if(w=='A')
        tmp += "1010";
    if(w=='B')
        tmp += "1011";
    if(w=='C')
        tmp += "1100";
    if(w=='D')
        tmp += "1101";
    if(w=='E')
        tmp += "1110";
    if(w=='F')
        tmp += "1111";
    return tmp;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        ans="";
        scanf("%d%d",&m,&n);
        pp.clear();
        int y;
        for(int i=1; i<=n; i++)
        {
            string x;
            cin>>y>>x;
            pp[x]=y;
        }
        string ss;
        cin>>ss;
        ans="";
        for(int i=0; i<ss.size(); i++)
        ans+=get(ss[i]);

        //cout<<ans.size()<<endl;

        int cnt = 0; xx=""; yy="";
        while(1)
        {
            if(xx.size()<=8)
            {
                if(cnt==ans.size())break;
                xx+=ans[cnt],cnt++;
            }
            else
            {
                int tot=0;
                for(int i=0; i<8; i++)
                {
                    if(xx[i]=='1')
                    tot++;
                }
                if((tot%2==1&&xx[8]=='0'))
                {
                    xx.pop_back();
                    yy+=xx;
                }
                else if((tot%2==0&&xx[8]=='1'))
                {
                    xx.pop_back();
                    yy+=xx;
                }
                xx.clear();
            }
        }
        //cout<<yy.size()<<endl;

        string rr="";
        string tt="";
        for(int i=0;i<yy.size();i++)
        {
            if(tt=="")
            {
                tt+=yy[i];
            }
            else if(pp.count(tt)==0)
            {
                tt+=yy[i];
            }
            else
            {
                rr+=(char)pp[tt];
                if(rr.size()>=m) break;
                tt.clear();
                tt+=yy[i];
            }
        }
        if(rr.size()<m)
        rr+=pp[tt];

        cout<<rr<<endl;
    }


}