시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB93302638.806%

문제

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+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgZFx1Y2MyOCBcdWMxOGNcdWMyMTggXHVjNWM2XHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWNmNjRcdWI5YzgoLClcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTc0XHVjMTFjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjNWVjXHViN2VjXHVhYzFjXHVjNzdjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWMwYWNcdWM4MDRcdWMyMWNcdWM3M2NcdWI4NWMgXHVhYzAwXHVjN2E1IFx1YzU1ZVx1YzExY1x1YjI5NCBcdWFjODNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAoXHVjOTg5LCBcdWNjYWJcdWM5ZjggXHVjMjE4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjMjE4XHVjNWY0LCBcdWFjMTlcdWM3NDQgXHViNTRjXHViMjk0IFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjMjE4XHVhYzAwIFx1Yzc5MVx1Yzc0MCBcdWMyMThcdWM1ZjQsIC4uLi4pIFx1YjljY1x1YzU3ZCwgZFx1Y2MyOCBcdWMxOGNcdWMyMTggXHVjNWM2XHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0ICZxdW90O05vIGFudGktcHJpbWUgc2VxdWVuY2UgZXhpc3RzLiZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNDI0MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFudGktcHJpbWUgU2VxdWVuY2VzIiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiBhIHNlcXVlbmNlIG9mIGNvbnNlY3V0aXZlIGludGVnZXJzIG4sIG4rMSwgbisyLC4uLixtLCBhbiBhbnRpLXByaW1lIHNlcXVlbmNlIGlzIGEgcmVhcnJhbmdlbWVudCBvZiB0aGVzZSBpbnRlZ2VycyBzbyB0aGF0IGVhY2ggYWRqYWNlbnQgcGFpciBvZiBpbnRlZ2VycyBzdW1zIHRvIGEgY29tcG9zaXRlIChub24tcHJpbWUpIG51bWJlci4gRm9yIGV4YW1wbGUsIGlmIG4gPSAxIGFuZCBtID0gMTAsIG9uZSBzdWNoIGFudGktcHJpbWUgc2VxdWVuY2UgaXMgMSwzLDUsNCwyLDYsOSw3LDgsMTAuIFRoaXMgaXMgYWxzbyB0aGUgbGV4aWNvZ3JhcGhpY2FsbHkgZmlyc3Qgc3VjaCBzZXF1ZW5jZS48XC9wPlxyXG5cclxuPHA+V2UgY2FuIGV4dGVuZCB0aGUgZGVmaW5pdGlvbiBieSBkZWZpbmluZyBhIGRlZ3JlZSBkIGFudGktcHJpbWUgc2VxdWVuY2UgYXMgb25lIHdoZXJlIGFsbCBjb25zZWN1dGl2ZSBzdWJzZXF1ZW5jZXMgb2YgbGVuZ3RoIDIsMywuLi4sZCBzdW0gdG8gYSBjb21wb3NpdGUgbnVtYmVyLiBUaGUgc2VxdWVuY2UgYWJvdmUgaXMgYSBkZWdyZWUgMiBhbnRpcHJpbWUgc2VxdWVuY2UsIGJ1dCBub3QgYSBkZWdyZWUgMywgc2luY2UgdGhlIHN1YnNlcXVlbmNlIDUsIDQsIDIgc3VtcyB0byAxMS4gVGhlIGxleGljb2dyYXBoaWNhbGx5IGZpcnN0IGRlZ3JlZSAzIGFudGktcHJpbWUgc2VxdWVuY2UgZm9yIHRoZXNlIG51bWJlcnMgaXMgMSwzLDUsNCw2LDIsMTAsOCw3LDkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCB3aWxsIGNvbnNpc3Qgb2YgbXVsdGlwbGUgaW5wdXQgc2V0cy4gRWFjaCBzZXQgd2lsbCBjb25zaXN0IG9mIHRocmVlIGludGVnZXJzLCBuLCBtLCBhbmQgZCBvbiBhIHNpbmdsZSBsaW5lLiBUaGUgdmFsdWVzIG9mIG4sIG0gYW5kIGQgd2lsbCBzYXRpc2Z5IDEgJmxlOyBuICZsdDsgbSAmbGU7IDEwMDAsIGFuZCAyICZsZTsgZCAmbGU7IDEwLiBUaGUgbGluZSAwIDAgMCB3aWxsIGluZGljYXRlIGVuZCBvZiBpbnB1dCBhbmQgc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggaW5wdXQgc2V0LCBvdXRwdXQgYSBzaW5nbGUgbGluZSBjb25zaXN0aW5nIG9mIGEgY29tbWEtc2VwYXJhdGVkIGxpc3Qgb2YgaW50ZWdlcnMgZm9ybWluZyBhIGRlZ3JlZSBkIGFudGktcHJpbWUgc2VxdWVuY2UgKGRvIG5vdCBpbnNlcnQgYW55IHNwYWNlcyBhbmQgZG8gbm90IHNwbGl0IHRoZSBvdXRwdXQgb3ZlciBtdWx0aXBsZSBsaW5lcykuIEluIHRoZSBjYXNlIHdoZXJlIG1vcmUgdGhhbiBvbmUgYW50aS1wcmltZSBzZXF1ZW5jZSBleGlzdHMsIHByaW50IHRoZSBsZXhpY29ncmFwaGljYWxseSBmaXJzdCBvbmUgKGkuZS4sIG91dHB1dCB0aGUgb25lIHdpdGggdGhlIGxvd2VzdCBmaXJzdCB2YWx1ZTsgaW4gY2FzZSBvZiBhIHRpZSwgdGhlIGxvd2VzdCBzZWNvbmQgdmFsdWUsIGV0Yy4pLiBJbiB0aGUgY2FzZSB3aGVyZSBubyBhbnRpLXByaW1lIHNlcXVlbmNlIGV4aXN0cywgb3V0cHV0PFwvcD5cclxuXHJcbjxwcmU+XHJcbk5vIGFudGktcHJpbWUgc2VxdWVuY2UgZXhpc3RzLjxcL3ByZT5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==