시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 109 71 60 76.923%

문제

창영이는 바이너리 트리를 매우 좋아한다. 그가 가장 좋아하는 게임은 바이너리 트리를 만들고, 노드에 알파벳 대문자를 하나씩 쓰는 것이다. 같은 알파벳을 여러 노드에 쓰지 않는다.

아래는 창영이가 만든 한 바이너리 트리이다.

                                               D
                                              / \
                                             /   \
                                            B     E
                                           / \     \
                                          /   \     \
                                         A     C     G
                                                    /
                                                   /
                                                  F

창영이는 후손들에게 물려주기 위해서, 만든 트리를 항상 종이제 적어놓는다. 이때, 트리를 프리오더 순회한 결과와 인오더로 순회한 결과를 적어 놓는다. 위의 트리를 프리오더로 순회하면 DBACEGF가 되고, 인오더로 순회하면 ABCDEFG가 된다. 창영이는 이 두 순서만 있으면, 트리를 만들 수 있다고 생각했기 때문에, 포스트오더로 순회한 결과는 적지 않았다.

몇 년이 지난 후, 종이를 보고 트리를 다시 만드려고 했다. 하지만 너무 귀찮은 나머지 프로그램을 작성하려고 한다. 트리를 프리오더와 인오더로 순회한 결과가 주어졌을 때, 포스트오더로 순회한 결과를 구하는 프로그램을 작성하시오.

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 한 줄로 이루어져 있고, 프리오더로 순회한 결과와 인오더로 순회한 결과가 공백으로 구분되어져 있다. 두 문자열의 길이는 항상 같으며, 26자를 넘지 않는다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 트리를 포스트오더로 순회한 결과를 출력한다.

예제 입력 1

DBACEGF ABCDEFG
BCAD CBAD

예제 출력 1

ACBFGED
CDAB
W3sicHJvYmxlbV9pZCI6IjY1OTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI5YWMgXHViY2Y1XHVhZDZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHViYzE0XHVjNzc0XHViMTA4XHViOWFjIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWI5ZTRcdWM2YjAgXHVjODhiXHVjNTQ0XHVkNTVjXHViMmU0LiBcdWFkZjhcdWFjMDAgXHVhYzAwXHVjN2E1IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NDAgXHViYzE0XHVjNzc0XHViMTA4XHViOWFjIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFjZTAsIFx1YjE3OFx1YjRkY1x1YzVkMCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViMzAwXHViYjM4XHVjNzkwXHViOTdjIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM0ZjBcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWFjMTlcdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzQ0IFx1YzVlY1x1YjdlYyBcdWIxNzhcdWI0ZGNcdWM1ZDAgXHVjNGYwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4XHViMjk0IFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWI5Y2NcdWI0ZTAgXHVkNTVjIFx1YmMxNFx1Yzc3NFx1YjEwOFx1YjlhYyBcdWQyYjhcdWI5YWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgRFxyXG4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgXC8gXFxcclxuICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgXC8gICBcXFxyXG4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEIgICAgIEVcclxuICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIFwvIFxcICAgICBcXFxyXG4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBcLyAgIFxcICAgICBcXFxyXG4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEEgICAgIEMgICAgIEdcclxuICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIFwvXHJcbiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIFwvXHJcbiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgRjxcL3ByZT5cclxuXHJcbjxwPlx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWQ2YzRcdWMxOTBcdWI0ZTRcdWM1ZDBcdWFjOGMgXHViYjNjXHViODI0XHVjOGZjXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYywgXHViOWNjXHViNGUwIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWQ1NmRcdWMwYzEgXHVjODg1XHVjNzc0XHVjODFjIFx1YzgwMVx1YzViNFx1YjE5M1x1YjI5NFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWQyYjhcdWI5YWNcdWI5N2MgXHVkNTA0XHViOWFjXHVjNjI0XHViMzU0IFx1YzIxY1x1ZDY4Y1x1ZDU1YyBcdWFjYjBcdWFjZmNcdWM2NDAgXHVjNzc4XHVjNjI0XHViMzU0XHViODVjIFx1YzIxY1x1ZDY4Y1x1ZDU1YyBcdWFjYjBcdWFjZmNcdWI5N2MgXHVjODAxXHVjNWI0IFx1YjE5M1x1YjI5NFx1YjJlNC4gXHVjNzA0XHVjNzU4IFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWQ1MDRcdWI5YWNcdWM2MjRcdWIzNTRcdWI4NWMgXHVjMjFjXHVkNjhjXHVkNTU4XHViYTc0IERCQUNFR0ZcdWFjMDAgXHViNDE4XHVhY2UwLCBcdWM3NzhcdWM2MjRcdWIzNTRcdWI4NWMgXHVjMjFjXHVkNjhjXHVkNTU4XHViYTc0IEFCQ0RFRkdcdWFjMDAgXHViNDFjXHViMmU0LiBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVjNzc0IFx1YjQ1MCBcdWMyMWNcdWMxMWNcdWI5Y2MgXHVjNzg4XHVjNzNjXHViYTc0LCBcdWQyYjhcdWI5YWNcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVkM2VjXHVjMmE0XHVkMmI4XHVjNjI0XHViMzU0XHViODVjIFx1YzIxY1x1ZDY4Y1x1ZDU1YyBcdWFjYjBcdWFjZmNcdWIyOTQgXHVjODAxXHVjOWMwIFx1YzU0YVx1YzU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYTg3IFx1YjE0NFx1Yzc3NCBcdWM5YzBcdWIwOWMgXHVkNmM0LCBcdWM4ODVcdWM3NzRcdWI5N2MgXHViY2Y0XHVhY2UwIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWIyZTRcdWMyZGMgXHViOWNjXHViNGRjXHViODI0XHVhY2UwIFx1ZDU4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YjEwOFx1YmIzNCBcdWFkYzBcdWNjMmVcdWM3NDAgXHViMDk4XHViYTM4XHVjOWMwIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQyYjhcdWI5YWNcdWI5N2MgXHVkNTA0XHViOWFjXHVjNjI0XHViMzU0XHVjNjQwIFx1Yzc3OFx1YzYyNFx1YjM1NFx1Yjg1YyBcdWMyMWNcdWQ2OGNcdWQ1NWMgXHVhY2IwXHVhY2ZjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1ZDNlY1x1YzJhNFx1ZDJiOFx1YzYyNFx1YjM1NFx1Yjg1YyBcdWMyMWNcdWQ2OGNcdWQ1NWMgXHVhY2IwXHVhY2ZjXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1ZDU1OFx1YjA5OCBcdWI2MTBcdWIyOTQgXHVhZGY4IFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVkNTA0XHViOWFjXHVjNjI0XHViMzU0XHViODVjIFx1YzIxY1x1ZDY4Y1x1ZDU1YyBcdWFjYjBcdWFjZmNcdWM2NDAgXHVjNzc4XHVjNjI0XHViMzU0XHViODVjIFx1YzIxY1x1ZDY4Y1x1ZDU1YyBcdWFjYjBcdWFjZmNcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWFjMTlcdWM3M2NcdWJhNzAsIDI2XHVjNzkwXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWQzZWNcdWMyYTRcdWQyYjhcdWM2MjRcdWIzNTRcdWI4NWMgXHVjMjFjXHVkNjhjXHVkNTVjIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjU5NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRyZWUgUmVjb3ZlcnkiLCJkZXNjcmlwdGlvbiI6IjxwPkxpdHRsZSBWYWxlbnRpbmUgbGlrZWQgcGxheWluZyB3aXRoIGJpbmFyeSB0cmVlcyB2ZXJ5IG11Y2guIEhlciBmYXZvcml0ZSBnYW1lIHdhcyBjb25zdHJ1Y3RpbmcgcmFuZG9tbHkgbG9va2luZyBiaW5hcnkgdHJlZXMgd2l0aCBjYXBpdGFsIGxldHRlcnMgaW4gdGhlIG5vZGVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGlzIGlzIGFuIGV4YW1wbGUgb2Ygb25lIG9mIGhlciBjcmVhdGlvbnM6PFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgRFxyXG4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgXC8gXFxcclxuICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgXC8gICBcXFxyXG4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEIgICAgIEVcclxuICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIFwvIFxcICAgICBcXFxyXG4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBcLyAgIFxcICAgICBcXFxyXG4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEEgICAgIEMgICAgIEdcclxuICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIFwvXHJcbiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIFwvXHJcbiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgRjxcL3ByZT5cclxuXHJcbjxwPlRvIHJlY29yZCBoZXIgdHJlZXMgZm9yIGZ1dHVyZSBnZW5lcmF0aW9ucywgc2hlIHdyb3RlIGRvd24gdHdvIHN0cmluZ3MgZm9yIGVhY2ggdHJlZTogYSBwcmVvcmRlciB0cmF2ZXJzYWwgKHJvb3QsIGxlZnQgc3VidHJlZSwgcmlnaHQgc3VidHJlZSkgYW5kIGFuIGlub3JkZXIgdHJhdmVyc2FsIChsZWZ0IHN1YnRyZWUsIHJvb3QsIHJpZ2h0IHN1YnRyZWUpLiBGb3IgdGhlIHRyZWUgZHJhd24gYWJvdmUgdGhlIHByZW9yZGVyIHRyYXZlcnNhbCBpcyBEQkFDRUdGIGFuZCB0aGUgaW5vcmRlciB0cmF2ZXJzYWwgaXMgQUJDREVGRy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U2hlIHRob3VnaHQgdGhhdCBzdWNoIGEgcGFpciBvZiBzdHJpbmdzIHdvdWxkIGdpdmUgZW5vdWdoIGluZm9ybWF0aW9uIHRvIHJlY29uc3RydWN0IHRoZSB0cmVlIGxhdGVyIChidXQgc2hlIG5ldmVyIHRyaWVkIGl0KS48XC9wPlxyXG5cclxuPHA+Tm93LCB5ZWFycyBsYXRlciwgbG9va2luZyBhZ2FpbiBhdCB0aGUgc3RyaW5ncywgc2hlIHJlYWxpemVkIHRoYXQgcmVjb25zdHJ1Y3RpbmcgdGhlIHRyZWVzIHdhcyBpbmRlZWQgcG9zc2libGUsIGJ1dCBvbmx5IGJlY2F1c2Ugc2hlIG5ldmVyIGhhZCB1c2VkIHRoZSBzYW1lIGxldHRlciB0d2ljZSBpbiB0aGUgc2FtZSB0cmVlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ib3dldmVyLCBkb2luZyB0aGUgcmVjb25zdHJ1Y3Rpb24gYnkgaGFuZCwgc29vbiB0dXJuZWQgb3V0IHRvIGJlIHRlZGlvdXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNvIG5vdyBzaGUgYXNrcyB5b3UgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgZG9lcyB0aGUgam9iIGZvciBoZXIhPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgZmlsZSB3aWxsIGNvbnRhaW4gb25lIG9yIG1vcmUgdGVzdCBjYXNlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2Ygb25lIGxpbmUgY29udGFpbmluZyB0d28gc3RyaW5ncyBwcmVvcmQgYW5kIGlub3JkLCByZXByZXNlbnRpbmcgdGhlIHByZW9yZGVyIHRyYXZlcnNhbCBhbmQgaW5vcmRlciB0cmF2ZXJzYWwgb2YgYSBiaW5hcnkgdHJlZS4gQm90aCBzdHJpbmdzIGNvbnNpc3Qgb2YgdW5pcXVlIGNhcGl0YWwgbGV0dGVycy4gKFRodXMgdGhleSBhcmUgbm90IGxvbmdlciB0aGFuIDI2IGNoYXJhY3RlcnMuKTxcL3A+XHJcblxyXG48cD5JbnB1dCBpcyB0ZXJtaW5hdGVkIGJ5IGVuZCBvZiBmaWxlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcmVjb3ZlciBWYWxlbnRpbmUmIzM5O3MgYmluYXJ5IHRyZWUgYW5kIHByaW50IG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIHRyZWUmIzM5O3MgcG9zdG9yZGVyIHRyYXZlcnNhbCAobGVmdCBzdWJ0cmVlLCByaWdodCBzdWJ0cmVlLCByb290KTxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=