{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eLATTICE is learning Digital Electronic Technology. He is talented, so he understood all those pieces of knowledge in $10^{-9}$ second. In the next $10^{-9}$ second, he built a data decoding device that decodes data encoded with his special binary coding rule to meaningful words.\u003c/p\u003e\u003cp\u003eHis coding rule is called \"prefix code\", a type of code system (typically a variable-length code) distinguished by its possession of the \"prefix property\", which requires that there is no whole code word in the system that is a prefix (initial segment) of any other code word in the system. Note that his code is composed of only $0$ and $1$.\u003c/p\u003e\u003cp\u003eLATTICE\u0027s device only receives data that perfectly matches LATTICE\u0027s rules, in other words, people who send message to LATTICE will always obey his coding rule. However, in the process of receiving data, there are errors that cannot avoid, so LATTICE uses parity check to detect error bytes, after every $8$-bit data there is $1$ bit called parity bit, which should be \u003ccode\u003e\u00270\u0027\u003c/code\u003e if there are odd number of \u003ccode\u003e\u00271\u0027\u003c/code\u003es in the previous $8$ bits and should be \u003ccode\u003e\u00271\u0027\u003c/code\u003e if there are even number of \u003ccode\u003e\u00271\u0027\u003c/code\u003es. If the parity bit does not meet the fact, then the whole $9$ bits (including the parity bit) should be considered as invalid data and ignored. \u003cstrong\u003eData without parity bit is also considered as invalid data\u003c/strong\u003e. Parity bits will be deleted after the parity check.\u003c/p\u003e\u003cp\u003eFor example, consider the given data \u003ccode\u003e\"101010101010101010101010\"\u003c/code\u003e, it should be divided into $3$ parts:\u003ccode\u003e\"101010101\"\u003c/code\u003e,\u003ccode\u003e\"010101010\"\u003c/code\u003e and \u003ccode\u003e\"101010\"\u003c/code\u003e. For the first part, there are $4$ \u003ccode\u003e\u00271\u0027\u003c/code\u003es in the first $8$ bits, and parity bit is \u003ccode\u003e\u00271\u0027\u003c/code\u003e, so this part passed the check. For the second part, there are $4$ \u003ccode\u003e\u00271\u0027\u003c/code\u003es and parity bit is \u003ccode\u003e\u00270\u0027\u003c/code\u003e, so this part failed the check. For the third part, it has less than $9$ bits so it contains no parity bit, so this part also failed the check. The data after parity check is \u003ccode\u003e\"10101010\"\u003c/code\u003e, which is the first $8$ bits of first part.\u003c/p\u003e\u003cp\u003eData passed the parity check will go into a process that decodes LATTICE\u0027s code. The process is described in the following example: consider a situation that, \u003ccode\u003e\"010\"\u003c/code\u003e represents \u003ccode\u003e\u0027A\u0027\u003c/code\u003e and \u003ccode\u003e\"1011\"\u003c/code\u003e represents \u003ccode\u003e\u0027B\u0027\u003c/code\u003e, if the data after parity check is \u003ccode\u003e\"01010110101011010010\"\u003c/code\u003e, it can be divided into \u003ccode\u003e\"010\"\u003c/code\u003e+\u003ccode\u003e\"1011\"\u003c/code\u003e+\u003ccode\u003e\"010\"\u003c/code\u003e+\u003ccode\u003e\"1011\"\u003c/code\u003e+\u003ccode\u003e\"010\"\u003c/code\u003e+\u003ccode\u003e\"010\"\u003c/code\u003e, which means \u003ccode\u003e\"ABABAA\"\u003c/code\u003e . LATTICE\u0027s device is so exquisite that it can decode all visible characters in the ASCII table .\u003c/p\u003e\u003cp\u003eLATTICE is famous for his Talk show, some reporters have sneaked into his mansion, they stole the data LATTICE to decode in hexadecimal, the coding rule consists of $N$ pairs of corresponding relations from a bit string $S_i$ to an ASCII code $C_i$, and the message length $M$, they want to peek his privacy so they come to you to write a program that decodes messages that LATTICE receives.\u003c/p\u003e\u003ch3\u003eInput\u003c/h3\u003e\u003cp\u003eThe first line an integer $T\\ (T\u0026lt;35)$ represents the number of test cases.\u003c/p\u003e\u003cp\u003eEvery test case starts with one line containing two integers, $M\\ (0\u0026lt;M\\leq100000)$, the number of original characters, and $N\\ (1\\leq N \\leq 256)$, then $N$ lines, every line contains an integer $C_i$, and a string $S_i(0\u0026lt;|S_i|\\leq 10)$, means that $S_i$ \u003cem\u003erepresents\u003c/em\u003e $C_i$, the ASCII code to a visible character and $S_i$ only contains \u003ccode\u003e\u00270\u0027\u003c/code\u003e or \u003ccode\u003e\u00271\u0027\u003c/code\u003e and there are no two numbers $i$ and $j$ that $S_i$ is prefix of $S_j$.\u003c/p\u003e\u003cp\u003eThen one line contains data that is going to be received in hexadecimal. $(0\u0026lt;|data|\u0026lt;200000)$.\u003c/p\u003e\u003ch3\u003eOutput\u003c/h3\u003e\u003cp\u003eFor each test case, output the decoded message in a new line, the length of the decoded message should be the same with the length of original characters, which means you can stop decoding having outputted $M$ characters. Input guarantees that it will have no less than $M$ valid characters and all given ASCII codes represent visible characters.\u003c/p\u003e\u003ch3\u003eHint\u003c/h3\u003e\u003cp\u003eLattice\u0027s encoding rule for test case $2$:\u003c/p\u003e\u003ctable\u003e\u003cthead\u003e\u003ctr\u003e\u003cth\u003eASCII code\u003c/th\u003e\u003cth\u003echaracter\u003c/th\u003e\u003cth\u003elattice\u0027s code\u003c/th\u003e\u003c/tr\u003e\u003c/thead\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd\u003e$49$\u003c/td\u003e\u003ctd\u003e$1$\u003c/td\u003e\u003ctd\u003e$0001$\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e$50$\u003c/td\u003e\u003ctd\u003e$2$\u003c/td\u003e\u003ctd\u003e$01001$\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e$51$\u003c/td\u003e\u003ctd\u003e$3$\u003c/td\u003e\u003ctd\u003e$011$\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003cp\u003ethe device takes this input in hex\u003c/p\u003e\u003cpre\u003e\u003ccode\u003e14DB24722698\u003c/code\u003e\u003c/pre\u003e\u003cp\u003einput in binary\u003c/p\u003e\u003cpre\u003e\u003ccode\u003e0001 0100 1101 1011 0010 0100 0111 0010 0010 0110 1001 1000\u003c/code\u003e\u003c/pre\u003e\u003cp\u003eformatted into $6$ lines, each line contains $8$ data bits and one parity bit\u003c/p\u003e\u003cpre\u003e\u003ccode\u003e00010100 1\n10110110 0\n10010001 1\n10010001 0\n01101001 1\n000\u003c/code\u003e\u003c/pre\u003e\u003cp\u003eparity check of the third line and the last line failed, so ignore those two lines.parity bits should also be ignored.\u003c/p\u003e\u003cpre\u003e\u003ccode\u003e00010100\n10110110\n10010001\n01101001\u003c/code\u003e\u003c/pre\u003e\u003cp\u003earrange those bits by the rules informed\u003c/p\u003e\u003cpre\u003e\u003ccode\u003e0001 01001 011 011 01001 0001 011 01001\u003c/code\u003e\u003c/pre\u003e\u003cp\u003eoutput the result\u003c/p\u003e\u003cpre\u003e\u003ccode\u003e12332132\u003c/code\u003e\u003c/pre\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n15 9\n32 0100\n33 11\n100 1011\n101 0110\n104 1010\n108 00\n111 100\n114 0111\n119 0101\nA6Fd021171c562Fde1\n8 3\n49 0001\n50 01001\n51 011\n14DB24722698\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003ehello world!!!!\n12332132\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}}]}