시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 1133 668 524 60.578%

문제

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

한 단어는 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+XHVjMThjXHVkNzZjXHViMjk0IFx1YWNmNVx1YWMxY1x1ZDBhNFx1YzY0MCBcdWFjMWNcdWM3NzhcdWQwYTQgXHVkNTVjIFx1YzMwZFx1YzczY1x1Yjg1YyBcdWJjZjRcdWM1NDhcdWM3NDQgXHVjNzIwXHVjOWMwXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWI5ZTRcdWM2YjAgXHViZDg4XHVkM2I4XHVkNTU4XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU4OFx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YzE4Y1x1ZDc2Y1x1YjI5NCBcdWFjZjVcdWFjMWNcdWQwYTRcdWI5Y2NcdWM3NDQmbmJzcDtcdWM3NzRcdWM2YTlcdWQ1NThcdWIyOTQgXHVjNTU0XHVkNjM4XHVkNjU0IFx1Y2NiNFx1YWNjNFx1Yjk3YyBcdWFjMWNcdWJjMWNcdWQ1ODhcdWIyZTQuIFx1Yzc3NFx1Yjk3YyAmcXVvdDtcdWNjYTBcdWJjYmQgXHViY2Y0XHVjNTQ4Jm5ic3A7XHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4JnF1b3Q7XHVjNzc0XHViNzdjXHVhY2UwIFx1YmQ4MFx1Yjk3NFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NWMgXHViMmU4XHVjNWI0XHViMjk0IDF+MTBcdWFjMWNcdWM3NTggXHViMzAwXHViYjM4XHVjNzkwKEEtWilcdWI0ZTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC4mbmJzcDtcdWQ1NWMgXHViYjM4XHVjN2E1XHVjNzQwJm5ic3A7XHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxYyZuYnNwO1x1YjJlOFx1YzViNFx1YjRlNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4NGNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgxYyAxIFx1YWNmNVx1YWMxY1x1ZDBhNFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVkNTVjIFx1YmM4OFx1YjljYyBcdWMwYWNcdWM2YTlcdWI0MWMgXHViMmU4XHVjNWI0XHViNGU0XHViODVjIFx1YjQxOFx1YzViNFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODFjIDIgXHVhY2Y1XHVhYzFjXHVkMGE0XHViMjk0IFx1YzgxYyAxIFx1YWNmNVx1YWMxY1x1ZDBhNFx1Yzc1OCBcdWIyZThcdWM1YjRcdWI0ZTRcdWM3NDQgXHVjN2FjXHViYzMwXHVjZTU4XHVkNTU4XHVjNWVjIFx1YjljY1x1YjRlNFx1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkM2M5XHViYjM4KFx1YzU1NFx1ZDYzOFx1ZDY1NCBcdWI0MThcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YmIzOFx1YzdhNSlcdWM3NDAgXHVjODFjIDEmbmJzcDtcdWFjZjVcdWFjMWNcdWQwYTRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWIyZThcdWM1YjRcdWI0ZTRcdWI4NWMgXHViNDE4XHVjNWI0XHVjNzg4XHVjOWMwXHViOWNjLCBcdWM4MWMgMSZuYnNwO1x1YWNmNVx1YWMxY1x1ZDBhNFx1YzY0MCBcdWIyZTRcdWI5NzRcdWFjOGMgXHVhYzAxIFx1YjJlOFx1YzViNFx1YjRlNFx1Yzc0MCZuYnNwO1x1YzkxMVx1YmNmNVx1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU1NFx1ZDYzOFx1YmIzOChcdWM1NTRcdWQ2MzhcdWQ2NTQgXHViNDFjIFx1YmIzOFx1YzdhNSlcdWM3NDAgXHVkM2M5XHViYjM4XHVjNzQ0IFx1YzgxYyAyIFx1YWNmNVx1YWMxY1x1ZDBhNFx1Yjk3YyBcdWI5Y2NcdWI0ZTAgXHVhZGRjXHVjZTU5XHVjNzU4IFx1YmMxOFx1YjMwMFx1Yjg1YyBcdWM3YWNcdWJjMzBcdWNlNThcdWQ1NThcdWM1ZWMmbmJzcDtcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzhmY1x1YzViNFx1YzljNCAyXHVhYzFjXHVjNzU4IFx1YWNmNVx1YWMxY1x1ZDBhNFx1YzY0MCZuYnNwO1x1YzU1NFx1ZDYzOFx1YmIzOFx1YzczY1x1Yjg1YyBcdWQzYzlcdWJiMzhcdWM3NDQgXHViY2Y1XHVhZDZjXHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0Jm5ic3A7XHVkNTU4XHViMDk4XHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuIFx1YzgxNVx1YzIxOFx1YjI5NCAxMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWM1NDRcdWI3OTggXHVkNTZkXHViYWE5XHViNGU0XHVjNzQ0IFx1ZDU1YyBcdWM5MDRcdWM1MjkgXHVjNzg1XHViODI1XHViYzFiXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1ZDU1YyBcdWJiMzhcdWM3YTVcdWM3NTggXHViMmU4XHVjNWI0IFx1YzIxOCZuYnNwO24mbmJzcDsoMSAmbGU7IG4gJmxlOyAxIDAwMCk8XC9saT5cclxuXHQ8bGk+XHVjODFjIDEgXHVhY2Y1XHVhYzFjXHVkMGE0PFwvbGk+XHJcblx0PGxpPlx1YzgxYyAyJm5ic3A7XHVhY2Y1XHVhYzFjXHVkMGE0PFwvbGk+XHJcblx0PGxpPlx1YzU1NFx1ZDYzOFx1YmIzODxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWIyZThcdWM1YjRcdWI0ZTRcdWM3NDAgXHVjZDVjXHVjMThjIDFcdWFjMWMsIFx1Y2Q1Y1x1YjMwMCAxMFx1YWMxY1x1Yzc1OCZuYnNwO1x1YjMwMFx1YmIzOFx1Yzc5MFx1YjRlNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzhcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNDxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzU1NFx1ZDYzOFx1YmIzOFx1Yzc0NCBcdWQ1NzRcdWIzYzVcdWQ1NWMmbmJzcDtcdWQzYzlcdWJiMzg8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM3NDQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWM5MDRcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTMyMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVuY3J5cHRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPkFsaWNlIHRoaW5rcyBpdCBpcyB2ZXJ5IGluY29udmVuaWVudCB0byBoYXZlIHRvIGtlZXAgb25lIG9mIGhlciBrZXlzIGluIGEgcHVibGljJm5kYXNoO3ByaXZhdGUga2V5IHBhaXIgc2VjcmV0LiBUaGVyZWZvcmUgc2hlIGludmVudGVkIGEgcHVibGljJm5kYXNoO3B1YmxpYyBrZXkgZW5jcnlwdGlvbiBzY2hlbWUgY2FsbGVkIHRoZSBSZWFsbHkgU2VjdXJlIEFsZ29yaXRobSAoUlNBKS4gVGhlIGFsZ29yaXRobSB3b3JrcyBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48cD5BIDxlbT53b3JkPFwvZW0+IGlzIGEgc2VxdWVuY2Ugb2YgYmV0d2VlbiBvbmUgYW5kIHRlbiBjYXBpdGFsIGxldHRlcnMgKEEmbmRhc2g7WikuIEEgPGVtPnNlbnRlbmNlPFwvZW0+IGlzIGEgc2VxdWVuY2Ugb2Ygd29yZHMsIHNlcGFyYXRlZCBieSBzcGFjZXMuIFRoZSA8ZW0+XHVmYjAxcnN0IHB1YmxpYyBrZXk8XC9lbT4gaXMgYSBzZW50ZW5jZSBpbiB3aGljaCBlYWNoIHdvcmQgaXMgdXNlZCBhdCBtb3N0IG9uY2UuIFRoZSA8ZW0+c2Vjb25kIHB1YmxpYyBrZXk8XC9lbT4gaXMgYSBzZW50ZW5jZSBmb3JtZWQgYnkgYXBwbHlpbmcgYSBwZXJtdXRhdGlvbiZuYnNwOyZzaWdtYTsmbmJzcDt0byB0aGUgd29yZHMgaW4gdGhlIFx1ZmIwMXJzdCBwdWJsaWMga2V5LiBUaGUgPGVtPnBsYWludGV4dDxcL2VtPiAodGhlIHVuZW5jcnlwdGVkIG1lc3NhZ2UpIGlzIGEgc2VudGVuY2UgdGhhdCBoYXMgZXhhY3RseSBhcyBtYW55IHdvcmRzIGFzIHRoZSBwdWJsaWMga2V5cy4gKFVubGlrZSBmb3IgdGhlIHB1YmxpYyBrZXlzLCB0aGVzZSB3b3JkcyBhcmUgbm90IG5lY2Vzc2FyaWx5IHVuaXF1ZS4pIFRoZSA8ZW0+Y2lwaGVydGV4dDxcL2VtPiAodGhlIGVuY3J5cHRlZCBtZXNzYWdlKSBpcyB0aGUgc2VudGVuY2UgZm9ybWVkIGJ5IGFwcGx5aW5nIHRoZSBwZXJtdXRhdGlvbiAmc2lnbWE7IHRvIHRoZSBwbGFpbnRleHQuPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSB0d28gcHVibGljIGtleXMgYW5kIHRoZSBjaXBoZXJ0ZXh0LCByZWNvdmVyIHRoZSBwbGFpbnRleHQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgXHVmYjAxcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYW4gaW50ZWdlciBuICgxICZsZTsgbiAmbGU7IDEgMDAwKTogdGhlIG51bWJlciBvZiB3b3JkcyBpbiBlYWNoIHNlbnRlbmNlLjxcL2xpPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGEgc2VudGVuY2U6IHRoZSBcdWZiMDFyc3QgcHVibGljIGtleS48XC9saT5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhIHNlbnRlbmNlOiB0aGUgc2Vjb25kIHB1YmxpYyBrZXkuPFwvbGk+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYSBzZW50ZW5jZTogdGhlIGNpcGhlcnRleHQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+QWxsIHdvcmRzIGNvbnNpc3Qgb2YgYXQgbGVhc3QgMSBhbmQgYXQgbW9zdCAxMCB1cHBlcmNhc2UgbGV0dGVycy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYSBzZW50ZW5jZTogdGhlIHBsYWludGV4dC48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==