시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 47 13 12 40.000%

문제

단어의 첫 글자와 마지막 글자를 제외한 나머지 글자의 순서를 섞어도 그 단어는 쉽게 읽을 수 있다. 예를 들어, 문장 "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+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQsIFx1YzZkMFx1Yjc5OCBcdWJiMzhcdWM3YTVcdWM3NDQgXHVjNzIwXHVjNzdjXHVkNTU4XHVhYzhjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTc0IFx1YWRmOCBcdWJiMzhcdWM3YTVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJiMzhcdWM3YTVcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0ICZxdW90O2FtYmlndW91cyZxdW90O1x1Yjk3YywgXHViZDg4XHVhYzAwXHViMmE1XHVkNTVjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAmcXVvdDtpbXBvc3NpYmxlJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM2OTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJPYmZ1c2NhdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+SXQgaXMgYSB3ZWxsLWtub3duIGZhY3QgdGhhdCBpZiB5b3UgbWl4IHVwIHRoZSBsZXR0ZXJzIG9mIGEgd29yZCwgd2hpbGUgbGVhdmluZyB0aGUgXHVmYjAxcnN0IGFuZCBsYXN0IGxldHRlcnMgaW4gdGhlaXIgcGxhY2VzLCB3b3JkcyBzdGlsbCByZW1haW4gcmVhZGFibGUuIEZvciBleGFtcGxlLCB0aGUgc2VudGVuY2UgJmxkcXVvO3RpaHMgc25ldG5jZWUgbWthZXMgcHJmZWNldCBzZXNuZSZyZHF1bzssIG1ha2VzIHBlcmZlY3Qgc2Vuc2UgdG8gbW9zdCBwZW9wbGUuPFwvcD5cclxuXHJcbjxwPklmIHlvdSByZW1vdmUgYWxsIHNwYWNlcyBmcm9tIGEgc2VudGVuY2UsIGl0IHN0aWxsIHJlbWFpbnMgcGVyZmVjdGx5IHJlYWRhYmxlLCBzZWUgZm9yIGV4YW1wbGU6ICZsZHF1bzt0aGlzc2VudGVuY2VtYWtlc3BlcmZlY3RzZW5zZSZyZHF1bzssIGhvd2V2ZXIgaWYgeW91IGNvbWJpbmUgdGhlc2UgdHdvIHRoaW5ncywgZmlyc3Qgc2h1ZmZsaW5nLCB0aGVuIHJlbW92aW5nIHNwYWNlcywgdGhpbmdzIGdldCBoYXJkLiBUaGUgZm9sbG93aW5nIHNlbnRlbmNlIGlzIGhhcmRlciB0byBkZWNpcGhlcjogJmxkcXVvO3RpaHNzbmV0bmNlZW1rYWVzcHJmZWNldHNlc25lJnJkcXVvOy48XC9wPlxyXG5cclxuPHA+WW91JnJzcXVvO3JlIGdpdmVuIGEgc2VudGVuY2UgaW4gdGhlIGxhc3QgZm9ybSwgdG9nZXRoZXIgd2l0aCBhIGRpY3Rpb25hcnkgb2YgdmFsaWQgd29yZHMgYW5kIGFyZSBhc2tlZCB0byBkZWNpcGhlciB0aGUgdGV4dC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3RjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggYSBzdHJpbmcgczogdGhlIHNlbnRlbmNlIHRvIGRlY2lwaGVyLiBUaGUgc2VudGVuY2UgY29uc2lzdHMgb2YgbG93ZXJjYXNlIGxldHRlcnMgYW5kIGhhcyBhIGxlbmd0aCBvZiBhdCBsZWFzdCAxIGFuZCBhdCBtb3N0IDEgMDAwIGNoYXJhY3RlcnMuPFwvbGk+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggYW4gaW50ZWdlciBuIHdpdGggMSAmbGU7IG4gJmxlOyAxMCAwMDA6IHRoZSBudW1iZXIgb2Ygd29yZHMgaW4gdGhlIGRpY3Rpb25hcnkuPFwvbGk+XHJcblx0PGxpPm4gbGluZXMgd2l0aCBvbmUgd29yZCBlYWNoLiBBIHdvcmQgY29uc2lzdHMgb2YgbG93ZXJjYXNlIGxldHRlcnMgYW5kIGhhcyBhIGxlbmd0aCBvZiBhdCBsZWFzdCAxIGFuZCBhdCBtb3N0IDEwMCBjaGFyYWN0ZXJzLiBBbGwgdGhlIHdvcmRzIGFyZSB1bmlxdWUuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCB0aGUgZGVjaXBoZXJlZCBzZW50ZW5jZSwgaWYgaXQgaXMgcG9zc2libGUgdG8gdW5pcXVlbHkgZGVjaXBoZXIgaXQuIE90aGVyd2lzZSAmbGRxdW87aW1wb3NzaWJsZSZyZHF1bzsgb3IgJmxkcXVvO2FtYmlndW91cyZyZHF1bzssIGRlcGVuZGluZyBvbiB3aGljaCBpcyB0aGUgY2FzZS48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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