시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 77 24 24 45.283%

문제

상근이가 살고 있는 마을에 유행성 독감이 전염되기 시작했다. 마을에는 총 M명이 살고 있고, 각 사람은 0번부터 M-1번까지 번호가 매겨져 있다. 독감은 딱 하루 동안만 걸린다. 따라서, 한 사람이 여러 번 독감에 걸릴 수 있다.

독감은 다른 마을에 놀러갔다가 돌아온 사람들이 전염시켰다. 이 사람들의 번호는 모두 알려져 있다. 첫째 날에 독감에 걸린 사람은 이 사람들 뿐이다. 독감은 이 사람들에 근거해서 전염이 된다.

둘째 날부터 각각의 날에 독감에 걸린 사람은 다음과 같은 규칙을 갖는다.

이전 날에 독감에 걸린 사람 a와 첫째 날에 걸린 사람 b를 곱한 뒤 M으로 나눈 나머지 번호를 갖는 p는 모두 독감에 걸린다.

즉, (a * b) mod M = p 에 해당하는 p는 모두 독감에 걸린다.

a와 b는 같아도 된다. 예를 들어, 마을에 101명이 살고 있고, 첫째 날에 독감에 걸린 사람이 5와 50이라고 하자. 둘째 날에 독감에 걸린 사람은 25, 48 (250 mod 101), 76 (2500 mod 101)이 된다. 또, 셋째 날에 독감에 걸린 사람 중 한 명은 77 이다. ((48 * 50) mod 101)

K일에 독감에 걸려 있는 사람을 모두 구하는 프로그램을 작성하시오.

입력

첫째 날에 K, M, N이 주어진다. (1 ≤ K ≤ 1018, 3 ≤ M ≤ 1500, N < M) N은 첫째 날 독감에 걸린 사람의 수이다.

둘째 줄에는 첫째 날 독감에 걸린 사람이 공백으로 구분되어 주어진다.

출력

첫째 줄에 K일에 독감에 걸려있는 사람의 번호를 공백으로 구분하여 오름차순으로 출력한다.

예제 입력 1

2 100 3
1 2 3

예제 출력 1

1 2 3 4 6 9
W3sicHJvYmxlbV9pZCI6IjM5ODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3MjBcdWQ1ODlcdWMxMzEgXHViM2M1XHVhYzEwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWI5YzhcdWM3NDRcdWM1ZDAgXHVjNzIwXHVkNTg5XHVjMTMxIFx1YjNjNVx1YWMxMFx1Yzc3NCBcdWM4MDRcdWM1ZmNcdWI0MThcdWFlMzAgXHVjMmRjXHVjNzkxXHVkNTg4XHViMmU0LiBcdWI5YzhcdWM3NDRcdWM1ZDBcdWIyOTQgXHVjZDFkIE1cdWJhODVcdWM3NzQgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1YzBhY1x1Yjc4Y1x1Yzc0MCAwXHViYzg4XHViZDgwXHVkMTMwIE0tMVx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViM2M1XHVhYzEwXHVjNzQwIFx1YjUzMSBcdWQ1NThcdWI4ZTggXHViM2Q5XHVjNTQ4XHViOWNjIFx1YWM3OFx1YjliMFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWQ1NWMgXHVjMGFjXHViNzhjXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWJjODggXHViM2M1XHVhYzEwXHVjNWQwIFx1YWM3OFx1YjliNCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzYzVcdWFjMTBcdWM3NDAgXHViMmU0XHViOTc4IFx1YjljOFx1Yzc0NFx1YzVkMCBcdWIxODBcdWI3ZWNcdWFjMTRcdWIyZTRcdWFjMDAgXHViM2NjXHVjNTQ0XHVjNjI4IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWM4MDRcdWM1ZmNcdWMyZGNcdWNmMzBcdWIyZTQuIFx1Yzc3NCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWM1NGNcdWI4MjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWM5ZjggXHViMGEwXHVjNWQwIFx1YjNjNVx1YWMxMFx1YzVkMCBcdWFjNzhcdWI5YjAgXHVjMGFjXHViNzhjXHVjNzQwIFx1Yzc3NCBcdWMwYWNcdWI3OGNcdWI0ZTQgXHViZmQwXHVjNzc0XHViMmU0LiBcdWIzYzVcdWFjMTBcdWM3NDAgXHVjNzc0IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1YzVkMCBcdWFkZmNcdWFjNzBcdWQ1NzRcdWMxMWMgXHVjODA0XHVjNWZjXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YjBhMFx1YmQ4MFx1ZDEzMCBcdWFjMDFcdWFjMDFcdWM3NTggXHViMGEwXHVjNWQwIFx1YjNjNVx1YWMxMFx1YzVkMCBcdWFjNzhcdWI5YjAgXHVjMGFjXHViNzhjXHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YWMxNlx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjODA0IFx1YjBhMFx1YzVkMCBcdWIzYzVcdWFjMTBcdWM1ZDAgXHVhYzc4XHViOWIwIFx1YzBhY1x1Yjc4YyBhXHVjNjQwIFx1Y2NhYlx1YzlmOCBcdWIwYTBcdWM1ZDAgXHVhYzc4XHViOWIwIFx1YzBhY1x1Yjc4YyBiXHViOTdjIFx1YWNmMVx1ZDU1YyBcdWI0YTQgTVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWFjMTZcdWIyOTQgcFx1YjI5NCBcdWJhYThcdWI0NTAgXHViM2M1XHVhYzEwXHVjNWQwIFx1YWM3OFx1YjliMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOTg5LCAoYSAqIGIpIG1vZCBNID0gcCBcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IHBcdWIyOTQgXHViYWE4XHViNDUwIFx1YjNjNVx1YWMxMFx1YzVkMCBcdWFjNzhcdWI5YjBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmFcdWM2NDAgYlx1YjI5NCBcdWFjMTlcdWM1NDRcdWIzYzQgXHViNDFjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWI5YzhcdWM3NDRcdWM1ZDAgMTAxXHViYTg1XHVjNzc0IFx1YzBiNFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1Y2NhYlx1YzlmOCBcdWIwYTBcdWM1ZDAgXHViM2M1XHVhYzEwXHVjNWQwIFx1YWM3OFx1YjliMCBcdWMwYWNcdWI3OGNcdWM3NzQgNVx1YzY0MCA1MFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuIFx1YjQ1OFx1YzlmOCBcdWIwYTBcdWM1ZDAgXHViM2M1XHVhYzEwXHVjNWQwIFx1YWM3OFx1YjliMCBcdWMwYWNcdWI3OGNcdWM3NDAgMjUsIDQ4ICgyNTAgbW9kIDEwMSksIDc2ICgyNTAwIG1vZCAxMDEpXHVjNzc0IFx1YjQxY1x1YjJlNC4gXHViNjEwLCBcdWMxNGJcdWM5ZjggXHViMGEwXHVjNWQwIFx1YjNjNVx1YWMxMFx1YzVkMCBcdWFjNzhcdWI5YjAgXHVjMGFjXHViNzhjIFx1YzkxMSBcdWQ1NWMgXHViYTg1XHVjNzQwIDc3IFx1Yzc3NFx1YjJlNC4gKCg0OCAqIDUwKSBtb2QgMTAxKTxcL3A+XHJcblxyXG48cD5LXHVjNzdjXHVjNWQwIFx1YjNjNVx1YWMxMFx1YzVkMCBcdWFjNzhcdWI4MjQgXHVjNzg4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc0NCBcdWJhYThcdWI0NTAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHViMGEwXHVjNWQwIEssIE0sIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEsgJmxlOyAxMDxzdXA+MTg8XC9zdXA+LCAzICZsZTsgTSAmbGU7IDE1MDAsIE4gJmx0OyBNKSBOXHVjNzQwIFx1Y2NhYlx1YzlmOCBcdWIwYTAgXHViM2M1XHVhYzEwXHVjNWQwIFx1YWM3OFx1YjliMCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2NhYlx1YzlmOCBcdWIwYTAgXHViM2M1XHVhYzEwXHVjNWQwIFx1YWM3OFx1YjliMCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBLXHVjNzdjXHVjNWQwIFx1YjNjNVx1YWMxMFx1YzVkMCBcdWFjNzhcdWI4MjRcdWM3ODhcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzk4OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRMQUtBVkFDIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgZmFyYXdheSBjaXR5IG9mIFhhbmFkdSwgYSBmbHUgZXBpZGVtaWMgaGFzIGJyb2tlbiBvdXQsIGNhdXNlZCBieSBhIHN0cmFpbiBrbm93biBhcyBoYWlyeSBmbHUuIFRoZXJlIGFyZSBNIHBlb3BsZSBsaXZpbmcgaW4gdGhlIGNpdHksIGVhY2ggcmVzaWRlbnQgaGF2aW5nIGEgdW5pcXVlIHBlcnNvbmFsIElEIG51bWJlciBmcm9tIHRoZSByYW5nZSBvZiAwIHRvIE0gJm5kYXNoOyAxLCBpbmNsdXNpdmUuIEluZmVjdGlvbiB3aXRoIHRoaXMgc3RyYWluIGxhc3RzIGV4YWN0bHkgb25lIGRheSwgYW5kIGEgcGVyc29uIGNhbiBjYXRjaCBpdCBtdWx0aXBsZSB0aW1lcyBwZXIgc2Vhc29uIChzaW5jZSBpdCBtdXRhdGVzIHRvbyBxdWlja2x5IGZvciBsYXN0aW5nIGltbXVuaXR5KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+T24gdGhlIGZpcnN0IGRheSBvZiB0aGUgZXBpZGVtaWMsIHRoZSBmbHUgd2FzIGJyb3VnaHQgZnJvbSBhbm90aGVyIGZhcmF3YXkgY291bnRyeSBieSBhIGdyb3VwIG9mIHJlc2lkZW50cyBuaWNrbmFtZWQgJmxkcXVvO2luaXQtcGF0aWVudHMmcmRxdW87LCB3aG9zZSBJRCBudW1iZXJzIGFyZSBrbm93bi4gVGhlIGZsdSYjMzk7cyBzcHJlYWQgaXMgYmFzZWQgb24gdGhlbS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBmb2xsb3dpbmcgZGF5LCBhIHJlc2lkZW50IHdpdGggSUQgbnVtYmVyIHAgd2lsbCBjYXRjaCB0aGUgZmx1IGlmZiB0aGVyZSBleGlzdHMgYSByZXNpZGVudCB3aXRoIElEIGEgd2hvIHdhcyBpbmZlY3RlZCB0aGUgcHJldmlvdXMgZGF5LCBhcyB3ZWxsIGFzIGFuIGluaXQtcGF0aWVudCB3aXRoIElEIGIsIHN1Y2ggdGhhdDombmJzcDs8XC9wPlxyXG5cclxuPHA+KGEgKiBiKSBtb2QgTSA9IHAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBudW1iZXJzIGEgYW5kIGIgbmVlZCBub3QgYmUgZGlzdGluY3QuIEZvciBleGFtcGxlLCBjb25zaWRlciBhIGNhc2Ugd2hlcmUgdGhlcmUgYXJlIDEwMSBwZW9wbGUgaW4gdGhlIHRvd24sIGFuZCB0aGUgaW5pdC1wYXRpZW50cyBhcmUgNSBhbmQgNTAuIE9uIHRoZSBmaXJzdCBkYXksIHRoZSBpbml0LXBhdGllbnRzIGFyZSBpbmZlY3RlZCBieSBkZWZpbml0aW9uLiBPbiB0aGUgc2Vjb25kIGRheSwgdGhlIHJlc2lkZW50cyBpbmZlY3RlZCBhcmUgMjUsIDQ4ICgyNTAgbW9kIDEwMSksIGFuZCA3NiAoMjUwMCBtb2QgMTAxKS4gT24gdGhlIHRoaXJkIGRheSwgb25lIG9mIHRoZSBpbmZlY3RlZCBwYXRpZW50cyBpcyA3Nywgc2luY2UgKDQ4ICogNTApIG1vZCAxMDEgPSA3Ny4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2hvIHdpbGwgY2F0Y2ggdGhlIGZsdSBvbiB0aGUgSy10aCBkYXk/Jm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aHJlZSBwb3NpdGl2ZSBpbnRlZ2VycywgSywgTSwgYW5kIE4gKDEgJmxlOyBLICZsZTsgMTAxOCwgMyAmbGU7IE0gJmxlOyAxNTAwLCBOICZsdDsgTSkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBOIHNwYWNlLXNlcGFyYXRlZCBub25uZWdhdGl2ZSBpbnRlZ2VycywgdGhlIHBlcnNvbmFsIElEIG51bWJlcnMgb2YgcmVzaWRlbnRzIHdobyB3ZXJlIGluZmVjdGVkIG9uIHRoZSBmaXJzdCBkYXkgKHRoZSBpbml0LXBhdGllbnRzKS4gVGhlc2UgbnVtYmVycyBhcmUgdW5pcXVlLCBpbmNyZWFzaW5nLCBhbmQgZG8gbm90IGV4Y2VlZCBNIC0gMS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBwZXJzb25hbCBJRCBudW1iZXJzIG9mIHJlc2lkZW50cyBpbmZlY3RlZCB3aXRoIGZsdSBvbiB0aGUgSy10aCBkYXksIGdpdmVuIHNwYWNlLXNlcGFyYXRlZCBhbmQgaW4gaW5jcmVhc2luZyBvcmRlci4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=