시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 41 11 11 39.286%

문제

단어의 첫 글자와 마지막 글자를 제외한 나머지 글자의 순서를 섞어도 그 단어는 쉽게 읽을 수 있다. 예를 들어, 문장 "tihs snetncee mkaes prfecet sesne"는 많은 사람들이 쉽게 읽을 수 있다.

문장의 공백을 모두 제거해도 그 문장은 쉽게 읽을 수 있다. 예를 들면 "thissentencemakesperfectsense" 이다.

하지만, 글자의 순서를 섞고, 공백을 제거하면 문장은 쉽게 읽을 수 없다. "tihssnetnceemkaesprfecetsesne"와 같은 문장은 쉽게 읽을 수 없다.

글자의 순서를 섞고, 단어 사이의 공백을 제거한 문장이 주어진다. 또, 올바른 단어의 목록이 주어진다. 이때, 원래 문장을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 글자의 순서를 뒤섞고, 공백을 제거한 문장이 주어진다. 이 문장은 알파벳 소문자로만 이루어져 있으며, 길이는 최대 1000글자이다.

둘째 줄에는 올바른 단어의 개수 n (1 ≤ n ≤ 10,000)이 주어진다. 다음 n개 줄에는 올바른 단어가 주어진다. 모든 단어는 중복되지 않으며, 알파벳 소문자로만 이루어져 있다. 또, 길이는 최대 100글자이다.

출력

각 테스트 케이스마다, 원래 문장을 유일하게 만들 수 있으면 그 문장을 출력한다. 문장을 만들 수 있는 방법이 여러 가지인 경우에는 "ambiguous"를, 불가능한 경우에는 "impossible"을 출력한다.

예제 입력 1

3
tihssnetnceemkaesprfecetsesne
5
makes
perfect
sense
sentence
this
hitehre
2
there
hello
hitehre
3
hi
there
three

예제 출력 1

this sentence makes perfect sense
impossible
ambiguous
W3sicHJvYmxlbV9pZCI6IjM2OTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NjBcdWI5ZTRcdWQ1NjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjJlOFx1YzViNFx1Yzc1OCBcdWNjYWIgXHVhZTAwXHVjNzkwXHVjNjQwIFx1YjljOFx1YzljMFx1YjljOSBcdWFlMDBcdWM3OTBcdWI5N2MgXHVjODFjXHVjNjc4XHVkNTVjIFx1YjA5OFx1YmEzOFx1YzljMCBcdWFlMDBcdWM3OTBcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1YzExZVx1YzViNFx1YjNjNCBcdWFkZjggXHViMmU4XHVjNWI0XHViMjk0IFx1YzI3ZFx1YWM4YyBcdWM3N2RcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViYjM4XHVjN2E1ICZxdW90O3RpaHMgc25ldG5jZWUgbWthZXMgcHJmZWNldCBzZXNuZSZxdW90O1x1YjI5NCBcdWI5Y2VcdWM3NDAgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1YzI3ZFx1YWM4YyBcdWM3N2RcdWM3NDQmbmJzcDtcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM3YTVcdWM3NTggXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWM4MWNcdWFjNzBcdWQ1NzRcdWIzYzQgXHVhZGY4IFx1YmIzOFx1YzdhNVx1Yzc0MCBcdWMyN2RcdWFjOGMgXHVjNzdkXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgJnF1b3Q7dGhpc3NlbnRlbmNlbWFrZXNwZXJmZWN0c2Vuc2UmcXVvdDsgXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YWUwMFx1Yzc5MFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWI5N2MgXHVjMTFlXHVhY2UwLCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjODFjXHVhYzcwXHVkNTU4XHViYTc0IFx1YmIzOFx1YzdhNVx1Yzc0MCBcdWMyN2RcdWFjOGMgXHVjNzdkXHVjNzQ0IFx1YzIxOCBcdWM1YzZcdWIyZTQuICZxdW90O3RpaHNzbmV0bmNlZW1rYWVzcHJmZWNldHNlc25lJnF1b3Q7XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWJiMzhcdWM3YTVcdWM3NDAgXHVjMjdkXHVhYzhjIFx1Yzc3ZFx1Yzc0NCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFlMDBcdWM3OTBcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1YzExZVx1YWNlMCwgXHViMmU4XHVjNWI0IFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjODFjXHVhYzcwXHVkNTVjIFx1YmIzOFx1YzdhNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjYxMCwgXHVjNjJjXHViYzE0XHViOTc4IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWJhYTlcdWI4NWRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzZkMFx1Yjc5OCBcdWJiMzhcdWM3YTVcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHVjZDVjXHViMzAwIDEwMFx1YWMxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFlMDBcdWM3OTBcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1YjRhNFx1YzExZVx1YWNlMCwgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU1YyBcdWJiMzhcdWM3YTVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViYjM4XHVjN2E1XHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZTM4XHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YjMwMCAxMDAwXHVhZTAwXHVjNzkwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWIyZThcdWM1YjRcdWM3NTggXHVhYzFjXHVjMjE4IG4gKDEgJmxlOyBuICZsZTsgMTAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBuXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzggXHViMmU4XHVjNWI0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YjJlOFx1YzViNFx1YjI5NCBcdWM5MTFcdWJjZjVcdWI0MThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTcwLCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgXHVhZTM4XHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YjMwMCAxMDBcdWFlMDBcdWM3OTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQsIFx1YzZkMFx1Yjc5OCBcdWJiMzhcdWM3YTVcdWM3NDQgXHVjNzIwXHVjNzdjXHVkNTU4XHVhYzhjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTc0IFx1YWRmOCBcdWJiMzhcdWM3YTVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJiMzhcdWM3YTVcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0ICZxdW90O2FtYmlndW91cyZxdW90O1x1Yjk3YywgXHViZDg4XHVhYzAwXHViMmE1XHVkNTVjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAmcXVvdDtpbXBvc3NpYmxlJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNjk4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiT2JmdXNjYXRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPkl0IGlzIGEgd2VsbC1rbm93biBmYWN0IHRoYXQgaWYgeW91IG1peCB1cCB0aGUgbGV0dGVycyBvZiBhIHdvcmQsIHdoaWxlIGxlYXZpbmcgdGhlIFx1ZmIwMXJzdCBhbmQgbGFzdCBsZXR0ZXJzIGluIHRoZWlyIHBsYWNlcywgd29yZHMgc3RpbGwgcmVtYWluIHJlYWRhYmxlLiBGb3IgZXhhbXBsZSwgdGhlIHNlbnRlbmNlICZsZHF1bzt0aWhzIHNuZXRuY2VlIG1rYWVzIHByZmVjZXQgc2VzbmUmcmRxdW87LCBtYWtlcyBwZXJmZWN0IHNlbnNlIHRvIG1vc3QgcGVvcGxlLjxcL3A+XHJcblxyXG48cD5JZiB5b3UgcmVtb3ZlIGFsbCBzcGFjZXMgZnJvbSBhIHNlbnRlbmNlLCBpdCBzdGlsbCByZW1haW5zIHBlcmZlY3RseSByZWFkYWJsZSwgc2VlIGZvciBleGFtcGxlOiAmbGRxdW87dGhpc3NlbnRlbmNlbWFrZXNwZXJmZWN0c2Vuc2UmcmRxdW87LCBob3dldmVyIGlmIHlvdSBjb21iaW5lIHRoZXNlIHR3byB0aGluZ3MsIGZpcnN0IHNodWZmbGluZywgdGhlbiByZW1vdmluZyBzcGFjZXMsIHRoaW5ncyBnZXQgaGFyZC4gVGhlIGZvbGxvd2luZyBzZW50ZW5jZSBpcyBoYXJkZXIgdG8gZGVjaXBoZXI6ICZsZHF1bzt0aWhzc25ldG5jZWVta2Flc3ByZmVjZXRzZXNuZSZyZHF1bzsuPFwvcD5cclxuXHJcbjxwPllvdSZyc3F1bztyZSBnaXZlbiBhIHNlbnRlbmNlIGluIHRoZSBsYXN0IGZvcm0sIHRvZ2V0aGVyIHdpdGggYSBkaWN0aW9uYXJ5IG9mIHZhbGlkIHdvcmRzIGFuZCBhcmUgYXNrZWQgdG8gZGVjaXBoZXIgdGhlIHRleHQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgXHVmYjAxcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0Y2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0Y2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIGEgc3RyaW5nIHM6IHRoZSBzZW50ZW5jZSB0byBkZWNpcGhlci4gVGhlIHNlbnRlbmNlIGNvbnNpc3RzIG9mIGxvd2VyY2FzZSBsZXR0ZXJzIGFuZCBoYXMgYSBsZW5ndGggb2YgYXQgbGVhc3QgMSBhbmQgYXQgbW9zdCAxIDAwMCBjaGFyYWN0ZXJzLjxcL2xpPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIGFuIGludGVnZXIgbiB3aXRoIDEgJmxlOyBuICZsZTsgMTAgMDAwOiB0aGUgbnVtYmVyIG9mIHdvcmRzIGluIHRoZSBkaWN0aW9uYXJ5LjxcL2xpPlxyXG5cdDxsaT5uIGxpbmVzIHdpdGggb25lIHdvcmQgZWFjaC4gQSB3b3JkIGNvbnNpc3RzIG9mIGxvd2VyY2FzZSBsZXR0ZXJzIGFuZCBoYXMgYSBsZW5ndGggb2YgYXQgbGVhc3QgMSBhbmQgYXQgbW9zdCAxMDAgY2hhcmFjdGVycy4gQWxsIHRoZSB3b3JkcyBhcmUgdW5pcXVlLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggdGhlIGRlY2lwaGVyZWQgc2VudGVuY2UsIGlmIGl0IGlzIHBvc3NpYmxlIHRvIHVuaXF1ZWx5IGRlY2lwaGVyIGl0LiBPdGhlcndpc2UgJmxkcXVvO2ltcG9zc2libGUmcmRxdW87IG9yICZsZHF1bzthbWJpZ3VvdXMmcmRxdW87LCBkZXBlbmRpbmcgb24gd2hpY2ggaXMgdGhlIGNhc2UuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2007 H번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: vega