시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 30 9 4 25.000%

문제

동일이는 어느 날 혼자서 할 수 있는 재미있는 놀이 하나를 생각해냈다.

이 놀이는 N개의 알파벳 소문자로 이루어진 문자열 하나로 시작된다.

동일이는 이 문자열의 임의의 두 글자를 서로 바꿀 수 있다. 이 행동은 0번 혹은 그 이상 원하는 할 수 있다.

목표는 사전순으로 가장 앞선 문자열을 만드는 것이다.

하지만 몇 번 게임을 하던 동일이는 아무래도 게임이 너무 쉽다고 생각하여 규칙 하나를 추가했다.

결과물이 될 문자열의 각 위치마다, 그 위치에 올 수 있는 문자를 정해 둔다.

예시는 다음과 같다.

  • 첫 글자는 a 또는 b가 되어야 한다.
  • 두 번째 글자는 b 또는 c가 되어야 한다.

이 규칙은 최종 결과물이 될 문자열에만 성립하며, 놀이 도중 만들어지는 문자열은 위의 규칙을 따르지 않아도 상관없다.

위의 규칙을 추가하자 놀이가 너무 어려워졌다.

동일이를 도와 규칙을 잘 지키면서 사전순으로 가장 앞서는 문자열이 무엇인지 찾아주도록 하자.

입력

첫 줄에 테스트 케이스의 수 T가 주어진다. ( 1 ≤ T ≤ 100 )

각 테스트 케이스의 첫 줄엔 놀이에 사용할 초기 문자열 S가 주어진다.

문자열은 N개의 알파벳 소문자로 이루어져 있다. ( 1 ≤ N ≤ 100 )

이어 N줄에 걸쳐 문자열 Ci가 주어진다. Ci는 Li개의 문자를 포함하며, 결과물의 i번째 글자에 올 수 있는 문자들의 목록이다. ( 1 ≤ Li ≤ 5 )

Ci에 등장하는 모든 문자는 초기 문자열 S에 최소한 한 번 이상 등장한다.

출력

각 테스트 케이스마다, 규칙을 지키며 만들 수 있는 사전순으로 가장 앞선 문자열을 출력한다. 만약 규칙대로 만들 수 있는 문자열이 존재하지 않는다면 NO SOLUTION을 출력한다.

예제 입력 1

2
abcde
abcde
a
abcde
abcde
abcde
abcde
ab
ab
ab
abcde
abcde

예제 출력 1

bacde
NO SOLUTION
W3sicHJvYmxlbV9pZCI6Ijk1NTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMTRcdWFmYjhcdWFlMzAgXHViMTgwXHVjNzc0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzZDlcdWM3N2NcdWM3NzRcdWIyOTQgXHVjNWI0XHViMjkwIFx1YjBhMCBcdWQ2M2NcdWM3OTBcdWMxMWMgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjN2FjXHViYmY4XHVjNzg4XHViMjk0IFx1YjE4MFx1Yzc3NCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjMGRkXHVhYzAxXHVkNTc0XHViMGM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHViMTgwXHVjNzc0XHViMjk0IE5cdWFjMWNcdWM3NTggXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0IFx1ZDU1OFx1YjA5OFx1Yjg1YyBcdWMyZGNcdWM3OTFcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNkOVx1Yzc3Y1x1Yzc3NFx1YjI5NCBcdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWI0NTAgXHVhZTAwXHVjNzkwXHViOTdjIFx1YzExY1x1Yjg1YyBcdWJjMTRcdWFmYzAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1ZDU4OVx1YjNkOVx1Yzc0MCAwXHViYzg4IFx1ZDYzOVx1Yzc0MCBcdWFkZjggXHVjNzc0XHVjMGMxIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE5XHVkNDVjXHViMjk0IFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjMDBcdWM3YTUgXHVjNTVlXHVjMTIwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NThcdWM5YzBcdWI5Y2MgXHViYTg3IFx1YmM4OCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHViMzU4IFx1YjNkOVx1Yzc3Y1x1Yzc3NFx1YjI5NCBcdWM1NDRcdWJiMzRcdWI3OThcdWIzYzQgXHVhYzhjXHVjNzg0XHVjNzc0IFx1YjEwOFx1YmIzNCBcdWMyN2RcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTU4XHVjNWVjIFx1YWRkY1x1Y2U1OSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjZDk0XHVhYzAwXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjYjBcdWFjZmNcdWJiM2NcdWM3NzQgXHViNDIwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFjMDEgXHVjNzA0XHVjZTU4XHViOWM4XHViMmU0LCBcdWFkZjggXHVjNzA0XHVjZTU4XHVjNWQwIFx1YzYyYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWM4MTVcdWQ1NzQgXHViNDU0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWMyZGNcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWNjYWIgXHVhZTAwXHVjNzkwXHViMjk0IGEgXHViNjEwXHViMjk0IGJcdWFjMDAgXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWFlMDBcdWM3OTBcdWIyOTQgYiBcdWI2MTBcdWIyOTQgY1x1YWMwMCBcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Yzc3NCBcdWFkZGNcdWNlNTlcdWM3NDAgXHVjZDVjXHVjODg1IFx1YWNiMFx1YWNmY1x1YmIzY1x1Yzc3NCBcdWI0MjAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwXHViOWNjIFx1YzEzMVx1YjliZFx1ZDU1OFx1YmE3MCwgXHViMTgwXHVjNzc0IFx1YjNjNFx1YzkxMSBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM5YzBcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YzcwNFx1Yzc1OCBcdWFkZGNcdWNlNTlcdWM3NDQgXHViNTMwXHViOTc0XHVjOWMwIFx1YzU0YVx1YzU0NFx1YjNjNCBcdWMwYzFcdWFkMDBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZGNcdWNlNTlcdWM3NDQgXHVjZDk0XHVhYzAwXHVkNTU4XHVjNzkwIFx1YjE4MFx1Yzc3NFx1YWMwMCBcdWIxMDhcdWJiMzQgXHVjNWI0XHViODI0XHVjNmNjXHVjODRjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzZDlcdWM3N2NcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwIFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWM3OTggXHVjOWMwXHVkMGE0XHViYTc0XHVjMTFjIFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjMDBcdWM3YTUgXHVjNTVlXHVjMTFjXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWJiMzRcdWM1YzdcdWM3NzhcdWM5YzAgXHVjYzNlXHVjNTQ0XHVjOGZjXHViM2M0XHViODVkIFx1ZDU1OFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICggMSAmbGU7IFQgJmxlOyAxMDAgKTxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQ0IFx1YjE4MFx1Yzc3NFx1YzVkMCBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjZDA4XHVhZTMwIFx1YmIzOFx1Yzc5MFx1YzVmNCBTXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIE5cdWFjMWNcdWM3NTggXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAoIDEgJmxlOyBOICZsZTsgMTAwICk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjNWI0IE5cdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YmIzOFx1Yzc5MFx1YzVmNCBDPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIEM8c3ViPmk8XC9zdWI+XHViMjk0IEw8c3ViPmk8XC9zdWI+XHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWJhNzAsIFx1YWNiMFx1YWNmY1x1YmIzY1x1Yzc1OCBpXHViYzg4XHVjOWY4IFx1YWUwMFx1Yzc5MFx1YzVkMCBcdWM2MmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWI0ZTRcdWM3NTggXHViYWE5XHViODVkXHVjNzc0XHViMmU0LiAoIDEgJmxlOyBMPHN1Yj5pPFwvc3ViPiAmbGU7IDUgKTxcL3A+XHJcblxyXG48cD5DPHN1Yj5pPFwvc3ViPlx1YzVkMCBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQgXHViYWE4XHViNGUwIFx1YmIzOFx1Yzc5MFx1YjI5NCBcdWNkMDhcdWFlMzAgXHViYjM4XHVjNzkwXHVjNWY0IFNcdWM1ZDAgXHVjZDVjXHVjMThjXHVkNTVjIFx1ZDU1YyBcdWJjODggXHVjNzc0XHVjMGMxIFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YzljMFx1ZDBhNFx1YmE3MCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWM4MDRcdWMyMWNcdWM3M2NcdWI4NWMgXHVhYzAwXHVjN2E1IFx1YzU1ZVx1YzEyMCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVhZGRjXHVjZTU5XHViMzAwXHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHViYTc0IE5PIFNPTFVUSU9OXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5NTUxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIFN3YXBwaW5nIEdhbWUiLCJkZXNjcmlwdGlvbiI6IjxwPkxhc3QgeWVhciB5b3UgaW52ZW50ZWQgYSBnYW1lIHdoaWNoIGNhbiBiZSBwbGF5ZWQgdXNpbmcgYSBib2FyZCBhbmQgYSBkaWUgKHNpbmd1bGFyIG9mIGRpY2UpLCB0aGlzIHllYXIgeW91IGludmVudGVkIGFub3RoZXIgbmV3IGdhbWUgd2hpY2ggY2FuIGJlIHBsYXllZCB1c2luZyBhIHNpbmdsZSBzdHJpbmcgb2Ygc29tZSBsZXR0ZXJzLjxcL3A+XHJcblxyXG48cD5UaGUgZ2FtZSBzdGFydHMgd2l0aCBhIHN0cmluZyBvZiBOIGxvd2VyIGNhc2UgRW5nbGlzaCBsZXR0ZXJzICgmbHNxdW87YSZyc3F1bzsgdG8gJmxzcXVvO3omcnNxdW87KSwgYW5kIHlvdSBjYW4gb25seSBzd2FwIHR3byBkaWZmZXJlbnQgY2hhcmFjdGVycyBpbiB0aGlzIHN0cmluZywgYW5kIHlvdSBjYW4gbWFrZSB0aGlzIHN0ZXAgemVybyBvciBtb3JlIHRpbWVzLiBZb3VyIGdvYWwgaXMgdG8gcmVhY2ggdGhlIGxleGljb2dyYXBoaWNhbGx5IHNtYWxsZXN0IHN0cmluZyBhZnRlciBkb2luZyB6ZXJvIG9yIG1vcmUgbW92ZXMuPFwvcD5cclxuXHJcbjxwPkJ1dCB0aGVyZSBhcmUgc29tZSBjb25zdHJhaW50cyBvbiB0aGUgZmluYWwgc3RyaW5nLiBGb3IgZWFjaCBwb3NpdGlvbiwgaXQgbXVzdCBiZSBhIGxldHRlciBvZiBzb21lIGdpdmVuIGxldHRlcnMgKHRoZSBnaXZlbiBsZXR0ZXJzIGFyZSBub3QgbmVjZXNzYXJ5IHRoZSBzYW1lIGZvciBlYWNoIHBvc2l0aW9uKS4gRm9yIGV4YW1wbGUsIHRoZSBmaXJzdCBsZXR0ZXIgbXVzdCBiZSAmbHNxdW87YSZyc3F1bzsgb3IgJmxzcXVvO2ImcnNxdW87LCB0aGUgc2Vjb25kIGxldHRlciBtdXN0IGJlICZsc3F1bztiJnJzcXVvOyBvciAmbHNxdW87YyZyc3F1bzssIGFuZCBzbyBvbi48XC9wPlxyXG5cclxuPHA+Tm90ZSB0aGF0IHRoZXNlIGNvbnN0cmFpbnRzIGFyZSBvbiB0aGUgZmluYWwgc3RyaW5nIG9ubHksIHdoaWNoIG1lYW5zIHlvdSBjYW4gbWFrZSBtb3ZlcyB3aGljaCBjYXVzZSBpbnZhbGlkIHN0cmluZ3MgdG8gcmVhY2ggYSB2YWxpZCBzdHJpbmcgYWZ0ZXIgc29tZSBtb3JlIG1vdmVzLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgaW5pdGlhbCBzdHJpbmcgYW5kIHRoZSBjb25zdHJhaW50cyBvbiBlYWNoIHBvc2l0aW9uLCB5b3VyIHRhc2sgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRvIGZpbmQgdGhlIGxleGljb2dyYXBoaWNhbGx5IHNtYWxsZXN0IHZhbGlkIHN0cmluZyBhZnRlciBtYWtpbmcgemVybyBvciBtb3JlIG1vdmVzLjxcL3A+XHJcblxyXG48cD5Ob3RlOiBXaGVuIGNvbXBhcmluZyB0d28gZGlmZmVyZW50IHN0cmluZ3Mgb2YgdGhlIHNhbWUgbGVuZ3RoLCB0aGUgbGV4aWNvZ3JhcGhpY2FsbHkgc21hbGxlciBvbmUgaXMgdGhlIG9uZSB3aXRoIGEgc21hbGxlciBsZXR0ZXIgb24gdGhlIGZpcnN0IHBsYWNlIHdoZXJlIHRoZXkgZGlmZmVyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIHdpbGwgYmUgdGVzdGVkIG9uIG9uZSBvciBtb3JlIHRlc3QgY2FzZXMuIFRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCB3aWxsIGJlIGEgc2luZ2xlIGludGVnZXIgVCwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzICgxICZsZTsgVCAmbGU7IDEwMCkuIEZvbGxvd2VkIGJ5IHRoZSB0ZXN0IGNhc2VzLCBlYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0aGUgaW5pdGlhbCBzdHJpbmcgUyB3aGljaCBjb25zaXN0cyBvZiBOIGxvd2VyIGNhc2UgRW5nbGlzaCBsZXR0ZXJzICgxICZsZTsgTiAmbGU7IDEwMCkuIEZvbGxvd2VkIGJ5IE4gbGluZXMgZWFjaCBsaW5lIGNvbnRhaW5zIGEgc3RyaW5nIEM8c3ViPmk8XC9zdWI+IHdoaWNoIGNvbnNpc3RzIG9mIEw8c3ViPmk8XC9zdWI+IGRpc3RpbmN0IGxvd2VyIGNhc2UgRW5nbGlzaCBsZXR0ZXJzICgxICZsZTsgTDxzdWI+aTxcL3N1Yj4gJmxlOyA1KSB3aGljaCBhcmUgdGhlIHZhbGlkIGxldHRlcnMgZm9yIHRoZSBpLXRoIHBvc2l0aW9uIGluIHRoZSBmaW5hbCBzdHJpbmcuIEVhY2ggbGV0dGVyIGluIGVhY2ggQzxzdWI+aTxcL3N1Yj4gd2lsbCBhcHBlYXIgYXQgbGVhc3Qgb25jZSBpbiBTLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgb24gYSBzaW5nbGUgbGluZSB0aGUgbGV4aWNvZ3JhcGhpY2FsbHkgc21hbGxlc3QgdmFsaWQgc3RyaW5nIHlvdSBjYW4gZ2V0IGFmdGVyIHplcm8gb3IgbW9yZSBtb3Zlcy4gSWYgdGhlcmUgaXMgbm8gc3VjaCB2YWxpZCBzdHJpbmcgcHJpbnQgJmxzcXVvO05PIFNPTFVUSU9OJnJzcXVvOyAod2l0aG91dCB0aGUgcXVvdGVzKS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=