{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eOne day in a forest, Alice found an old monolith.\u003c/p\u003e\n\n\u003cp\u003e\u003cimg src\u003d\"https://static.e-olymp.com/content/6f/6f7718a28bb1b510ac46b0d6976055f0f70ff25b.jpg\" /\u003e\u003c/p\u003e\n\n\u003cp\u003eShe investigated the monolith, and found this was a sentence written in an old language. A sentence consists of glyphs and rectangles which surrounds them. For the above example, there are following glyphs.\u003c/p\u003e\n\n\u003cp\u003e\u003cimg src\u003d\"https://static.e-olymp.com/content/eb/eb01f7e9fdee742fe5ba4cee2697b80909c3fed1.jpg\" /\u003e\u003c/p\u003e\n\n\u003cp\u003eNotice that some glyphs are flipped horizontally in a sentence.\u003c/p\u003e\n\n\u003cp\u003eShe decided to transliterate it using ASCII letters assigning an alphabet to each glyph, and \u0027\u003cstrong\u003e\\[\u003c/strong\u003e\u0027 and \u0027\u003cstrong\u003e\\]\u003c/strong\u003e\u0027 to rectangles. If a sentence contains a flipped glyph, she transliterates it from right to left. For example, she could assign \u0027\u003cstrong\u003ea\u003c/strong\u003e\u0027 and \u0027\u003cstrong\u003eb\u003c/strong\u003e\u0027 to the above glyphs respectively. Then the above sentence would be transliterated into \"\u003cstrong\u003e\\[\\[ab\\]\\[ab\\]a\\]\u003c/strong\u003e\".\u003c/p\u003e\n\n\u003cp\u003eAfter examining the sentence, Alice gured out that the sentence was organized by the following structure:\u003c/p\u003e\n\n\u003cul\u003e\n\u003cp\u003e\u003cli\u003e A sentence \u003cstrong\u003e\\[seq\\]\u003c/strong\u003e is a sequence consists of zero or more \u003cstrong\u003e\\[term\\]\u003c/strong\u003es.\u003c/p\u003e\n\n\u003cp\u003e\u003cli\u003e A term \u003cstrong\u003e\\[term\\]\u003c/strong\u003e is either a glyph or a \u003cstrong\u003e\\[box\\]\u003c/strong\u003e. A glyph may be flipped.\u003c/p\u003e\n\n\u003cp\u003e\u003cli\u003e \u003cstrong\u003e\\[box\\]\u003c/strong\u003e is a rectangle surrounding a \u003cstrong\u003e\\[seq\\]\u003c/strong\u003e. The height of a box is larger than any glyphs inside.\u003c/p\u003e\n\n\u003c/ul\u003e\n\n\u003cp\u003eNow, the sentence written on the monolith is a nonempty \u003cstrong\u003e\\[seq\\]\u003c/strong\u003e. Each term in the sequence fits in a rectangular bounding box, although the boxes are not explicitly indicated for glyphs. Those bounding boxes for adjacent terms have no overlap to each other. Alice formalized the transliteration rules as follows.\u003c/p\u003e\n\n\u003cp\u003eLet \u003cstrong\u003ef\u003c/strong\u003e be the transliterate function.\u003c/p\u003e\n\n\u003cp\u003eEach sequence \u003cstrong\u003es \u003d t_1t_2...t_m\u003c/strong\u003e is written either from left to right, or from right to left. However, please note here \u003cstrong\u003et_1\u003c/strong\u003ecorresponds to the leftmost term in the sentence, \u003cstrong\u003et_2\u003c/strong\u003e to the \u003cstrong\u003e2\u003c/strong\u003end term from the left, and so on.\u003c/p\u003e\n\n\u003cp\u003e\u003cimg src\u003d\"https://static.e-olymp.com/content/dd/ddcddc096af9cafb0f6c97c1d1d73558916df9ab.jpg\" /\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cimg src\u003d\"https://static.e-olymp.com/content/dd/ddcddc096af9cafb0f6c97c1d1d73558916df9ab.jpg\" /\u003e\u003c/p\u003e\n\n\u003cp\u003eLet\u0027s de ne to be the flipped glyph \u003cstrong\u003eg\u003c/strong\u003e. A sequence must have been written from right to left, when a sequence contains one or more single-glyph term which is unreadable without flipping, i.e. there exists an integer \u003cstrong\u003ei\u003c/strong\u003e where \u003cstrong\u003et_i\u003c/strong\u003e is a single glyph \u003cstrong\u003eg\u003c/strong\u003e, and \u003cstrong\u003eg\u003c/strong\u003e is not in the glyph dictionary given separately whereas is. In such cases \u003cstrong\u003ef(s)\u003c/strong\u003e is de ned to be \u003cstrong\u003ef(t_m)f(t_\\{m-1\\\u003c/strong\u003e)...f(t_1)}, otherwise \u003cstrong\u003ef(s) \u003d f(t_1)f(t_2)...f(t_m)\u003c/strong\u003e. It is guaranteed that all the glyphs in the sequence are flipped if there is one or more glyph which is unreadable without flipping.\u003c/p\u003e\n\n\u003cp\u003e\u003cimg src\u003d\"https://static.e-olymp.com/content/dd/ddcddc096af9cafb0f6c97c1d1d73558916df9ab.jpg\" /\u003e\u003c/p\u003e\n\n\u003cp\u003eIf the term \u003cstrong\u003et_i\u003c/strong\u003e is a box enclosing a sequence \u003cstrong\u003es′\u003c/strong\u003e, \u003cstrong\u003ef(t_i) \u003d \u0027\\[\u0027f(s′)\u0027\\]\u0027\u003c/strong\u003e. If the term \u003cstrong\u003et_i\u003c/strong\u003e is a glyph \u003cstrong\u003eg\u003c/strong\u003e, \u003cstrong\u003ef(t_i)\u003c/strong\u003e is mapped to an alphabet letter corresponding to the glyph \u003cstrong\u003eg\u003c/strong\u003e, or if the sequence containing \u003cstrong\u003eg\u003c/strong\u003e is written from right to left.\u003c/p\u003e\n\n\u003cp\u003ePlease make a program to transliterate the sentences on the monoliths to help Alice.\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eInput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eThe input consists of several datasets. The end of the input is denoted by two zeros separated by a single-space.\u003c/p\u003e\n\n\u003cp\u003eEach dataset has the following format.\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003en m\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eglyph_1\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003e...\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eglyph_n\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003estring_1\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003e...\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003estring_m\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003en\u003c/strong\u003e (\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003en\u003c/strong\u003e ≤ \u003cstrong\u003e26\u003c/strong\u003e) is the number of glyphs and \u003cstrong\u003em\u003c/strong\u003e (\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003em\u003c/strong\u003e ≤ \u003cstrong\u003e10\u003c/strong\u003e) is the number of monoliths. \u003cstrong\u003eglyph_i\u003c/strong\u003e is given by the following format.\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003ec h w\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eb_11...b_1w\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003e...\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eb_h1...b_hw\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003ec\u003c/strong\u003e is a lower-case alphabet that Alice assigned to the glyph. \u003cstrong\u003eh\u003c/strong\u003e and \u003cstrong\u003ew\u003c/strong\u003e (\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003eh\u003c/strong\u003e ≤ \u003cstrong\u003e15\u003c/strong\u003e, \u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003ew\u003c/strong\u003e ≤ \u003cstrong\u003e15\u003c/strong\u003e) specify the height and width of the bitmap of the glyph, respectively. The matrix \u003cstrong\u003eb\u003c/strong\u003e indicates the bitmap. A white cell is represented by \u0027\u003cstrong\u003e.\u003c/strong\u003e\u0027 and a black cell is represented by \u0027\u003cstrong\u003e*\u003c/strong\u003e\u0027.\u003c/p\u003e\n\n\u003cp\u003eYou can assume that all the glyphs are assigned distinct characters. You can assume that every column of the bitmap contains at least one black cell, and the rst and last row of the bitmap contains at least one black cell. Every bitmap is different to each other, but it is possible that a flipped bitmap is same to another bitmap. Moreover there may be symmetric bitmaps.\u003c/p\u003e\n\n\u003cp\u003e\u003cimg src\u003d\"https://static.e-olymp.com/content/47/47a62a70775e595f742f4c873564811e89938b84.jpg\" /\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003estring_i\u003c/strong\u003e is given by the following format.\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eh w\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eb_11...b_1w\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003e...\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eb_h1...b_hw\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eh\u003c/strong\u003e and \u003cstrong\u003ew\u003c/strong\u003e (\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003eh\u003c/strong\u003e ≤ \u003cstrong\u003e100\u003c/strong\u003e, \u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003ew\u003c/strong\u003e ≤ \u003cstrong\u003e1000\u003c/strong\u003e) is the height and width of the bitmap of the sequence. Similarly to the glyph dictionary, \u003cstrong\u003eb\u003c/strong\u003e indicates the bitmap where \u003cstrong\u003eA\u003c/strong\u003e white cell is represented by \u0027\u003cstrong\u003e.\u003c/strong\u003e\u0027 and a black cell by \u0027\u003cstrong\u003e*\u003c/strong\u003e\u0027.\u003c/p\u003e\n\n\u003cp\u003eThere is no noise: every black cell in the bitmap belongs to either one glyph or one rectangle box. The height of a rectangle is at least \u003cstrong\u003e3\u003c/strong\u003e and more than the maximum height of the tallest glyph. The width of a rectangle is at least \u003cstrong\u003e3\u003c/strong\u003e.\u003c/p\u003e\n\n\u003cp\u003eA box must have a margin of \u003cstrong\u003e1\u003c/strong\u003e pixel around the edge of it.\u003c/p\u003e\n\n\u003cp\u003eYou can assume the glyphs are never arranged vertically. Moreover, you can assume that if two rectangles, or a rectangle and a glyph, are in the same column, then one of them contains the other. For all bounding boxes of glyphs and black cells of rectangles, there is at least one white cell between every two of them. You can assume at least one cell in the bitmap is black.\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eOutput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eFor each monolith, output the transliterated sentence in one line. After the output for one dataset, output \u0027\u003cstrong\u003e#\u003c/strong\u003e\u0027 in one line.\u003c/p\u003e\n\n"}},{"title":"Example","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 1\na 11 9\n****.....\n.*.*.....\n.*.*.....\n.*..*....\n.**..*...\n..**..*..\n..*.*....\n..**.*.*.\n..*..*.*.\n..*****.*\n******.**\nb 10 6\n....*.\n....*.\n....*.\n....*.\n....*.\n....*.\n....*.\n....*.\n.**..*\n*****.\n19 55\n*******************************************************\n*.....................................................*\n*.********************.********************...........*\n*.*..................*.*..................*...........*\n*.*.****.............*.*.............****.*.****......*\n*.*..*.*..........*..*.*..*..........*.*..*..*.*......*\n*.*..*.*..........*..*.*..*..........*.*..*..*.*......*\n*.*..*..*.........*..*.*..*.........*..*..*..*..*.....*\n*.*..**..*........*..*.*..*........*..**..*..**..*....*\n*.*...**..*.......*..*.*..*.......*..**...*...**..*...*\n*.*...*.*.........*..*.*..*.........*.*...*...*.*.....*\n*.*...**.*.*......*..*.*..*......*.*.**...*...**.*.*..*\n*.*...*..*.*......*..*.*..*......*.*..*...*...*..*.*..*\n*.*...*****.*..**..*.*.*.*..**..*.*****...*...*****.*.*\n*.*.******.**.*****..*.*..*****.**.******.*.******.**.*\n*.*..................*.*..................*...........*\n*.********************.********************...........*\n*.....................................................*\n*******************************************************\n2 3\na 2 3\n.*.\n***\nb 3 3\n.*.\n***\n.*.\n2 3\n.*.\n***\n4 3\n***\n*.*\n*.*\n***\n9 13\n************.\n*..........*.\n*.......*..*.\n*...*..***.*.\n*..***.....*.\n*...*......*.\n*..........*.\n************.\n.............\n3 1\na 2 2\n.*\n**\nb 2 1\n*\n*\nc 3 3\n***\n*.*\n***\n11 16\n****************\n*..............*\n*....*********.*\n*....*.......*.*\n*.*..*.***...*.*\n*.**.*.*.*.*.*.*\n*....*.***.*.*.*\n*....*.......*.*\n*....*********.*\n*..............*\n****************\n0 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e[[ab][ab]a]\n#\na\n[]\n[ba]\n#\n[[cb]a]\n#\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}