시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB133654043146.146%

문제

암호화 방식 중에는 소수를 이용하는 것들이 많다. 보통은 매우 큰 두 개의 소수를 선택하고, 두 소수를 곱한 값을 암호화에서의 키로 사용하고는 한다. 이러한 방법이 좋은 이유는 일반적으로 매우 큰 수를 소인수분해 하는 것이 어렵기 때문이다.

소수를 택할 때 큰 수를 택하면, 이 둘을 곱해서 얻어지는 키 값도 커지게 된다. 하지만 그 반대는 성립하지 않을 수도 있다. 즉, 키 값이 매우 큰 경우에도 이를 소인수분해 하는 것은 쉬울 수도 있다.

따라서 암호문이 크랙되지 않도록 하기 위해서는, 키 값이 적절히 큰 수들의 곱으로 이루어져 있는지를 확인해야 할 필요가 있다. 키 값 K와 정수 L이 주어졌을 때, K를 인수분해 했을 때, 항상 L 이상의 값으로만 이루어져 있는지를 확인하고 싶다. 물론 인수분해 할 때 1로 나누는 경우는 고려하지 않는다.

예를 들어 K=143인 경우, 이는 11과 13의 곱으로 이루어져 있다. 즉, 이를 인수분해 하는 방법은 11×13, 143의 두 가지 경우뿐이다. 따라서 L이 11일 경우에는 인수분해 했을 때 나온 수들이 모두 L 이상이므로 좋은 경우지만, L이 12이상일 경우에는 좋은 암호가 아니다.

K와 L이 주어졌을 때, 좋은 암호인지 판단하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 K, L이 주어진다.

출력

좋은 암호인 경우에는 GOOD을 출력한다. 나쁜 암호일 경우에는 BAD를 출력하고, K의 가장 작은 (1 아닌) 인수를 출력한다.

제한

  • 4 ≤ K ≤ 10100
  • 2 ≤ L ≤ 1,000,000

예제 입력 1

143 11

예제 출력 1

GOOD

예제 입력 2

143 12

예제 출력 2

BAD 11
W3sicHJvYmxlbV9pZCI6IjIwNjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4OGJcdWM3NDAgXHVjNTU0XHVkNjM4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NTRcdWQ2MzhcdWQ2NTQgXHViYzI5XHVjMmRkIFx1YzkxMVx1YzVkMFx1YjI5NCBcdWMxOGNcdWMyMThcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTU4XHViMjk0IFx1YWM4M1x1YjRlNFx1Yzc3NCBcdWI5Y2VcdWIyZTQuIFx1YmNmNFx1ZDFiNVx1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVkMDcwIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjMThjXHVjMjE4XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YWNlMCwgXHViNDUwIFx1YzE4Y1x1YzIxOFx1Yjk3YyBcdWFjZjFcdWQ1NWMgXHVhYzEyXHVjNzQ0IFx1YzU1NFx1ZDYzOFx1ZDY1NFx1YzVkMFx1YzExY1x1Yzc1OCBcdWQwYTRcdWI4NWMgXHVjMGFjXHVjNmE5XHVkNTU4XHVhY2UwXHViMjk0IFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM4OGJcdWM3NDAgXHVjNzc0XHVjNzIwXHViMjk0IFx1Yzc3Y1x1YmMxOFx1YzgwMVx1YzczY1x1Yjg1YyBcdWI5ZTRcdWM2YjAgXHVkMDcwIFx1YzIxOFx1Yjk3YyBcdWMxOGNcdWM3NzhcdWMyMThcdWJkODRcdWQ1NzQgXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWM1YjRcdWI4MzVcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxOGNcdWMyMThcdWI5N2MgXHVkMGRkXHVkNTYwIFx1YjU0YyBcdWQwNzAgXHVjMjE4XHViOTdjIFx1ZDBkZFx1ZDU1OFx1YmE3NCwgXHVjNzc0IFx1YjQ1OFx1Yzc0NCBcdWFjZjFcdWQ1NzRcdWMxMWMgXHVjNWJiXHVjNWI0XHVjOWMwXHViMjk0IFx1ZDBhNCBcdWFjMTJcdWIzYzQgXHVjZWU0XHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YWRmOCBcdWJjMThcdWIzMDBcdWIyOTQgXHVjMTMxXHViOWJkXHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM5ODksIFx1ZDBhNCBcdWFjMTJcdWM3NzQgXHViOWU0XHVjNmIwIFx1ZDA3MCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIzYzQgXHVjNzc0XHViOTdjIFx1YzE4Y1x1Yzc3OFx1YzIxOFx1YmQ4NFx1ZDU3NCBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YzI2Y1x1YzZiOCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI1MzBcdWI3N2NcdWMxMWMgXHVjNTU0XHVkNjM4XHViYjM4XHVjNzc0IFx1ZDA2Y1x1Yjc5OVx1YjQxOFx1YzljMCBcdWM1NGFcdWIzYzRcdWI4NWQgXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCwgXHVkMGE0IFx1YWMxMlx1Yzc3NCBcdWM4MDFcdWM4MDhcdWQ3ODggXHVkMDcwIFx1YzIxOFx1YjRlNFx1Yzc1OCBcdWFjZjFcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWQ2NTVcdWM3NzhcdWQ1NzRcdWM1N2MgXHVkNTYwIFx1ZDU0NFx1YzY5NFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1ZDBhNCBcdWFjMTIgS1x1YzY0MCBcdWM4MTVcdWMyMTggTFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBLXHViOTdjIFx1Yzc3OFx1YzIxOFx1YmQ4NFx1ZDU3NCBcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWQ1NmRcdWMwYzEgTCBcdWM3NzRcdWMwYzFcdWM3NTggXHVhYzEyXHVjNzNjXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTRcdWM5YzBcdWI5N2MgXHVkNjU1XHVjNzc4XHVkNTU4XHVhY2UwIFx1YzJmNlx1YjJlNC4gXHViYjNjXHViODYwIFx1Yzc3OFx1YzIxOFx1YmQ4NFx1ZDU3NCBcdWQ1NjAgXHViNTRjIDFcdWI4NWMgXHViMDk4XHViMjA0XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWFjZTBcdWI4MjRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IEs9MTQzXHVjNzc4IFx1YWNiZFx1YzZiMCwgXHVjNzc0XHViMjk0IDExXHVhY2ZjIDEzXHVjNzU4IFx1YWNmMVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM5ODksIFx1Yzc3NFx1Yjk3YyBcdWM3NzhcdWMyMThcdWJkODRcdWQ1NzQgXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCAxMSZ0aW1lczsxMywgMTQzXHVjNzU4IFx1YjQ1MCBcdWFjMDBcdWM5YzAgXHVhY2JkXHVjNmIwXHViZmQwXHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgTFx1Yzc3NCAxMVx1Yzc3YyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNzc4XHVjMjE4XHViZDg0XHVkNTc0IFx1ZDU4OFx1Yzc0NCBcdWI1NGMgXHViMDk4XHVjNjI4IFx1YzIxOFx1YjRlNFx1Yzc3NCBcdWJhYThcdWI0NTAgTCBcdWM3NzRcdWMwYzFcdWM3NzRcdWJiYzBcdWI4NWMgXHVjODhiXHVjNzQwIFx1YWNiZFx1YzZiMFx1YzljMFx1YjljYywgTFx1Yzc3NCAxMlx1Yzc3NFx1YzBjMVx1Yzc3YyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjODhiXHVjNzQwIFx1YzU1NFx1ZDYzOFx1YWMwMCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPktcdWM2NDAgTFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM4OGJcdWM3NDAgXHVjNTU0XHVkNjM4XHVjNzc4XHVjOWMwIFx1ZDMxMFx1YjJlOFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVjODE1XHVjMjE4IEssIExcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzg4Ylx1Yzc0MCBcdWM1NTRcdWQ2MzhcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IEdPT0RcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIwOThcdWMwNWMgXHVjNTU0XHVkNjM4XHVjNzdjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBCQURcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBLXHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgKDEgXHVjNTQ0XHViMmNjKSBcdWM3NzhcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT40ICZsZTsgSyAmbGU7IDEwPHN1cD4xMDA8XC9zdXA+PFwvbGk+XHJcblx0PGxpPjIgJmxlOyBMICZsZTsgMSwwMDAsMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIyMDYxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIEVtYmFycmFzc2VkIENyeXB0b2dyYXBoZXIiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDZcL1NjcmVlbiBzaG90IDIwMTAtMDYtMTEgYXQgNF80OF80MiBQTS5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MjQ0cHg7IHdpZHRoOjI5MXB4XCIgXC8+VGhlIHlvdW5nIGFuZCB2ZXJ5IHByb21pc2luZyBjcnlwdG9ncmFwaGVyIE9kZCBFdmVuIGhhcyBpbXBsZW1lbnRlZCB0aGUgc2VjdXJpdHkgbW9kdWxlIG9mIGEgbGFyZ2Ugc3lzdGVtIHdpdGggdGhvdXNhbmRzIG9mIHVzZXJzLCB3aGljaCBpcyBub3cgaW4gdXNlIGluIGhpcyBjb21wYW55LiBUaGUgY3J5cHRvZ3JhcGhpYyBrZXlzIGFyZSBjcmVhdGVkIGZyb20gdGhlIHByb2R1Y3Qgb2YgdHdvIHByaW1lcywgYW5kIGFyZSBiZWxpZXZlZCB0byBiZSBzZWN1cmUgYmVjYXVzZSB0aGVyZSBpcyBubyBrbm93biBtZXRob2QgZm9yIGZhY3RvcmluZyBzdWNoIGEgcHJvZHVjdCBlZmZlY3RpdmVseS48XC9wPlxyXG5cclxuPHA+V2hhdCBPZGQgRXZlbiBkaWQgbm90IHRoaW5rIG9mLCB3YXMgdGhhdCBib3RoIGZhY3RvcnMgaW4gYSBrZXkgc2hvdWxkIGJlIGxhcmdlLCBub3QganVzdCB0aGVpciBwcm9kdWN0LiBJdCBpcyBub3cgcG9zc2libGUgdGhhdCBzb21lIG9mIHRoZSB1c2VycyBvZiB0aGUgc3lzdGVtIGhhdmUgd2VhayBrZXlzLiBJbiBhIGRlc3BlcmF0ZSBhdHRlbXB0IG5vdCB0byBiZSBcdWZiMDFyZWQsIE9kZCBFdmVuIHNlY3JldGx5IGdvZXMgdGhyb3VnaCBhbGwgdGhlIHVzZXJzIGtleXMsIHRvIGNoZWNrIGlmIHRoZXkgYXJlIHN0cm9uZyBlbm91Z2guIEhlIHVzZXMgaGlzIHZlcnkgcG93ZWZ1bCBBdGFyaSwgYW5kIGlzIGVzcGVjaWFsbHkgY2FyZWZ1bCB3aGVuIGNoZWNraW5nIGhpcyBib3NzJnJzcXVvOyBrZXkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgNCAmbGU7IEsgJmxlOyAxMDxzdXA+MTAwPFwvc3VwPiBhbmQgMiAmbGU7IEwgJmxlOyAxMDxzdXA+NjxcL3N1cD4uIEsgaXMgdGhlIGtleSBpdHNlbGYsIGEgcHJvZHVjdCBvZiB0d28gcHJpbWVzLiBMIGlzIHRoZSB3YW50ZWQgbWluaW11bSBzaXplIG9mIHRoZSBmYWN0b3JzIGluIHRoZSBrZXkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIG51bWJlciBLLCBpZiBvbmUgb2YgaXRzIGZhY3RvcnMgYXJlIHN0cmljdGx5IGxlc3MgdGhhbiB0aGUgcmVxdWlyZWQgTCwgeW91ciBwcm9ncmFtIHNob3VsZCBvdXRwdXQgJmxkcXVvO0JBRCBwJnJkcXVvOywgd2hlcmUgcCBpcyB0aGUgc21hbGxlc3QgZmFjdG9yIGluIEsuIE90aGVyd2lzZSwgaXQgc2hvdWxkIG91dHB1dCAmbGRxdW87R09PRCZyZHF1bzsuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==