시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 20 11 10 52.632%

문제

n부터 m까지 숫자가 연속되어 있는 수열 n,n+1,n+2,...,m이 주어졌을 때, 이 수열의 수의 위치를 적절히 바꿔서 인접한 수의 합이 모두 소수가 아닌 수열을 소수 없는 수열이라고 한다. 예를 들어, n=1, m=10일 때, 1,3,5,4,2,6,9,7,8,10은 소수 없는 수열 중 하나이고, 그러한 수열 중 사전순으로 가장 앞서는 수열이다.

여기서 d차 소수 없는 수열은, 연속된 2,3,...,d개의 합이 모두 소수가 아닌 수열이다. 위에서 예로 든 수열은 2차 소수 없는 수열이다. 하지만, 5, 4, 2의 합이 11이 되고, 이 수는 소수이므로 3차 소수 없는 수열은 아니다. 3차 소수 없는 수열 중 사전순으로 가장 앞서는 것은 1,3,5,4,6,2,10,8,7,9이다.

n, m, d가 주어졌을 때, 사전순으로 가장 앞서는 d차 소수 없는 수열을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n, m, d가 공백으로 구분되어져 있다. n, m, d는 1 ≤ n < m ≤ 1000, 2 ≤ d ≤ 10을 만족한다. 입력의 마지막 줄에는 0 0 0이 주어진다.

출력

각 테스트 케이스에 대해서, d차 소수 없는 수열을 콤마(,)로 구분해서 출력한다. 만약 그러한 수열이 여러개일 경우에는 사전순으로 가장 앞서는 것을 출력한다. (즉, 첫째 수가 가장 작은 수열, 같을 때는 두번째 수가 작은 수열, ....) 만약, d차 소수 없는 수열이 없는 경우에는 "No anti-prime sequence exists."을 출력한다.

예제 입력 1

1 10 2
1 10 3
1 10 5
40 60 7
0 0 0

예제 출력 1

1,3,5,4,2,6,9,7,8,10
1,3,5,4,6,2,10,8,7,9
No anti-prime sequence exists.
40,41,43,42,44,46,45,47,48,50,55,53,52,60,56,49,51,59,58,57,54
W3sicHJvYmxlbV9pZCI6IjQyNDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWMyMTggXHVjNWM2XHViMjk0IFx1YzIxOFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiXHJcbjxwPlxyXG5cdG5cdWJkODBcdWQxMzAgbVx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjNWYwXHVjMThkXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWMyMThcdWM1ZjQgbixuKzEsbisyLC4uLixtXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVjMjE4XHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWM4MDFcdWM4MDhcdWQ3ODggXHViYzE0XHVhZmQ0XHVjMTFjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWMxOGNcdWMyMThcdWFjMDAgXHVjNTQ0XHViMmNjIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWMxOGNcdWMyMTggXHVjNWM2XHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIG49MSwgbT0xMFx1Yzc3YyBcdWI1NGMsIDEsMyw1LDQsMiw2LDksNyw4LDEwXHVjNzQwIFx1YzE4Y1x1YzIxOCBcdWM1YzZcdWIyOTQgXHVjMjE4XHVjNWY0IFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NzRcdWFjZTAsIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWMyMThcdWM1ZjQgXHVjOTExIFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjMDBcdWM3YTUgXHVjNTVlXHVjMTFjXHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNWVjXHVhZTMwXHVjMTFjIGRcdWNjMjggXHVjMThjXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NDAsIFx1YzVmMFx1YzE4ZFx1YjQxYyAyLDMsLi4uLGRcdWFjMWNcdWM3NTggXHVkNTY5XHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWMxOGNcdWMyMThcdWFjMDAgXHVjNTQ0XHViMmNjIFx1YzIxOFx1YzVmNFx1Yzc3NFx1YjJlNC4gXHVjNzA0XHVjNWQwXHVjMTFjIFx1YzYwOFx1Yjg1YyBcdWI0ZTAgXHVjMjE4XHVjNWY0XHVjNzQwIDJcdWNjMjggXHVjMThjXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgNSwgNCwgMlx1Yzc1OCBcdWQ1NjlcdWM3NzQgMTFcdWM3NzQgXHViNDE4XHVhY2UwLCBcdWM3NzQgXHVjMjE4XHViMjk0IFx1YzE4Y1x1YzIxOFx1Yzc3NFx1YmJjMFx1Yjg1YyAzXHVjYzI4IFx1YzE4Y1x1YzIxOCBcdWM1YzZcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzQwIFx1YzU0NFx1YjJjOFx1YjJlNC4gM1x1Y2MyOCBcdWMxOGNcdWMyMTggXHVjNWM2XHViMjk0IFx1YzIxOFx1YzVmNCBcdWM5MTEgXHVjMGFjXHVjODA0XHVjMjFjXHVjNzNjXHViODVjIFx1YWMwMFx1YzdhNSBcdWM1NWVcdWMxMWNcdWIyOTQgXHVhYzgzXHVjNzQwIDEsMyw1LDQsNiwyLDEwLDgsNyw5XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRuLCBtLCBkXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjMDBcdWM3YTUgXHVjNTVlXHVjMTFjXHViMjk0IGRcdWNjMjggXHVjMThjXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgbiwgbSwgZFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gbiwgbSwgZFx1YjI5NCAxICZsZTsgbiAmbHQ7IG0gJmxlOyAxMDAwLCAyICZsZTsgZCAmbGU7IDEwXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMCAwIDBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgZFx1Y2MyOCBcdWMxOGNcdWMyMTggXHVjNWM2XHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWNmNjRcdWI5YzgoLClcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTc0XHVjMTFjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjNWVjXHViN2VjXHVhYzFjXHVjNzdjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWMwYWNcdWM4MDRcdWMyMWNcdWM3M2NcdWI4NWMgXHVhYzAwXHVjN2E1IFx1YzU1ZVx1YzExY1x1YjI5NCBcdWFjODNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAoXHVjOTg5LCBcdWNjYWJcdWM5ZjggXHVjMjE4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjMjE4XHVjNWY0LCBcdWFjMTlcdWM3NDQgXHViNTRjXHViMjk0IFx1YjQ1MFx1YmM4OFx1YzlmOCBcdWMyMThcdWFjMDAgXHVjNzkxXHVjNzQwIFx1YzIxOFx1YzVmNCwgLi4uLikgXHViOWNjXHVjNTdkLCBkXHVjYzI4IFx1YzE4Y1x1YzIxOCBcdWM1YzZcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7Tm8gYW50aS1wcmltZSBzZXF1ZW5jZSBleGlzdHMuJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MjQxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQW50aS1wcmltZSBTZXF1ZW5jZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIGEgc2VxdWVuY2Ugb2YgY29uc2VjdXRpdmUgaW50ZWdlcnMgbiwgbisxLCBuKzIsLi4uLG0sIGFuIGFudGktcHJpbWUgc2VxdWVuY2UgaXMgYSByZWFycmFuZ2VtZW50IG9mIHRoZXNlIGludGVnZXJzIHNvIHRoYXQgZWFjaCBhZGphY2VudCBwYWlyIG9mIGludGVnZXJzIHN1bXMgdG8gYSBjb21wb3NpdGUgKG5vbi1wcmltZSkgbnVtYmVyLiBGb3IgZXhhbXBsZSwgaWYgbiA9IDEgYW5kIG0gPSAxMCwgb25lIHN1Y2ggYW50aS1wcmltZSBzZXF1ZW5jZSBpcyAxLDMsNSw0LDIsNiw5LDcsOCwxMC4gVGhpcyBpcyBhbHNvIHRoZSBsZXhpY29ncmFwaGljYWxseSBmaXJzdCBzdWNoIHNlcXVlbmNlLjxcL3A+XHJcblxyXG48cD5XZSBjYW4gZXh0ZW5kIHRoZSBkZWZpbml0aW9uIGJ5IGRlZmluaW5nIGEgZGVncmVlIGQgYW50aS1wcmltZSBzZXF1ZW5jZSBhcyBvbmUgd2hlcmUgYWxsIGNvbnNlY3V0aXZlIHN1YnNlcXVlbmNlcyBvZiBsZW5ndGggMiwzLC4uLixkIHN1bSB0byBhIGNvbXBvc2l0ZSBudW1iZXIuIFRoZSBzZXF1ZW5jZSBhYm92ZSBpcyBhIGRlZ3JlZSAyIGFudGlwcmltZSBzZXF1ZW5jZSwgYnV0IG5vdCBhIGRlZ3JlZSAzLCBzaW5jZSB0aGUgc3Vic2VxdWVuY2UgNSwgNCwgMiBzdW1zIHRvIDExLiBUaGUgbGV4aWNvZ3JhcGhpY2FsbHkgZmlyc3QgZGVncmVlIDMgYW50aS1wcmltZSBzZXF1ZW5jZSBmb3IgdGhlc2UgbnVtYmVycyBpcyAxLDMsNSw0LDYsMiwxMCw4LDcsOS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IHdpbGwgY29uc2lzdCBvZiBtdWx0aXBsZSBpbnB1dCBzZXRzLiBFYWNoIHNldCB3aWxsIGNvbnNpc3Qgb2YgdGhyZWUgaW50ZWdlcnMsIG4sIG0sIGFuZCBkIG9uIGEgc2luZ2xlIGxpbmUuIFRoZSB2YWx1ZXMgb2YgbiwgbSBhbmQgZCB3aWxsIHNhdGlzZnkgMSAmbGU7IG4gJmx0OyBtICZsZTsgMTAwMCwgYW5kIDIgJmxlOyBkICZsZTsgMTAuIFRoZSBsaW5lIDAgMCAwIHdpbGwgaW5kaWNhdGUgZW5kIG9mIGlucHV0IGFuZCBzaG91bGQgbm90IGJlIHByb2Nlc3NlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBpbnB1dCBzZXQsIG91dHB1dCBhIHNpbmdsZSBsaW5lIGNvbnNpc3Rpbmcgb2YgYSBjb21tYS1zZXBhcmF0ZWQgbGlzdCBvZiBpbnRlZ2VycyBmb3JtaW5nIGEgZGVncmVlIGQgYW50aS1wcmltZSBzZXF1ZW5jZSAoZG8gbm90IGluc2VydCBhbnkgc3BhY2VzIGFuZCBkbyBub3Qgc3BsaXQgdGhlIG91dHB1dCBvdmVyIG11bHRpcGxlIGxpbmVzKS4gSW4gdGhlIGNhc2Ugd2hlcmUgbW9yZSB0aGFuIG9uZSBhbnRpLXByaW1lIHNlcXVlbmNlIGV4aXN0cywgcHJpbnQgdGhlIGxleGljb2dyYXBoaWNhbGx5IGZpcnN0IG9uZSAoaS5lLiwgb3V0cHV0IHRoZSBvbmUgd2l0aCB0aGUgbG93ZXN0IGZpcnN0IHZhbHVlOyBpbiBjYXNlIG9mIGEgdGllLCB0aGUgbG93ZXN0IHNlY29uZCB2YWx1ZSwgZXRjLikuIEluIHRoZSBjYXNlIHdoZXJlIG5vIGFudGktcHJpbWUgc2VxdWVuY2UgZXhpc3RzLCBvdXRwdXQ8XC9wPlxyXG5cclxuPHByZT5cclxuTm8gYW50aS1wcmltZSBzZXF1ZW5jZSBleGlzdHMuPFwvcHJlPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=