시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 125 54 51 55.435%

문제

미친 과학자 창호는 어젯 밤 구재현을 납치해서, 구재현의 DNA를 추출했다. 인간의 DNA의 길이는 n이며, A, C, G, T 4개의 염색체로 구성되어 있다.

창호는 매일 자신을 놀리던 구재현을 좋아하지 않고, 대신 잘 생긴 콜드플레이의 크리스 마틴을 더 좋아한다. 이러한 경험을 토대로 창호는 이론을 하나 만들었다. 창호의 이론에 따르면, 구재현의 DNA와의 유사도가 최소인 DNA가 크리스 마틴의 DNA이다.

두 DNA의 유사도는, 두 DNA 간의 최장 공통 부분 수열(LCS)의 길이를 뜻한다. 어떠한 DNA의 부분 수열은, 그 DNA에서 0개 이상의 원소를 제거해서 만들 수 있는 또 다른 DNA 수열을 뜻한다. 두 DNA A, B의 최장 공통 부분 수열은, A와 B의 부분 수열이면서, 길이가 최대인 수열들을 뜻한다.

사실 잘 몰랐겠지만, 여러분도 지금 창호에게 납치되어 있다. 크리스 마틴의 DNA를 구하지 못하면 여러분에게 무슨 일이 일어날 지 모른다. 빨리 크리스 마틴의 DNA를 구하자. 가능한 답이 여러 가지일 경우, 아무거나 출력하면 된다.

입력

첫번째 줄에 인간 DNA의 길이 n이 주어진다. (1 ≤ n ≤ 10, 000) 이 주어진다.

이후 길이 n의 DNA 문자열이 주어진다. 문자열의 모든 문자는 A, C, G, T 넷 중 하나다.

출력

첫번째 줄에 최소 유사도 c 를 출력한다.

두번째 줄에 이를 만족하는 길이 n의 문자열을 출력한다. 가능한 답이 여러개 일 경우, 아무거나 출력하면 된다.

예제 입력 1

4
GACT

예제 출력 1

1
TCAG
W3sicHJvYmxlbV9pZCI6Ijc5NzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwNmNcdWI5YWNcdWMyYTQgXHViOWM4XHVkMmY0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWJiZjhcdWNlNWMgXHVhY2ZjXHVkNTU5XHVjNzkwIFx1Y2MzZFx1ZDYzOFx1YjI5NCBcdWM1YjRcdWM4MmYgXHViYzI0IFx1YWQ2Y1x1YzdhY1x1ZDYwNFx1Yzc0NCBcdWIwYTlcdWNlNThcdWQ1NzRcdWMxMWMsIFx1YWQ2Y1x1YzdhY1x1ZDYwNFx1Yzc1OCBETkFcdWI5N2MgXHVjZDk0XHVjZDljXHVkNTg4XHViMmU0LiBcdWM3NzhcdWFjMDRcdWM3NTggRE5BXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBuXHVjNzc0XHViYTcwLCBBLCBDLCBHLCBUIDRcdWFjMWNcdWM3NTggXHVjNWZjXHVjMGM5XHVjY2I0XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2MzZFx1ZDYzOFx1YjI5NCBcdWI5ZTRcdWM3N2MgXHVjNzkwXHVjMmUwXHVjNzQ0IFx1YjE4MFx1YjlhY1x1YjM1OCBcdWFkNmNcdWM3YWNcdWQ2MDRcdWM3NDQgXHVjODhiXHVjNTQ0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCwgXHViMzAwXHVjMmUwIFx1Yzc5OCBcdWMwZGRcdWFlMzQgXHVjZjVjXHViNGRjXHVkNTBjXHViODA4XHVjNzc0XHVjNzU4IFx1ZDA2Y1x1YjlhY1x1YzJhNCBcdWI5YzhcdWQyZjRcdWM3NDQgXHViMzU0IFx1Yzg4Ylx1YzU0NFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YWNiZFx1ZDVkOFx1Yzc0NCBcdWQxYTBcdWIzMDBcdWI4NWMgXHVjYzNkXHVkNjM4XHViMjk0IFx1Yzc3NFx1Yjg2MFx1Yzc0NCBcdWQ1NThcdWIwOTggXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LiBcdWNjM2RcdWQ2MzhcdWM3NTggXHVjNzc0XHViODYwXHVjNWQwIFx1YjUzMFx1Yjk3NFx1YmE3NCwgXHVhZDZjXHVjN2FjXHVkNjA0XHVjNzU4IEROQVx1YzY0MFx1Yzc1OCBcdWM3MjBcdWMwYWNcdWIzYzRcdWFjMDAgXHVjZDVjXHVjMThjXHVjNzc4IEROQVx1YWMwMCBcdWQwNmNcdWI5YWNcdWMyYTQgXHViOWM4XHVkMmY0XHVjNzU4IEROQVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIEROQVx1Yzc1OCBcdWM3MjBcdWMwYWNcdWIzYzRcdWIyOTQsIFx1YjQ1MCBETkEgXHVhYzA0XHVjNzU4IFx1Y2Q1Y1x1YzdhNSBcdWFjZjVcdWQxYjUgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNChMQ1MpXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWI3M2JcdWQ1NWNcdWIyZTQuIFx1YzViNFx1YjVhMFx1ZDU1YyBETkFcdWM3NTggXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc0MCwgXHVhZGY4IEROQVx1YzVkMFx1YzExYyAwXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWI5N2MgXHVjODFjXHVhYzcwXHVkNTc0XHVjMTFjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjYxMCBcdWIyZTRcdWI5NzggRE5BIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWI3M2JcdWQ1NWNcdWIyZTQuIFx1YjQ1MCBETkEgQSwgQlx1Yzc1OCBcdWNkNWNcdWM3YTUgXHVhY2Y1XHVkMWI1IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NDAsIEFcdWM2NDAgQlx1Yzc1OCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzc0XHViYTc0XHVjMTFjLCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVjZDVjXHViMzAwXHVjNzc4IFx1YzIxOFx1YzVmNFx1YjRlNFx1Yzc0NCBcdWI3M2JcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBhY1x1YzJlNCBcdWM3OTggXHViYWIwXHViNzkwXHVhY2EwXHVjOWMwXHViOWNjLCBcdWM1ZWNcdWI3ZWNcdWJkODRcdWIzYzQgXHVjOWMwXHVhZTA4IFx1Y2MzZFx1ZDYzOFx1YzVkMFx1YWM4YyBcdWIwYTlcdWNlNThcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWQwNmNcdWI5YWNcdWMyYTQgXHViOWM4XHVkMmY0XHVjNzU4IEROQVx1Yjk3YyBcdWFkNmNcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTU4XHViYTc0IFx1YzVlY1x1YjdlY1x1YmQ4NFx1YzVkMFx1YWM4YyBcdWJiMzRcdWMyYTggXHVjNzdjXHVjNzc0IFx1Yzc3Y1x1YzViNFx1YjBhMCBcdWM5YzAgXHViYWE4XHViOTc4XHViMmU0LiBcdWJlNjhcdWI5YWMgXHVkMDZjXHViOWFjXHVjMmE0IFx1YjljOFx1ZDJmNFx1Yzc1OCBETkFcdWI5N2MgXHVhZDZjXHVkNTU4XHVjNzkwLiBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViMmY1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWM3N2MgXHVhY2JkXHVjNmIwLCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNzc4XHVhYzA0IEROQVx1Yzc1OCBcdWFlMzhcdWM3NzQgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDEwLCAwMDApIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBcdWFlMzhcdWM3NzQgblx1Yzc1OCBETkEgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWJiMzhcdWM3OTBcdWIyOTQgQSwgQywgRywgVCBcdWIxMzcgXHVjOTExIFx1ZDU1OFx1YjA5OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q1Y1x1YzE4YyBcdWM3MjBcdWMwYWNcdWIzYzQgYyBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc3NFx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhZTM4XHVjNzc0IG5cdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzAwXHViMmE1XHVkNTVjIFx1YjJmNVx1Yzc3NCBcdWM1ZWNcdWI3ZWNcdWFjMWMgXHVjNzdjIFx1YWNiZFx1YzZiMCwgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzk3NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkROQSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIG1hZCBzY2llbnRpc3QgQnl0ZWFzYXIgd291bGQgbGlrZSB0byBnaXZlIGJpcnRoIHRvIGEgbmV3IGtpbmQgb2YgY3JlYXR1cmVzLiBGb3IgdGhpcywgaGUgaGFzIGRlY2lkZWQgdG8gbW9kaWZ5IHRoZSBnZW5vbWUgb2YgYSBCeXRlYW4gbW91c2UuPFwvcD5cclxuXHJcbjxwPkEgRE5BIGNhbiBiZSBkZXNjcmliZWQgYXMgYSBzZXF1ZW5jZSBudWNsZW90aWRlcyBkZW5vdGVkIGJ5IGxldHRlcnMgQSwgQywgRyBhbmQgVC4gQnl0ZWFzYXImcnNxdW87cyBtYXN0ZXIgcGxhbiBpcyBxdWl0ZSBzaW1wbGU6IHVzaW5nIHRoZSBETkEgb2YgYSBtb3VzZSwgaGUgaXMgZ29pbmcgdG8gY3JlYXRlIGEgbmV3IEROQSBvZiB0aGUgc2FtZSBsZW5ndGggdGhhdCBpcyBhcyBsaXR0bGUgc2ltaWxhciB0byB0aGUgbW91c2UmcnNxdW87cyBETkEgYXMgcG9zc2libGUuIFRoZSBzaW1pbGFyaXR5IG9mIHR3byBETkFzIGlzIHRoZSBsZW5ndGggb2YgdGhlaXIgbG9uZ2VzdCBjb21tb24gc3Vic2VxdWVuY2UuIFRoZSBsb25nZXN0IGNvbW1vbiBzdWJzZXF1ZW5jZSBvZiB0d28gd29yZHMgeCwgeSBpcyBkZWZpbmVkIGFzIHRoZSBsb25nZXN0IHdvcmQgdGhhdCBjYW4gYmUgb2J0YWluZWQgZnJvbSBlYWNoIG9mIHgsIHkgYnkgcmVtb3Zpbmcgc29tZSAocG9zc2libHkgbm9uZSkgbGV0dGVycyBmcm9tIGJvdGggd29yZHMuIChOb3RlIHRoYXQgdHdvIHdvcmRzIG1heSBoYXZlIHNldmVyYWwgbG9uZ2VzdCBjb21tb24gc3Vic2VxdWVuY2VzLiBGb3IgZXhhbXBsZSwgdGhlIGxvbmdlc3QgY29tbW9uIHN1YnNlcXVlbmNlcyBvZiB0aGUgd29yZHMgQ0FDQ0EgYW5kIENBQUMgYXJlOiBDQUEgYW5kIENBQy4pIFdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNvbXB1dGVzIHRoZSByZXF1ZXN0ZWQgRE5BLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgb25lIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAxMCAwMDApLCB0aGUgbGVuZ3RoIG9mIHRoZSBETkEgb2YgYSBCeXRlYW4gbW91c2UuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyBhIGRlc2NyaXB0aW9uIG9mIG51Y2xlb3RpZGVzIGluIHRoZSBETkE6IGEgc2VxdWVuY2Ugb2YgbiB1cHBlcmNhc2UgbGV0dGVycyBBLCBDLCBHLCBULjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiBvbmUgaW50ZWdlcjogdGhlIHNpbWlsYXJpdHkgb2YgdGhlIEJ5dGVhbiBtb3VzZSZyc3F1bztzIEROQSBhbmQgdGhlIEROQSBjb21wdXRlZCBieSB5b3VyIHByb2dyYW0uIFRoZSBzZWNvbmQgbGluZSBzaG91bGQgaG9sZCBhIHNlcXVlbmNlIG9mIG4gbGV0dGVycyBBLCBDLCBHLCBULiBUaGlzIHNob3VsZCBiZSBhIEROQSB0aGF0IGlzIGFzIGxpdHRsZSBzaW1pbGFyIHRvIHRoZSBETkEgZnJvbSB0aGUgaW5wdXQgYXMgcG9zc2libGUuIFNob3VsZCB0aGVyZSBiZSBtYW55IGNvcnJlY3QgYW5zd2VycywgeW91ciBwcm9ncmFtIG1heSBvdXRwdXQgYW55IG9uZSBvZiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==