시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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
W3sicHJvYmxlbV9pZCI6IjM2OTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NjBcdWI5ZTRcdWQ1NjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjJlOFx1YzViNFx1Yzc1OCBcdWNjYWIgXHVhZTAwXHVjNzkwXHVjNjQwIFx1YjljOFx1YzljMFx1YjljOSBcdWFlMDBcdWM3OTBcdWI5N2MgXHVjODFjXHVjNjc4XHVkNTVjIFx1YjA5OFx1YmEzOFx1YzljMCBcdWFlMDBcdWM3OTBcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1YzExZVx1YzViNFx1YjNjNCBcdWFkZjggXHViMmU4XHVjNWI0XHViMjk0IFx1YzI3ZFx1YWM4YyBcdWM3N2RcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViYjM4XHVjN2E1ICZxdW90O3RpaHMgc25ldG5jZWUgbWthZXMgcHJmZWNldCBzZXNuZSZxdW90O1x1YjI5NCBcdWI5Y2VcdWM3NDAgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1YzI3ZFx1YWM4YyBcdWM3N2RcdTMxNDdcdWI5NzQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjN2E1XHVjNzU4IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWJhYThcdWI0NTAgXHVjODFjXHVhYzcwXHVkNTc0XHViM2M0IFx1YWRmOCBcdWJiMzhcdWM3YTVcdWM3NDAgXHVjMjdkXHVhYzhjIFx1Yzc3ZFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0ICZxdW90O3RoaXNzZW50ZW5jZW1ha2VzcGVyZmVjdHNlbnNlJnF1b3Q7IFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjLCBcdWFlMDBcdWM3OTBcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1YzExZVx1YWNlMCwgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU1OFx1YmE3NCBcdWJiMzhcdWM3YTVcdWM3NDAgXHVjMjdkXHVhYzhjIFx1Yzc3ZFx1Yzc0NCBcdWMyMTggXHVjNWM2XHViMmU0LiAmcXVvdDt0aWhzc25ldG5jZWVta2Flc3ByZmVjZXRzZXNuZSZxdW90O1x1YzY0MCBcdWFjMTlcdWM3NDAgXHViYjM4XHVjN2E1XHVjNzQwIFx1YzI3ZFx1YWM4YyBcdWM3N2RcdWM3NDQgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZTAwXHVjNzkwXHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWMxMWVcdWFjZTAsIFx1YjJlOFx1YzViNCBcdWMwYWNcdWM3NzRcdWM3NTggXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU1YyBcdWJiMzhcdWM3YTVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI2MTAsIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWIyZThcdWM1YjRcdWM3NTggXHViYWE5XHViODVkXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM2ZDBcdWI3OTggXHViYjM4XHVjN2E1XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1Y2Q1Y1x1YjMwMCAxMDBcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZTAwXHVjNzkwXHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWI0YTRcdWMxMWVcdWFjZTAsIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NWMgXHViYjM4XHVjN2E1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YmIzOFx1YzdhNVx1Yzc0MCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDAgMTAwMFx1YWUwMFx1Yzc5MFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzggXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOCBuICgxICZsZTsgbiAmbGU7IDEwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNjJjXHViYzE0XHViOTc4IFx1YjJlOFx1YzViNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWIyZThcdWM1YjRcdWIyOTQgXHVjOTExXHViY2Y1XHViNDE4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3MCwgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDAgMTAwXHVhZTAwXHVjNzkwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0LCBcdWM2ZDBcdWI3OTggXHViYjM4XHVjN2E1XHVjNzQ0IFx1YzcyMFx1Yzc3Y1x1ZDU1OFx1YWM4YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWFkZjggXHViYjM4XHVjN2E1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViYjM4XHVjN2E1XHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAmcXVvdDthbWJpZ3VvdXMmcXVvdDtcdWI5N2MsIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7aW1wb3NzaWJsZSZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzY5OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik9iZnVzY2F0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5JdCBpcyBhIHdlbGwta25vd24gZmFjdCB0aGF0IGlmIHlvdSBtaXggdXAgdGhlIGxldHRlcnMgb2YgYSB3b3JkLCB3aGlsZSBsZWF2aW5nIHRoZSBcdWZiMDFyc3QgYW5kIGxhc3QgbGV0dGVycyBpbiB0aGVpciBwbGFjZXMsIHdvcmRzIHN0aWxsIHJlbWFpbiByZWFkYWJsZS4gRm9yIGV4YW1wbGUsIHRoZSBzZW50ZW5jZSAmbGRxdW87dGlocyBzbmV0bmNlZSBta2FlcyBwcmZlY2V0IHNlc25lJnJkcXVvOywgbWFrZXMgcGVyZmVjdCBzZW5zZSB0byBtb3N0IHBlb3BsZS48XC9wPlxyXG5cclxuPHA+SWYgeW91IHJlbW92ZSBhbGwgc3BhY2VzIGZyb20gYSBzZW50ZW5jZSwgaXQgc3RpbGwgcmVtYWlucyBwZXJmZWN0bHkgcmVhZGFibGUsIHNlZSBmb3IgZXhhbXBsZTogJmxkcXVvO3RoaXNzZW50ZW5jZW1ha2VzcGVyZmVjdHNlbnNlJnJkcXVvOywgaG93ZXZlciBpZiB5b3UgY29tYmluZSB0aGVzZSB0d28gdGhpbmdzLCBmaXJzdCBzaHVmZmxpbmcsIHRoZW4gcmVtb3Zpbmcgc3BhY2VzLCB0aGluZ3MgZ2V0IGhhcmQuIFRoZSBmb2xsb3dpbmcgc2VudGVuY2UgaXMgaGFyZGVyIHRvIGRlY2lwaGVyOiAmbGRxdW87dGloc3NuZXRuY2VlbWthZXNwcmZlY2V0c2VzbmUmcmRxdW87LjxcL3A+XHJcblxyXG48cD5Zb3UmcnNxdW87cmUgZ2l2ZW4gYSBzZW50ZW5jZSBpbiB0aGUgbGFzdCBmb3JtLCB0b2dldGhlciB3aXRoIGEgZGljdGlvbmFyeSBvZiB2YWxpZCB3b3JkcyBhbmQgYXJlIGFza2VkIHRvIGRlY2lwaGVyIHRoZSB0ZXh0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBhIHN0cmluZyBzOiB0aGUgc2VudGVuY2UgdG8gZGVjaXBoZXIuIFRoZSBzZW50ZW5jZSBjb25zaXN0cyBvZiBsb3dlcmNhc2UgbGV0dGVycyBhbmQgaGFzIGEgbGVuZ3RoIG9mIGF0IGxlYXN0IDEgYW5kIGF0IG1vc3QgMSAwMDAgY2hhcmFjdGVycy48XC9saT5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIG4gd2l0aCAxICZsZTsgbiAmbGU7IDEwIDAwMDogdGhlIG51bWJlciBvZiB3b3JkcyBpbiB0aGUgZGljdGlvbmFyeS48XC9saT5cclxuXHQ8bGk+biBsaW5lcyB3aXRoIG9uZSB3b3JkIGVhY2guIEEgd29yZCBjb25zaXN0cyBvZiBsb3dlcmNhc2UgbGV0dGVycyBhbmQgaGFzIGEgbGVuZ3RoIG9mIGF0IGxlYXN0IDEgYW5kIGF0IG1vc3QgMTAwIGNoYXJhY3RlcnMuIEFsbCB0aGUgd29yZHMgYXJlIHVuaXF1ZS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0Y2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIHRoZSBkZWNpcGhlcmVkIHNlbnRlbmNlLCBpZiBpdCBpcyBwb3NzaWJsZSB0byB1bmlxdWVseSBkZWNpcGhlciBpdC4gT3RoZXJ3aXNlICZsZHF1bztpbXBvc3NpYmxlJnJkcXVvOyBvciAmbGRxdW87YW1iaWd1b3VzJnJkcXVvOywgZGVwZW5kaW5nIG9uIHdoaWNoIGlzIHRoZSBjYXNlLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d