시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6080 3314 2412 54.893%

문제

독일 로또는 {1, 2, ..., 49}에서 숫자 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 숫자 중 k(k>6)개의 숫자를 골라 집합 S를 만든 다음 그 숫자만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 숫자를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 숫자를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 숫자는 k (6 < k < 13)이고, 다음 k개 숫자는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다. 

출력

각 테스트 케이스 마다 숫자를 고르는 모든 방법을 출력한다. 이 때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제 입력 1

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

예제 출력 1

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

힌트

W3sicHJvYmxlbV9pZCI6IjY2MDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4NWNcdWI2MTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjNjNVx1Yzc3YyBcdWI4NWNcdWI2MTBcdWIyOTQgezEsIDIsIC4uLiwgNDl9XHVjNWQwXHVjMTFjIFx1YzIyYlx1Yzc5MCA2XHVhYzFjXHViOTdjIFx1YWNlMFx1Yjk3OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViODVjXHViNjEwIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWIyOTRcdWIzNzAgXHVjMGFjXHVjNmE5XHViNDE4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM3MjBcdWJhODVcdWQ1NWMgXHVjODA0XHViN2I1XHVjNzQwIDQ5XHVhYzAwXHVjOWMwIFx1YzIyYlx1Yzc5MCBcdWM5MTEgayhrJmd0OzYpXHVhYzFjXHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWFjZThcdWI3N2MgXHVjOWQxXHVkNTY5IFNcdWI5N2MgXHViOWNjXHViNGUwIFx1YjJlNFx1Yzc0YyBcdWFkZjggXHVjMjJiXHVjNzkwXHViOWNjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgaz04LCBTPXsxLDIsMyw1LDgsMTMsMjEsMzR9XHVjNzc4IFx1YWNiZFx1YzZiMCBcdWM3NzQgXHVjOWQxXHVkNTY5IFNcdWM1ZDBcdWMxMWMgXHVjMjJiXHVjNzkwXHViOTdjIFx1YWNlMFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWIyOTQgXHVjZDFkIDI4XHVhYzAwXHVjOWMwXHVjNzc0XHViMmU0LiAoWzEsMiwzLDUsOCwxM10sIFsxLDIsMyw1LDgsMjFdLCBbMSwyLDMsNSw4LDM0XSwgWzEsMiwzLDUsMTMsMjFdLCAuLi4sIFszLDUsOCwxMywyMSwzNF0pPFwvcD5cclxuXHJcbjxwPlx1YzlkMVx1ZDU2OSBTXHVjNjQwIGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMjJiXHVjNzkwXHViOTdjIFx1YWNlMFx1Yjk3NFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViYzI5XHViYzk1XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IGsgKDYgJmx0OyBrICZsdDsgMTMpXHVjNzc0XHVhY2UwLCBcdWIyZTRcdWM3NGMga1x1YWMxYyBcdWMyMmJcdWM3OTBcdWIyOTQgXHVjOWQxXHVkNTY5IFNcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHViMjk0IFx1YzIxOFx1Yzc3NFx1YjJlNC4gU1x1Yzc1OCBcdWM2ZDBcdWMxOGNcdWIyOTQgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVhY2UwXHViOTc0XHViMjk0IFx1YmFhOFx1YjRlMCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWMwYWNcdWM4MDQgXHVjMjFjXHVjNzNjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YmU0OCBcdWM5MDRcdWM3NDQgXHVkNTU4XHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2NjAzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTG90dG8iLCJkZXNjcmlwdGlvbiI6IjxwPkluIHRoZSBHZXJtYW4gTG90dG8geW91IGhhdmUgdG8gc2VsZWN0IDYgbnVtYmVycyBmcm9tIHRoZSBzZXQgezEsMiwuLi4sNDl9LiBBIHBvcHVsYXIgc3RyYXRlZ3kgdG8gcGxheSBMb3R0byAtIGFsdGhvdWdoIGl0IGRvZXNuJiMzOTt0IGluY3JlYXNlIHlvdXIgY2hhbmNlIG9mIHdpbm5pbmcgLSBpcyB0byBzZWxlY3QgYSBzdWJzZXQgUyBjb250YWluaW5nIGsgKGsmZ3Q7Nikgb2YgdGhlc2UgNDkgbnVtYmVycywgYW5kIHRoZW4gcGxheSBzZXZlcmFsIGdhbWVzIHdpdGggY2hvb3NpbmcgbnVtYmVycyBvbmx5IGZyb20gUy4gRm9yIGV4YW1wbGUsIGZvciBrPTggYW5kIFMgPSB7MSwyLDMsNSw4LDEzLDIxLDM0fSB0aGVyZSBhcmUgMjggcG9zc2libGUgZ2FtZXM6IFsxLDIsMyw1LDgsMTNdLCBbMSwyLDMsNSw4LDIxXSwgWzEsMiwzLDUsOCwzNF0sIFsxLDIsMyw1LDEzLDIxXSwgLi4uIFszLDUsOCwxMywyMSwzNF0uPFwvcD5cclxuXHJcbjxwPllvdXIgam9iIGlzIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IHJlYWRzIGluIHRoZSBudW1iZXIgayBhbmQgdGhlIHNldCBTIGFuZCB0aGVuIHByaW50cyBhbGwgcG9zc2libGUgZ2FtZXMgY2hvb3NpbmcgbnVtYmVycyBvbmx5IGZyb20gUy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBmaWxlIHdpbGwgY29udGFpbiBvbmUgb3IgbW9yZSB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiBvbmUgbGluZSBjb250YWluaW5nIHNldmVyYWwgaW50ZWdlcnMgc2VwYXJhdGVkIGZyb20gZWFjaCBvdGhlciBieSBzcGFjZXMuIFRoZSBmaXJzdCBpbnRlZ2VyIG9uIHRoZSBsaW5lIHdpbGwgYmUgdGhlIG51bWJlciBrICg2ICZsdDsgayAmbHQ7IDEzKS4gVGhlbiBrIGludGVnZXJzLCBzcGVjaWZ5aW5nIHRoZSBzZXQgUywgd2lsbCBmb2xsb3cgaW4gYXNjZW5kaW5nIG9yZGVyLiBJbnB1dCB3aWxsIGJlIHRlcm1pbmF0ZWQgYnkgYSB2YWx1ZSBvZiB6ZXJvICgwKSBmb3Igay48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCBhbGwgcG9zc2libGUgZ2FtZXMsIGVhY2ggZ2FtZSBvbiBvbmUgbGluZS4gVGhlIG51bWJlcnMgb2YgZWFjaCBnYW1lIGhhdmUgdG8gYmUgc29ydGVkIGluIGFzY2VuZGluZyBvcmRlciBhbmQgc2VwYXJhdGVkIGZyb20gZWFjaCBvdGhlciBieSBleGFjdGx5IG9uZSBzcGFjZS4gVGhlIGdhbWVzIHRoZW1zZWx2ZXMgaGF2ZSB0byBiZSBzb3J0ZWQgbGV4aWNvZ3JhcGhpY2FsbHksIHRoYXQgbWVhbnMgc29ydGVkIGJ5IHRoZSBsb3dlc3QgbnVtYmVyIGZpcnN0LCB0aGVuIGJ5IHRoZSBzZWNvbmQgbG93ZXN0IGFuZCBzbyBvbiwgYXMgZGVtb25zdHJhdGVkIGluIHRoZSBzYW1wbGUgb3V0cHV0IGJlbG93LiBUaGUgdGVzdCBjYXNlcyBoYXZlIHRvIGJlIHNlcGFyYXRlZCBmcm9tIGVhY2ggb3RoZXIgYnkgZXhhY3RseSBvbmUgYmxhbmsgbGluZS4gRG8gbm90IHB1dCBhIGJsYW5rIGxpbmUgYWZ0ZXIgdGhlIGxhc3QgdGVzdCBjYXNlLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=