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

문제

3×K(1 ≤ K ≤ 60)개의 도시로 이루어진 나라가 있다. 각각의 도시에는 모두 똑같이 1,000명씩의 사람이 살고 있다. 현재 정권을 잡고 있는 월드당에서는 차기 대선을 노리고 각 도시에 월드당을 지지하는 사람들이 몇 명씩 살고 있는지 조사하였다. 월드당은 여당이기 때문에 주도적으로 선거구를 원하는 대로 나눌 수 있다. 월드당에서는 조사 자료를 바탕으로 차기 대선에서 승리할 수 있도록 선거구를 나누려고 한다.

선거구를 나눌 때에는 각각 K개씩의 도시로 세 개의 선거구로 나누게 된다. 이 중 두 개 이상의 선거구에서 월드당을 지지할 경우 월드당이 당선되게 된다. 각 선거구에 대해서는 절반(500×K명)을 넘는 인원이 월드당을 지지할 경우, 그 선거구가 월드당을 지지하는 것이 된다.

각 도시에서 월드당을 지지하는 인원이 주어졌을 때, 이를 토대로 월드당이 당선될 수 있도록 선거구를 나누는 프로그램을 작성하시오.

입력

첫째 줄에 K가 주어진다. 다음 3×K개의 줄에는 차례로 1번, 2번, …, 3×K번 도시에서 월드당을 지지하는 인원의 수가 주어진다.

출력

처음 K개의 줄에 1번 선거구에 포함되는 도시의 번호를, 그 다음 K개의 줄에 2번 선거구에 포함되는 도시의 번호를, 그 다음 K개의 줄에 3번 선거구에 포함되는 도시의 번호를 출력한다. 항상 답이 존재하는 경우만 입력으로 주어지며, 답이 여러 개 존재할 경우에는 그 중 하나만 출력하면 된다.

예제 입력 1

2
510
500
500
670
400
310

예제 출력 1

1
2
3
6
5
4
W3sicHJvYmxlbV9pZCI6IjIyMDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMjBcdWFjNzBcdWFkNmMgXHViMDk4XHViMjA0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD4zJnRpbWVzO0soMSAmbGU7IEsgJmxlOyA2MClcdWFjMWNcdWM3NTggXHViM2M0XHVjMmRjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWIwOThcdWI3N2NcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViM2M0XHVjMmRjXHVjNWQwXHViMjk0IFx1YmFhOFx1YjQ1MCBcdWI2MTFcdWFjMTlcdWM3NzQgMSwwMDBcdWJhODVcdWM1MjlcdWM3NTggXHVjMGFjXHViNzhjXHVjNzc0IFx1YzBiNFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1ZDYwNFx1YzdhYyBcdWM4MTVcdWFkOGNcdWM3NDQgXHVjN2ExXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWM2ZDRcdWI0ZGNcdWIyZjlcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjYzI4XHVhZTMwIFx1YjMwMFx1YzEyMFx1Yzc0NCBcdWIxNzhcdWI5YWNcdWFjZTAgXHVhYzAxIFx1YjNjNFx1YzJkY1x1YzVkMCBcdWM2ZDRcdWI0ZGNcdWIyZjlcdWM3NDQgXHVjOWMwXHVjOWMwXHVkNTU4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWJhODcgXHViYTg1XHVjNTI5IFx1YzBiNFx1YWNlMCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjODcwXHVjMGFjXHVkNTU4XHVjNjAwXHViMmU0LiBcdWM2ZDRcdWI0ZGNcdWIyZjlcdWM3NDAgXHVjNWVjXHViMmY5XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM4ZmNcdWIzYzRcdWM4MDFcdWM3M2NcdWI4NWMgXHVjMTIwXHVhYzcwXHVhZDZjXHViOTdjIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWIzMDBcdWI4NWMgXHViMDk4XHViMjBjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzZkNFx1YjRkY1x1YjJmOVx1YzVkMFx1YzExY1x1YjI5NCBcdWM4NzBcdWMwYWMgXHVjNzkwXHViOGNjXHViOTdjIFx1YmMxNFx1ZDBkNVx1YzczY1x1Yjg1YyBcdWNjMjhcdWFlMzAgXHViMzAwXHVjMTIwXHVjNWQwXHVjMTFjIFx1YzJiOVx1YjlhY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkIFx1YzEyMFx1YWM3MFx1YWQ2Y1x1Yjk3YyBcdWIwOThcdWIyMDRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMjBcdWFjNzBcdWFkNmNcdWI5N2MgXHViMDk4XHViMjBjIFx1YjU0Y1x1YzVkMFx1YjI5NCBcdWFjMDFcdWFjMDEgS1x1YWMxY1x1YzUyOVx1Yzc1OCBcdWIzYzRcdWMyZGNcdWI4NWMgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWMxMjBcdWFjNzBcdWFkNmNcdWI4NWMgXHViMDk4XHViMjA0XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjNzc0IFx1YzkxMSBcdWI0NTAgXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWMxMjBcdWFjNzBcdWFkNmNcdWM1ZDBcdWMxMWMgXHVjNmQ0XHViNGRjXHViMmY5XHVjNzQ0IFx1YzljMFx1YzljMFx1ZDU2MCBcdWFjYmRcdWM2YjAgXHVjNmQ0XHViNGRjXHViMmY5XHVjNzc0IFx1YjJmOVx1YzEyMFx1YjQxOFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YWMwMSBcdWMxMjBcdWFjNzBcdWFkNmNcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjXHViMjk0IFx1YzgwOFx1YmMxOCg1MDAmdGltZXM7S1x1YmE4NSlcdWM3NDQgXHViMTE4XHViMjk0IFx1Yzc3OFx1YzZkMFx1Yzc3NCBcdWM2ZDRcdWI0ZGNcdWIyZjlcdWM3NDQgXHVjOWMwXHVjOWMwXHVkNTYwIFx1YWNiZFx1YzZiMCwgXHVhZGY4IFx1YzEyMFx1YWM3MFx1YWQ2Y1x1YWMwMCBcdWM2ZDRcdWI0ZGNcdWIyZjlcdWM3NDQgXHVjOWMwXHVjOWMwXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWIzYzRcdWMyZGNcdWM1ZDBcdWMxMWMgXHVjNmQ0XHViNGRjXHViMmY5XHVjNzQ0IFx1YzljMFx1YzljMFx1ZDU1OFx1YjI5NCBcdWM3NzhcdWM2ZDBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0XHViOTdjIFx1ZDFhMFx1YjMwMFx1Yjg1YyBcdWM2ZDRcdWI0ZGNcdWIyZjlcdWM3NzQgXHViMmY5XHVjMTIwXHViNDIwIFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHVjMTIwXHVhYzcwXHVhZDZjXHViOTdjIFx1YjA5OFx1YjIwNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIDMmdGltZXM7S1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjYzI4XHViODQwXHViODVjIDFcdWJjODgsIDJcdWJjODgsICZoZWxsaXA7LCAzJnRpbWVzO0tcdWJjODggXHViM2M0XHVjMmRjXHVjNWQwXHVjMTFjIFx1YzZkNFx1YjRkY1x1YjJmOVx1Yzc0NCBcdWM5YzBcdWM5YzBcdWQ1NThcdWIyOTQgXHVjNzc4XHVjNmQwXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjYzk4XHVjNzRjIEtcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIDFcdWJjODggXHVjMTIwXHVhYzcwXHVhZDZjXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NCBcdWIzYzRcdWMyZGNcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjLCBcdWFkZjggXHViMmU0XHVjNzRjIEtcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIDJcdWJjODggXHVjMTIwXHVhYzcwXHVhZDZjXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NCBcdWIzYzRcdWMyZGNcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjLCBcdWFkZjggXHViMmU0XHVjNzRjIEtcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIDNcdWJjODggXHVjMTIwXHVhYzcwXHVhZDZjXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NCBcdWIzYzRcdWMyZGNcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVkNTZkXHVjMGMxIFx1YjJmNVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViOWNjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YjJmNVx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjIFx1Yzg3NFx1YzdhY1x1ZDU2MCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVhZGY4IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5Y2MgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMjAzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSmVyc2V5IFBvbGl0aWNzIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgbmV3ZXN0IGNlbnN1cyBvZiBKZXJzZXkgQ293cyBhbmQgSG9sc3RlaW4gQ293cywgV2lzY29uc2luIGNvd3MgaGF2ZSBlYXJuZWQgdGhyZWUgc3RhbGxzIGluIHRoZSBCYXJuIG9mIFJlcHJlc2VudGF0aXZlcy4gVGhlIEplcnNleSBDb3dzIGN1cnJlbnRseSBjb250cm9sIHRoZSBzdGF0ZSYjMzk7cyByZWRpc3RyaWN0aW5nIGNvbW1pdHRlZS4gVGhleSB3YW50IHRvIHBhcnRpdGlvbiB0aGUgc3RhdGUgaW50byB0aHJlZSBlcXVhbGx5IHNpemVkIHZvdGluZyBkaXN0cmljdHMgc3VjaCB0aGF0IHRoZSBKZXJzZXkgQ293cyBhcmUgZ3VhcmFudGVlZCB0byB3aW4gZWxlY3Rpb25zIGluIGF0IGxlYXN0IHR3byBvZiB0aGUgZGlzdHJpY3RzLjxcL3A+XHJcblxyXG48cD5XaXNjb25zaW4gaGFzIDMqSyAoMSAmbHQ7PSBLICZsdDs9IDYwKSBjaXRpZXMgb2YgMSwwMDAgY293cywgbnVtYmVyZWQgMS4uMypLLCBlYWNoIHdpdGggYSBrbm93biBudW1iZXIgKHJhbmdlOiAwLi4xLDAwMCkgb2YgSmVyc2V5IENvd3MuIEZpbmQgYSB3YXkgdG8gcGFydGl0aW9uIHRoZSBzdGF0ZSBpbnRvIHRocmVlIGRpc3RyaWN0cywgZWFjaCB3aXRoIEsgY2l0aWVzLCBzdWNoIHRoYXQgdGhlIEplcnNleSBDb3dzIGhhdmUgdGhlIG1ham9yaXR5IHBlcmNlbnRhZ2UgaW4gYXQgbGVhc3QgdHdvIG9mIGRpc3RyaWN0cy48XC9wPlxyXG5cclxuPHA+QWxsIHN1cHBsaWVkIGlucHV0IGRhdGFzZXRzIGFyZSBzb2x2YWJsZS48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyLCBLPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLjMqSysxOiBPbmUgaW50ZWdlciBwZXIgbGluZSwgdGhlIG51bWJlciBvZiBjb3dzIGluIGVhY2ggY2l0eSB0aGF0IGFyZSBKZXJzZXkgQ293cy4gTGluZSBpKzEgY29udGFpbnMgY2l0eSBpJiMzOTtzIGNvdyBjZW5zdXMuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmVzIDEuLks6IEsgbGluZXMgdGhhdCBhcmUgdGhlIGNpdHkgbnVtYmVycyBpbiBkaXN0cmljdCBvbmUsIG9uZSBwZXIgbGluZTxcL2xpPlxyXG5cdDxsaT5MaW5lcyBLKzEuLjJLOiBLIGxpbmVzIHRoYXQgYXJlIHRoZSBjaXR5IG51bWJlcnMgaW4gZGlzdHJpY3QgdHdvLCBvbmUgcGVyIGxpbmU8XC9saT5cclxuXHQ8bGk+TGluZXMgMksrMS4uM0s6IEsgbGluZXMgdGhhdCBhcmUgdGhlIGNpdHkgbnVtYmVycyBpbiBkaXN0cmljdCB0aHJlZSwgb25lIHBlciBsaW5lPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiPHA+T3RoZXIgc29sdXRpb25zIG1pZ2h0IGJlIHBvc3NpYmxlLiBOb3RlIHRoYXQgJnF1b3Q7MiAzJnF1b3Q7IHdvdWxkIE5PVCBiZSBhIGRpc3RyaWN0IHdvbiBieSB0aGUgSmVyc2V5cywgYXMgdGhleSB3b3VsZCBiZSBleGFjdGx5IGhhbGYgb2YgdGhlIGNvd3MuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d