시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 450 292 240 66.667%

문제

소희는 공개키와 개인키 한 쌍으로 보안을 유지하는 것이 매우 불편하다고 생각했다. 그래서 소희는 공개키와 개인키를 암호화 체계를 개발했다. 이를 "철벽 보안 알고리즘"이라고 부르기로 했다. 알고리즘은 다음과 같다.

한 단어는 1~10개의 대문자(A-Z)들로 이루어진 문자열이다. 한 문장은 공백으로 구분된 단어들로 이루어졌다.

제 1 공개키는 최대 한 번만 사용된 단어들로 되어있다.

제 2 공개키는 제 1 공개키의 단어들을 재배치하여 만들어진다.

평문(암호화 되지 않은 문장)은 제 1 공개키와 같이 여러 단어들로 되어있지만, 제 1 공개키와 다르게 각 단어들은 중복이 가능하다.

암호문(암호화 된 문장)은 평문을 제 2 공개키를 만든 규칙의 반대로 재배치하여 만들어진다.

주어진 2개의 공개키와 암호문으로 평문을 복구하라.

입력

입력의 첫 줄에는 테스트 케이스의 수를 의미하는 하나의 정수가 입력된다. 정수는 100을 넘지 않는다.

각 테스트케이스마다 아래 항목들을 한 줄씩 입력받는다.

  • 한 문장의 단어 수 n (1 ≤ n ≤ 1 000)
  • 제 1 공개키
  • 제 2 공개키
  • 암호문

모든 단어들은 최소 1개, 최대 10개의 대문자들로 이루어져있다.

출력

각 케이스마다

  • 암호문을 해독한 평문

을 한 줄에 줄력한다.

예제 입력 1

2
4
A B C D
D A B C
C B A P
3
SECURITY THROUGH OBSCURITY
OBSCURITY THROUGH SECURITY
TOMORROW ATTACK WE

예제 출력 1

B A P C
WE ATTACK TOMORROW

힌트

W3sicHJvYmxlbV9pZCI6IjkzMjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjYTBcdWJjYmQgXHViY2Y0XHVjNTQ4IFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMThjXHVkNzZjXHViMjk0IFx1YWNmNVx1YWMxY1x1ZDBhNFx1YzY0MCBcdWFjMWNcdWM3NzhcdWQwYTQgXHVkNTVjIFx1YzMwZFx1YzczY1x1Yjg1YyBcdWJjZjRcdWM1NDhcdWM3NDQgXHVjNzIwXHVjOWMwXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWI5ZTRcdWM2YjAgXHViZDg4XHVkM2I4XHVkNTU4XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU4OFx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YzE4Y1x1ZDc2Y1x1YjI5NCBcdWFjZjVcdWFjMWNcdWQwYTRcdWM2NDAgXHVhYzFjXHVjNzc4XHVkMGE0XHViOTdjIFx1YzU1NFx1ZDYzOFx1ZDY1NCBcdWNjYjRcdWFjYzRcdWI5N2MgXHVhYzFjXHViYzFjXHVkNTg4XHViMmU0LiBcdWM3NzRcdWI5N2MgJnF1b3Q7XHVjY2EwXHViY2JkIFx1YmNmNFx1YzU0OCZuYnNwO1x1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OCZxdW90O1x1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWJkODBcdWI5NzRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OThcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTVjIFx1YjJlOFx1YzViNFx1YjI5NCAxfjEwXHVhYzFjXHVjNzU4IFx1YjMwMFx1YmIzOFx1Yzc5MChBLVopXHViNGU0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWIyZTQuJm5ic3A7XHVkNTVjIFx1YmIzOFx1YzdhNVx1Yzc0MCZuYnNwO1x1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MWMmbmJzcDtcdWIyZThcdWM1YjRcdWI0ZTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODRjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MWMgMSBcdWFjZjVcdWFjMWNcdWQwYTRcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWJjODhcdWI5Y2MgXHVjMGFjXHVjNmE5XHViNDFjIFx1YjJlOFx1YzViNFx1YjRlNFx1Yjg1YyBcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgxYyAyIFx1YWNmNVx1YWMxY1x1ZDBhNFx1YjI5NCBcdWM4MWMgMSBcdWFjZjVcdWFjMWNcdWQwYTRcdWM3NTggXHViMmU4XHVjNWI0XHViNGU0XHVjNzQ0IFx1YzdhY1x1YmMzMFx1Y2U1OFx1ZDU1OFx1YzVlYyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDNjOVx1YmIzOChcdWM1NTRcdWQ2MzhcdWQ2NTQgXHViNDE4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWJiMzhcdWM3YTUpXHVjNzQwIFx1YzgxYyAxJm5ic3A7XHVhY2Y1XHVhYzFjXHVkMGE0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHViMmU4XHVjNWI0XHViNGU0XHViODVjIFx1YjQxOFx1YzViNFx1Yzc4OFx1YzljMFx1YjljYywgXHVjODFjIDEmbmJzcDtcdWFjZjVcdWFjMWNcdWQwYTRcdWM2NDAgXHViMmU0XHViOTc0XHVhYzhjIFx1YWMwMSBcdWIyZThcdWM1YjRcdWI0ZTRcdWM3NDAmbmJzcDtcdWM5MTFcdWJjZjVcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NTRcdWQ2MzhcdWJiMzgoXHVjNTU0XHVkNjM4XHVkNjU0IFx1YjQxYyBcdWJiMzhcdWM3YTUpXHVjNzQwIFx1ZDNjOVx1YmIzOFx1Yzc0NCBcdWM4MWMgMiBcdWFjZjVcdWFjMWNcdWQwYTRcdWI5N2MgXHViOWNjXHViNGUwIFx1YWRkY1x1Y2U1OVx1Yzc1OCBcdWJjMThcdWIzMDBcdWI4NWMgXHVjN2FjXHViYzMwXHVjZTU4XHVkNTU4XHVjNWVjJm5ic3A7XHViOWNjXHViNGU0XHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4ZmNcdWM1YjRcdWM5YzQgMlx1YWMxY1x1Yzc1OCBcdWFjZjVcdWFjMWNcdWQwYTRcdWM2NDAmbmJzcDtcdWM1NTRcdWQ2MzhcdWJiMzhcdWM3M2NcdWI4NWMgXHVkM2M5XHViYjM4XHVjNzQ0IFx1YmNmNVx1YWQ2Y1x1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YjI5NCZuYnNwO1x1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LiBcdWM4MTVcdWMyMThcdWIyOTQgMTAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjNTQ0XHViNzk4IFx1ZDU2ZFx1YmFhOVx1YjRlNFx1Yzc0NCBcdWQ1NWMgXHVjOTA0XHVjNTI5IFx1Yzc4NVx1YjgyNVx1YmMxYlx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWQ1NWMgXHViYjM4XHVjN2E1XHVjNzU4IFx1YjJlOFx1YzViNCBcdWMyMTgmbmJzcDtuJm5ic3A7KDEgJmxlOyBuICZsZTsgMSAwMDApPFwvbGk+XHJcblx0PGxpPlx1YzgxYyAxIFx1YWNmNVx1YWMxY1x1ZDBhNDxcL2xpPlxyXG5cdDxsaT5cdWM4MWMgMiZuYnNwO1x1YWNmNVx1YWMxY1x1ZDBhNDxcL2xpPlxyXG5cdDxsaT5cdWM1NTRcdWQ2MzhcdWJiMzg8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHViMmU4XHVjNWI0XHViNGU0XHVjNzQwIFx1Y2Q1Y1x1YzE4YyAxXHVhYzFjLCBcdWNkNWNcdWIzMDAgMTBcdWFjMWNcdWM3NTgmbmJzcDtcdWIzMDBcdWJiMzhcdWM3OTBcdWI0ZTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4XHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQ8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM1NTRcdWQ2MzhcdWJiMzhcdWM3NDQgXHVkNTc0XHViM2M1XHVkNTVjJm5ic3A7XHVkM2M5XHViYjM4PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNzQ0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVjOTA0XHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkzMjIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFbmNyeXB0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5BbGljZSB0aGlua3MgaXQgaXMgdmVyeSBpbmNvbnZlbmllbnQgdG8gaGF2ZSB0byBrZWVwIG9uZSBvZiBoZXIga2V5cyBpbiBhIHB1YmxpYyZuZGFzaDtwcml2YXRlIGtleSBwYWlyIHNlY3JldC4gVGhlcmVmb3JlIHNoZSBpbnZlbnRlZCBhIHB1YmxpYyZuZGFzaDtwdWJsaWMga2V5IGVuY3J5cHRpb24gc2NoZW1lIGNhbGxlZCB0aGUgUmVhbGx5IFNlY3VyZSBBbGdvcml0aG0gKFJTQSkuIFRoZSBhbGdvcml0aG0gd29ya3MgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHA+QSA8ZW0+d29yZDxcL2VtPiBpcyBhIHNlcXVlbmNlIG9mIGJldHdlZW4gb25lIGFuZCB0ZW4gY2FwaXRhbCBsZXR0ZXJzIChBJm5kYXNoO1opLiBBIDxlbT5zZW50ZW5jZTxcL2VtPiBpcyBhIHNlcXVlbmNlIG9mIHdvcmRzLCBzZXBhcmF0ZWQgYnkgc3BhY2VzLiBUaGUgPGVtPlx1ZmIwMXJzdCBwdWJsaWMga2V5PFwvZW0+IGlzIGEgc2VudGVuY2UgaW4gd2hpY2ggZWFjaCB3b3JkIGlzIHVzZWQgYXQgbW9zdCBvbmNlLiBUaGUgPGVtPnNlY29uZCBwdWJsaWMga2V5PFwvZW0+IGlzIGEgc2VudGVuY2UgZm9ybWVkIGJ5IGFwcGx5aW5nIGEgcGVybXV0YXRpb24mbmJzcDsmc2lnbWE7Jm5ic3A7dG8gdGhlIHdvcmRzIGluIHRoZSBcdWZiMDFyc3QgcHVibGljIGtleS4gVGhlIDxlbT5wbGFpbnRleHQ8XC9lbT4gKHRoZSB1bmVuY3J5cHRlZCBtZXNzYWdlKSBpcyBhIHNlbnRlbmNlIHRoYXQgaGFzIGV4YWN0bHkgYXMgbWFueSB3b3JkcyBhcyB0aGUgcHVibGljIGtleXMuIChVbmxpa2UgZm9yIHRoZSBwdWJsaWMga2V5cywgdGhlc2Ugd29yZHMgYXJlIG5vdCBuZWNlc3NhcmlseSB1bmlxdWUuKSBUaGUgPGVtPmNpcGhlcnRleHQ8XC9lbT4gKHRoZSBlbmNyeXB0ZWQgbWVzc2FnZSkgaXMgdGhlIHNlbnRlbmNlIGZvcm1lZCBieSBhcHBseWluZyB0aGUgcGVybXV0YXRpb24gJnNpZ21hOyB0byB0aGUgcGxhaW50ZXh0LjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgdHdvIHB1YmxpYyBrZXlzIGFuZCB0aGUgY2lwaGVydGV4dCwgcmVjb3ZlciB0aGUgcGxhaW50ZXh0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGFuIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAxIDAwMCk6IHRoZSBudW1iZXIgb2Ygd29yZHMgaW4gZWFjaCBzZW50ZW5jZS48XC9saT5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhIHNlbnRlbmNlOiB0aGUgXHVmYjAxcnN0IHB1YmxpYyBrZXkuPFwvbGk+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYSBzZW50ZW5jZTogdGhlIHNlY29uZCBwdWJsaWMga2V5LjxcL2xpPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGEgc2VudGVuY2U6IHRoZSBjaXBoZXJ0ZXh0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkFsbCB3b3JkcyBjb25zaXN0IG9mIGF0IGxlYXN0IDEgYW5kIGF0IG1vc3QgMTAgdXBwZXJjYXNlIGxldHRlcnMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGEgc2VudGVuY2U6IHRoZSBwbGFpbnRleHQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=