시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVhZTAwXHVjNzkwXHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWMxMWVcdWFjZTAsIFx1YjJlOFx1YzViNCBcdWMwYWNcdWM3NzRcdWM3NTggXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU1YyBcdWJiMzhcdWM3YTVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI2MTAsIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWIyZThcdWM1YjRcdWM3NTggXHViYWE5XHViODVkXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVjNmQwXHViNzk4IFx1YmIzOFx1YzdhNVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWNkNWNcdWIzMDAgMTAwXHVhYzFjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWUwMFx1Yzc5MFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWI5N2MgXHViNGE0XHVjMTFlXHVhY2UwLCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjODFjXHVhYzcwXHVkNTVjIFx1YmIzOFx1YzdhNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM3YTVcdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjZDVjXHViMzAwIDEwMDBcdWFlMDBcdWM3OTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNjJjXHViYzE0XHViOTc4IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFjMWNcdWMyMTggbiAoMSAmbGU7IG4gJmxlOyAxMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHViMmU4XHVjNWI0XHViMjk0IFx1YzkxMVx1YmNmNVx1YjQxOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAsIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjZDVjXHViMzAwIDEwMFx1YWUwMFx1Yzc5MFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgXHVjNmQwXHViNzk4IFx1YmIzOFx1YzdhNVx1Yzc0NCBcdWM3MjBcdWM3N2NcdWQ1NThcdWFjOGMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVhZGY4IFx1YmIzOFx1YzdhNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YmIzOFx1YzdhNVx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7YW1iaWd1b3VzJnF1b3Q7XHViOTdjLCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NWMgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0ICZxdW90O2ltcG9zc2libGUmcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM2OTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJPYmZ1c2NhdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+SXQgaXMgYSB3ZWxsLWtub3duIGZhY3QgdGhhdCBpZiB5b3UgbWl4IHVwIHRoZSBsZXR0ZXJzIG9mIGEgd29yZCwgd2hpbGUgbGVhdmluZyB0aGUgXHVmYjAxcnN0IGFuZCBsYXN0IGxldHRlcnMgaW4gdGhlaXIgcGxhY2VzLCB3b3JkcyBzdGlsbCByZW1haW4gcmVhZGFibGUuIEZvciBleGFtcGxlLCB0aGUgc2VudGVuY2UgJmxkcXVvO3RpaHMgc25ldG5jZWUgbWthZXMgcHJmZWNldCBzZXNuZSZyZHF1bzssIG1ha2VzIHBlcmZlY3Qgc2Vuc2UgdG8gbW9zdCBwZW9wbGUuPFwvcD5cclxuXHJcbjxwPklmIHlvdSByZW1vdmUgYWxsIHNwYWNlcyBmcm9tIGEgc2VudGVuY2UsIGl0IHN0aWxsIHJlbWFpbnMgcGVyZmVjdGx5IHJlYWRhYmxlLCBzZWUgZm9yIGV4YW1wbGU6ICZsZHF1bzt0aGlzc2VudGVuY2VtYWtlc3BlcmZlY3RzZW5zZSZyZHF1bzssIGhvd2V2ZXIgaWYgeW91IGNvbWJpbmUgdGhlc2UgdHdvIHRoaW5ncywgZmlyc3Qgc2h1ZmZsaW5nLCB0aGVuIHJlbW92aW5nIHNwYWNlcywgdGhpbmdzIGdldCBoYXJkLiBUaGUgZm9sbG93aW5nIHNlbnRlbmNlIGlzIGhhcmRlciB0byBkZWNpcGhlcjogJmxkcXVvO3RpaHNzbmV0bmNlZW1rYWVzcHJmZWNldHNlc25lJnJkcXVvOy48XC9wPlxyXG5cclxuPHA+WW91JnJzcXVvO3JlIGdpdmVuIGEgc2VudGVuY2UgaW4gdGhlIGxhc3QgZm9ybSwgdG9nZXRoZXIgd2l0aCBhIGRpY3Rpb25hcnkgb2YgdmFsaWQgd29yZHMgYW5kIGFyZSBhc2tlZCB0byBkZWNpcGhlciB0aGUgdGV4dC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3RjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggYSBzdHJpbmcgczogdGhlIHNlbnRlbmNlIHRvIGRlY2lwaGVyLiBUaGUgc2VudGVuY2UgY29uc2lzdHMgb2YgbG93ZXJjYXNlIGxldHRlcnMgYW5kIGhhcyBhIGxlbmd0aCBvZiBhdCBsZWFzdCAxIGFuZCBhdCBtb3N0IDEgMDAwIGNoYXJhY3RlcnMuPFwvbGk+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggYW4gaW50ZWdlciBuIHdpdGggMSAmbGU7IG4gJmxlOyAxMCAwMDA6IHRoZSBudW1iZXIgb2Ygd29yZHMgaW4gdGhlIGRpY3Rpb25hcnkuPFwvbGk+XHJcblx0PGxpPm4gbGluZXMgd2l0aCBvbmUgd29yZCBlYWNoLiBBIHdvcmQgY29uc2lzdHMgb2YgbG93ZXJjYXNlIGxldHRlcnMgYW5kIGhhcyBhIGxlbmd0aCBvZiBhdCBsZWFzdCAxIGFuZCBhdCBtb3N0IDEwMCBjaGFyYWN0ZXJzLiBBbGwgdGhlIHdvcmRzIGFyZSB1bmlxdWUuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCB0aGUgZGVjaXBoZXJlZCBzZW50ZW5jZSwgaWYgaXQgaXMgcG9zc2libGUgdG8gdW5pcXVlbHkgZGVjaXBoZXIgaXQuIE90aGVyd2lzZSAmbGRxdW87aW1wb3NzaWJsZSZyZHF1bzsgb3IgJmxkcXVvO2FtYmlndW91cyZyZHF1bzssIGRlcGVuZGluZyBvbiB3aGljaCBpcyB0aGUgY2FzZS48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==