시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB2805101683937.422%

문제

스파이들은 사령부와 통신하기 위해서 SMTP(비밀 메시지 전송 프로토콜)를 사용해 비밀 회선으로 전자 메시지를 보낸다. 메시지가 적들에 의해 조작되어 보내진 것이 아닌 진짜 메시지라는 것을 표시하기 위해 모든 메시지는 회선에 노이즈가 있었거나 발신 측에서 손을 떨면서 메시지를 보낸 것처럼 변형되는데, 이 변형 알고리즘은 메시지를 가로채는 자들이 우연히 변형 규칙을 흉내 낼 수 없을 정도로 정교하다. 또한 요원들의 머리에 총구가 겨눠져 강제로 메시지를 말한 경우 간단히 실수를 의도적으로 넣어 이 메시지가 강제로 쓰인 메시지라는 것을 알려줄 수 있다.

알고리즘대로 정확하게 변형된 메시지는 각 문자가 세 번째 등장할 때 한 번 더 문자가 삽입된다. 예를 들면 요원이 "HELLOTHEREWELLBEFINE" 라는 메시지를 보내고 싶어 했다면 "HELLOTHEREEWELLLBEFINEE" 는 정확한 변형이다. 몇 년 동안 이 메시지들의 진짜 여부는 고도로 훈련된 원숭이들이 판별해내었다. 그러나 사령부에 도착하는 메시지들의 양이 많이 늘어나면서 이 작업을 자동으로 처리해주는 프로그램을 고안하기로 하였다.

입력

첫째 줄에 100 이하의 테스트 케이스의 개수가 주어진다. 그리고 각 테스트 케이스마다

  • 대문자로만 이루어진 10만자 이하의 문자열 M이 한 줄에 주어진다. 이 문자열은 검사해야할 메시지다.

출력

테스트 케이스마다

  • 메시지 M이 진짜 메시지면 “OK”를, 가짜 메시지면 “FAKE”를 한 줄에 출력한다.

예제 입력 1

3
BAPC
AABA
ABCABCBBAAACC

예제 출력 1

OK
FAKE
OK
W3sicHJvYmxlbV9pZCI6IjkzMjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzRcdWM5ZGMgXHViYTU0XHVjMmRjXHVjOWMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyYTRcdWQzMGNcdWM3NzRcdWI0ZTRcdWM3NDAgXHVjMGFjXHViODM5XHViZDgwXHVjNjQwIFx1ZDFiNVx1YzJlMFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgU01UUChcdWJlNDRcdWJjMDAgXHViYTU0XHVjMmRjXHVjOWMwIFx1YzgwNFx1YzFhMSZuYnNwO1x1ZDUwNFx1Yjg1Y1x1ZDFhMFx1Y2Y1YylcdWI5N2MgXHVjMGFjXHVjNmE5XHVkNTc0IFx1YmU0NFx1YmMwMCBcdWQ2OGNcdWMxMjBcdWM3M2NcdWI4NWMgXHVjODA0XHVjNzkwIFx1YmE1NFx1YzJkY1x1YzljMFx1Yjk3YyBcdWJjZjRcdWIwYjhcdWIyZTQuIFx1YmE1NFx1YzJkY1x1YzljMFx1YWMwMCBcdWM4MDFcdWI0ZTRcdWM1ZDAgXHVjNzU4XHVkNTc0IFx1Yzg3MFx1Yzc5MVx1YjQxOFx1YzViNCZuYnNwO1x1YmNmNFx1YjBiNFx1YzljNCBcdWFjODNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzljNFx1YzlkYyBcdWJhNTRcdWMyZGNcdWM5YzBcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1ZDQ1Y1x1YzJkY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViYWE4XHViNGUwIFx1YmE1NFx1YzJkY1x1YzljMFx1YjI5NCBcdWQ2OGNcdWMxMjBcdWM1ZDAgXHViMTc4XHVjNzc0XHVjOTg4XHVhYzAwIFx1Yzc4OFx1YzVjOFx1YWM3MFx1YjA5OCBcdWJjMWNcdWMyZTAmbmJzcDtcdWNlMjFcdWM1ZDBcdWMxMWMgXHVjMTkwXHVjNzQ0IFx1YjVhOFx1YmE3NFx1YzExYyBcdWJhNTRcdWMyZGNcdWM5YzBcdWI5N2MgXHViY2Y0XHViMGI4Jm5ic3A7XHVhYzgzXHVjYzk4XHViN2ZjIFx1YmNjMFx1ZDYxNVx1YjQxOFx1YjI5NFx1YjM3MCwmbmJzcDtcdWM3NzQgXHViY2MwXHVkNjE1IFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1Yzc0MCBcdWJhNTRcdWMyZGNcdWM5YzBcdWI5N2MgXHVhYzAwXHViODVjXHVjYzQ0XHViMjk0IFx1Yzc5MFx1YjRlNFx1Yzc3NCBcdWM2YjBcdWM1ZjBcdWQ3ODgmbmJzcDtcdWJjYzBcdWQ2MTUmbmJzcDtcdWFkZGNcdWNlNTlcdWM3NDQmbmJzcDtcdWQ3NDlcdWIwYjQmbmJzcDtcdWIwYmMgXHVjMjE4IFx1YzVjNlx1Yzc0NCBcdWM4MTVcdWIzYzRcdWI4NWMgXHVjODE1XHVhZDUwXHVkNTU4XHViMmU0LiBcdWI2MTBcdWQ1NWMgXHVjNjk0XHVjNmQwXHViNGU0XHVjNzU4IFx1YmEzOFx1YjlhY1x1YzVkMCBcdWNkMWRcdWFkNmNcdWFjMDAgXHVhY2E4XHViMjIwXHVjODM4IFx1YWMxNVx1YzgxY1x1Yjg1YyBcdWJhNTRcdWMyZGNcdWM5YzBcdWI5N2MgXHViOWQwXHVkNTVjIFx1YWNiZFx1YzZiMCBcdWFjMDRcdWIyZThcdWQ3ODgmbmJzcDtcdWMyZTRcdWMyMThcdWI5N2MgXHVjNzU4XHViM2M0XHVjODAxXHVjNzNjXHViODVjIFx1YjEyM1x1YzViNCBcdWM3NzQgXHViYTU0XHVjMmRjXHVjOWMwXHVhYzAwIFx1YWMxNVx1YzgxY1x1Yjg1YyBcdWM0ZjBcdWM3NzggXHViYTU0XHVjMmRjXHVjOWMwXHViNzdjXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM1NGNcdWI4MjRcdWM5MDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHViMzAwXHViODVjIFx1YzgxNVx1ZDY1NVx1ZDU1OFx1YWM4YyBcdWJjYzBcdWQ2MTVcdWI0MWMgXHViYTU0XHVjMmRjXHVjOWMwXHViMjk0IFx1YWMwMSBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWI0ZjFcdWM3YTVcdWQ1NjAgXHViNTRjIFx1ZDU1YyBcdWJjODggXHViMzU0IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWMwYmRcdWM3ODVcdWI0MWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgXHVjNjk0XHVjNmQwXHVjNzc0ICZxdW90Ozxjb2RlPkhFTExPVEhFUkVXRUxMQkVGSU5FPFwvY29kZT4mcXVvdDsgXHViNzdjXHViMjk0IFx1YmE1NFx1YzJkY1x1YzljMFx1Yjk3YyBcdWJjZjRcdWIwYjRcdWFjZTAgXHVjMmY2XHVjNWI0Jm5ic3A7XHVkNTg4XHViMmU0XHViYTc0ICZxdW90Ozxjb2RlPkhFTExPVEhFUkVFV0VMTExCRUZJTkVFPFwvY29kZT4mcXVvdDsgXHViMjk0IFx1YzgxNVx1ZDY1NVx1ZDU1YyBcdWJjYzBcdWQ2MTVcdWM3NzRcdWIyZTQuIFx1YmE4NyZuYnNwO1x1YjE0NCBcdWIzZDlcdWM1NDggXHVjNzc0IFx1YmE1NFx1YzJkY1x1YzljMFx1YjRlNFx1Yzc1OCBcdWM5YzRcdWM5ZGMgXHVjNWVjXHViZDgwXHViMjk0IFx1YWNlMFx1YjNjNFx1Yjg1YyBcdWQ2YzhcdWI4MjhcdWI0MWMgXHVjNmQwXHVjMjJkXHVjNzc0XHViNGU0XHVjNzc0IFx1ZDMxMFx1YmNjNFx1ZDU3NFx1YjBiNFx1YzVjOFx1YjJlNC4gXHVhZGY4XHViN2VjXHViMDk4IFx1YzBhY1x1YjgzOVx1YmQ4MFx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NThcdWIyOTQgXHViYTU0XHVjMmRjXHVjOWMwXHViNGU0XHVjNzU4IFx1YzU5MVx1Yzc3NCBcdWI5Y2VcdWM3NzQgXHViMjk4XHVjNWI0XHViMDk4XHViYTc0XHVjMTFjIFx1Yzc3NCBcdWM3OTFcdWM1YzVcdWM3NDQgXHVjNzkwXHViM2Q5XHVjNzNjXHViODVjIFx1Y2M5OFx1YjlhY1x1ZDU3NFx1YzhmY1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVhY2UwXHVjNTQ4XHVkNTU4XHVhZTMwXHViODVjIFx1ZDU1OFx1YzYwMFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgMTAwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNDxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YjMwMFx1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgMTBcdWI5Y2NcdWM3OTAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNCBNXHVjNzc0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAmbmJzcDtcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVhYzgwXHVjMGFjXHVkNTc0XHVjNTdjXHVkNTYwIFx1YmE1NFx1YzJkY1x1YzljMFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQ8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJhNTRcdWMyZGNcdWM5YzAgTVx1Yzc3NCZuYnNwO1x1YzljNFx1YzlkYyBcdWJhNTRcdWMyZGNcdWM5YzBcdWJhNzQmbmJzcDsmbGRxdW87PGNvZGU+T0s8XC9jb2RlPiZyZHF1bztcdWI5N2MsIFx1YWMwMFx1YzlkYyBcdWJhNTRcdWMyZGNcdWM5YzBcdWJhNzQmbmJzcDsmbGRxdW87PGNvZGU+RkFLRTxcL2NvZGU+JnJkcXVvO1x1Yjk3YyBcdWQ1NWMgXHVjOTA0XHVjNWQwJm5ic3A7XHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiOTMyNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdlbnVpbmUgTWVzc2FnZXMiLCJkZXNjcmlwdGlvbiI6IjxwPlRvIGNvbW11bmljYXRlIHdpdGggSFEsIHNwaWVzIHNlbmQgZWxlY3Ryb25pYyBtZXNzYWdlcyBvdmVyIHRoZSBJbmZvcm1hdGlvbiBTdXBlcmhpZ2h3YXkgdXNpbmcgYSBwcm90b2NvbCBjYWxsZWQgU01UUCAoU2VjcmV0IE1lc3NhZ2UgVHJhbnNsYXRpb24gUHJvdG9jb2wpLiBUbyBlbnN1cmUgdGhhdCB0aGVzZSBtZXNzYWdlcyBhcmUgZ2VudWluZSBhbmQgaGF2ZSBub3QsIGZvciBleGFtcGxlLCBiZWVuIHNlbnQgYnkgYW4gZXZpbCBhZHZlcnNhcnksIGV2ZXJ5IG1lc3NhZ2UgJm5ic3A7aXMgbW9kaVx1ZmIwMWVkIGluIHN1Y2ggYSB3YXkgdGhhdCBpdCBsb29rcyBsaWtlIHRoZXJlIHdhcyBub2lzZSBvbiB0aGUgY29tbXVuaWNhdGlvbiBsaW5lLCBvciB0aGUgc2VuZGVyIHdhcyB2ZXJ5IG5lcnZvdXMgd2hpbGUgdHlwaW5nIHRoZSBtZXNzYWdlLiBIb3dldmVyLCB0aGUgbXV0YXRpb24gYWxnb3JpdGhtIGlzIGNhcmVmdWxseSBjcmFmdGVkIHN1Y2ggdGhhdCBhbiBpbXBvc3RlciBpcyB2ZXJ5IHVubGlrZWx5IHRvIHJlcGxpY2F0ZSB0aGlzIHBhcnRpY3VsYXIgZWZmZWN0LCBhbmQgaXQgaXMgYWxzbyBlYXN5IGZvciBcdWZiMDFlbGQgYWdlbnRzIHRvIGludGVudGlvbmFsbHkgaW5zZXJ0IGEgJmxkcXVvO21pc3Rha2UmcmRxdW87IGlmIHRoZXkgYXJlIGZvcmNlZCBhdCBndW5wb2ludCB0byB3cml0ZSBhIG1lc3NhZ2UuPFwvcD5cclxuXHJcbjxwPkluIGEgY29ycmVjdGx5IG11dGF0ZWQgbWVzc2FnZSBldmVyeSB0aGlyZCBhcHBlYXJhbmNlIG9mIGVhY2ggbGV0dGVyIGlzIGR1cGxpY2F0ZWQuIEZvciBleGFtcGxlLCAmbGRxdW87PGNvZGU+SEVMTE9USEVSRUVXRUxMTEJFRklORUU8XC9jb2RlPiZyZHF1bzsgaXMgdGhlIGNvcnJlY3QgbXV0YXRpb24gaWYgdGhlIGFnZW50IHdhbnRlZCB0byBzZW5kICZsZHF1bzs8Y29kZT5IRUxMT1RIRVJFV0VMTEJFRklORTxcL2NvZGU+JnJkcXVvOy4gRm9yIHRoZSBwYXN0IGZldyBkZWNhZGVzIHRoZXNlIG1lc3NhZ2VzIGhhdmUgYmVlbiBjaGVja2VkIGJ5IGhpZ2hseSB0cmFpbmVkIG1vbmtleXMuIFNpbmNlIHRoZSBudW1iZXIgb2YgbWVzc2FnZXMgYXJyaXZpbmcgYXQgdGhlIEhRIGhhcyBncmVhdGx5IGluY3JlYXNlZCByZWNlbnRseSwgdGhleSBoYXZlIHRhc2tlZCB5b3Ugd2l0aCB3cml0aW5nIGFuIGF1dG9tYXRlZCBwcm9ncmFtIHRoYXQgY2FuIGFsZXJ0IEhRIHdoZW4gYSBtZXNzYWdlIGlzIGRlXHVmYjAxbml0ZWx5IGZha2UgYW5kIG5vdCBzZW50IGJ5IG91ciBhZ2VudC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhIHN0cmluZyBNICgxICZsZTsgbGVuZ3RoKE0pICZsZTsgMTAwIDAwMCksIGNvbnNpc3Rpbmcgb2YgdXBwZXJjYXNlIGxldHRlcnMgb25seTogdGhlIGluY29taW5nIG1lc3NhZ2UgdG8gY2hlY2suPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggZWl0aGVyICZsZHF1bzs8Y29kZT5PSzxcL2NvZGU+JnJkcXVvOyBvciAmbGRxdW87PGNvZGU+RkFLRTxcL2NvZGU+JnJkcXVvOywgaW5kaWNhdGluZyB3aGV0aGVyIG9yIG5vdCB0aGUgbWVzc2FnZSBNIGNhbiBiZSB0aGUgcmVzdWx0IG9mIGEgY29ycmVjdGx5IGFwcGxpZWQgbXV0YXRpb24gdG8gc29tZSAodW5zcGVjaVx1ZmIwMWVkKSBvcmlnaW5hbCBtZXNzYWdlLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2013 Preliminaries G번