시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 128 MB145815955.140%

문제

남극의 한 빙하 지대 어딘가에 펭귄 여러 마리가 살고 있다. 각 펭귄들은 바다에 떠 있는 여러 얼음 조각 위에 나뉘어 서 있다. 한 얼음 조각 위에 여러 마리의 펭귄이 있을 수도 있으며, 펭귄이 없는 빈 얼음 조각도 있을 수 있다.

펭귄은 사회성이 높은 동물이기 때문에 한 개의 얼음 위에 모두 모이고 싶다. 펭귄들은 얼음 조각들 중 하나를 도착지로 정해서 얼음과 얼음 사이를 점프해 오가며 도착지 위로 모두 모일 것이다. 단, 펭귄은 날 수 없기 때문에 많이 먼 얼음으로는 점프해서 가지 못한다.

게다가 지구 온난화 때문에 얼음 조각들이 녹고 있어서 몇몇 얼음 조각들은 펭귄이 밟았을 때 부서져 바다 아래로 가라앉아 버릴 수도 있다. 펭귄들은 얼음에 대해서는 아주 전문가이기 때문에 정확히 몇 번 밟아야 얼음이 가라앉는지 알 수 있다.

펭귄이 점프하여 다른 얼음으로 도약할 때 펭귄이 딛고 있던 얼음은 손상된다. 하지만 펭귄이 어떤 얼음으로 착지할 때 그 얼음은 손상되지 않는다.

펭귄들이 어떤 얼음 위로 모여야 다 모일 수 있을까?

얼음 조각 5개와 펭귄 세 마리가 있는 예제

입력

첫 줄에 테스트 케이스의 수 T가 주어진다. ( T ≤ 100 )

각 테스트 케이스는 다음과 같이 구성되어 있다.

  • 첫 줄에 얼음 조각의 개수 N (1 ≤ N ≤ 100)과 펭귄들이 점프할 수 있는 최대 거리 D ( 0 ≤ D ≤ 100000 ). D는 실수 범위에서 주어진다.
  • N줄에 걸쳐 정수 xi, yi, ni, mi
    • xi, yi는 좌표로 나타낸 얼음의 위치 ( -10000 ≤ xi, yi ≤ 10000 )
    • ni 는 그 얼음 위에 서 있는 펭귄의 수 ( 0 ≤ ni ≤ 10 )
    • mi는 펭귄이 그 얼음을 밟고 도약할 수 있는 최대 횟수 ( 1 ≤ mi ≤ 200 )

출력

각 테스트 케이스마다 펭귄들이 모두 모일 수 있는 얼음 조각의 번호를 공백으로 구분하여 오름차순으로 출력한다.

얼음 조각의 번호는 0부터 시작하여 입력으로 주어진 순서대로이며, 만일 어떤 얼음으로도 펭귄들이 다 모일 수 없을 경우 -1을 출력한다.

예제 입력 1

2
5 3.5
1 1 1 1
2 3 0 1
3 5 1 1
5 1 1 1
5 4 0 1
3 1.1
-1 0 5 10
0 0 3 9
2 0 1 1

예제 출력 1

1 2 4
-1
W3sicHJvYmxlbV9pZCI6IjM2OTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzYWRcdWFkYzRcdWI0ZTRcdWM3NTggXHVkNTg5XHVjOWM0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIwYThcdWFkZjlcdWM3NTggXHVkNTVjIFx1YmU1OVx1ZDU1OCBcdWM5YzBcdWIzMDAgXHVjNWI0XHViNTE4XHVhYzAwXHVjNWQwIFx1ZDNhZFx1YWRjNCBcdWM1ZWNcdWI3ZWMgXHViOWM4XHViOWFjXHVhYzAwIFx1YzBiNFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQzYWRcdWFkYzRcdWI0ZTRcdWM3NDAgXHViYzE0XHViMmU0XHVjNWQwIFx1YjVhMCBcdWM3ODhcdWIyOTQgXHVjNWVjXHViN2VjIFx1YzViY1x1Yzc0YyBcdWM4NzBcdWFjMDEgXHVjNzA0XHVjNWQwIFx1YjA5OFx1YjI1OFx1YzViNCBcdWMxMWMgXHVjNzg4XHViMmU0LiBcdWQ1NWMgXHVjNWJjXHVjNzRjIFx1Yzg3MFx1YWMwMSBcdWM3MDRcdWM1ZDAgXHVjNWVjXHViN2VjIFx1YjljOFx1YjlhY1x1Yzc1OCBcdWQzYWRcdWFkYzRcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1ZDNhZFx1YWRjNFx1Yzc3NCBcdWM1YzZcdWIyOTQgXHViZTQ4IFx1YzViY1x1Yzc0YyBcdWM4NzBcdWFjMDFcdWIzYzQgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDNhZFx1YWRjNFx1Yzc0MCBcdWMwYWNcdWQ2OGNcdWMxMzFcdWM3NzQgXHViMTkyXHVjNzQwIFx1YjNkOVx1YmIzY1x1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVkNTVjIFx1YWMxY1x1Yzc1OCBcdWM1YmNcdWM3NGMgXHVjNzA0XHVjNWQwIFx1YmFhOFx1YjQ1MCBcdWJhYThcdWM3NzRcdWFjZTAgXHVjMmY2XHViMmU0LiBcdWQzYWRcdWFkYzRcdWI0ZTRcdWM3NDAgXHVjNWJjXHVjNzRjIFx1Yzg3MFx1YWMwMVx1YjRlNCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1YjNjNFx1Y2MyOVx1YzljMFx1Yjg1YyBcdWM4MTVcdWQ1NzRcdWMxMWMgXHVjNWJjXHVjNzRjXHVhY2ZjIFx1YzViY1x1Yzc0YyBcdWMwYWNcdWM3NzRcdWI5N2MgXHVjODEwXHVkNTA0XHVkNTc0IFx1YzYyNFx1YWMwMFx1YmE3MCBcdWIzYzRcdWNjMjlcdWM5YzAgXHVjNzA0XHViODVjIFx1YmFhOFx1YjQ1MCBcdWJhYThcdWM3N2MgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWIyZTgsIFx1ZDNhZFx1YWRjNFx1Yzc0MCBcdWIwYTAgXHVjMjE4IFx1YzVjNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViOWNlXHVjNzc0IFx1YmEzYyBcdWM1YmNcdWM3NGNcdWM3M2NcdWI4NWNcdWIyOTQgXHVjODEwXHVkNTA0XHVkNTc0XHVjMTFjIFx1YWMwMFx1YzljMCBcdWJhYmJcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM4Y1x1YjJlNFx1YWMwMCBcdWM5YzBcdWFkNmMgXHVjNjI4XHViMDljXHVkNjU0IFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM1YmNcdWM3NGMgXHVjODcwXHVhYzAxXHViNGU0XHVjNzc0IFx1YjE3OVx1YWNlMCBcdWM3ODhcdWM1YjRcdWMxMWMgXHViYTg3XHViYTg3IFx1YzViY1x1Yzc0YyBcdWM4NzBcdWFjMDFcdWI0ZTRcdWM3NDAgXHVkM2FkXHVhZGM0XHVjNzc0IFx1YmMxZlx1YzU1OFx1Yzc0NCBcdWI1NGMgXHViZDgwXHVjMTFjXHVjODM4IFx1YmMxNFx1YjJlNCBcdWM1NDRcdWI3OThcdWI4NWMgXHVhYzAwXHViNzdjXHVjNTQ5XHVjNTQ0IFx1YmM4NFx1YjliNCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWQzYWRcdWFkYzRcdWI0ZTRcdWM3NDAgXHVjNWJjXHVjNzRjXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExY1x1YjI5NCBcdWM1NDRcdWM4ZmMgXHVjODA0XHViYjM4XHVhYzAwXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM4MTVcdWQ2NTVcdWQ3ODggXHViYTg3IFx1YmM4OCBcdWJjMWZcdWM1NDRcdWM1N2MgXHVjNWJjXHVjNzRjXHVjNzc0IFx1YWMwMFx1Yjc3Y1x1YzU0OVx1YjI5NFx1YzljMCBcdWM1NGMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkM2FkXHVhZGM0XHVjNzc0IFx1YzgxMFx1ZDUwNFx1ZDU1OFx1YzVlYyBcdWIyZTRcdWI5NzggXHVjNWJjXHVjNzRjXHVjNzNjXHViODVjIFx1YjNjNFx1YzU3ZFx1ZDU2MCBcdWI1NGMgXHVkM2FkXHVhZGM0XHVjNzc0IFx1YjUxYlx1YWNlMCBcdWM3ODhcdWIzNTggXHVjNWJjXHVjNzRjXHVjNzQwIFx1YzE5MFx1YzBjMVx1YjQxY1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1ZDNhZFx1YWRjNFx1Yzc3NCBcdWM1YjRcdWI1YTQgXHVjNWJjXHVjNzRjXHVjNzNjXHViODVjIFx1Y2MyOVx1YzljMFx1ZDU2MCBcdWI1NGMgXHVhZGY4IFx1YzViY1x1Yzc0Y1x1Yzc0MCBcdWMxOTBcdWMwYzFcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQzYWRcdWFkYzRcdWI0ZTRcdWM3NzQgXHVjNWI0XHViNWE0IFx1YzViY1x1Yzc0YyBcdWM3MDRcdWI4NWMgXHViYWE4XHVjNWVjXHVjNTdjIFx1YjJlNCBcdWJhYThcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG5cclxuPHA+PGltZyBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvcGVuZ3Vpbi5wbmdcIiBzdHlsZT1cImhlaWdodDoyOTcuNTI5NDExNzY0NzA2cHg7IHdpZHRoOjI4MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzViY1x1Yzc0YyBcdWM4NzBcdWFjMDEgNVx1YWMxY1x1YzY0MCBcdWQzYWRcdWFkYzQgXHVjMTM4IFx1YjljOFx1YjlhY1x1YWMwMCBcdWM3ODhcdWIyOTQgXHVjNjA4XHVjODFjPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoIFQgJmxlOyAxMDAgKTxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWM1YmNcdWM3NGMgXHVjODcwXHVhYzAxXHVjNzU4IFx1YWMxY1x1YzIxOCBOICgxICZsZTsgTiAmbGU7IDEwMClcdWFjZmMgXHVkM2FkXHVhZGM0XHViNGU0XHVjNzc0IFx1YzgxMFx1ZDUwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWFjNzBcdWI5YWMgRCAoIDAgJmxlOyBEICZsZTsgMTAwMDAwICkuIERcdWIyOTQgXHVjMmU0XHVjMjE4IFx1YmM5NFx1YzcwNFx1YzVkMFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPk5cdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YzgxNVx1YzIxOCB4aSwgeWksIG5pLCBtaVxyXG5cdDx1bD5cclxuXHRcdDxsaT54aSwgeWlcdWIyOTQgXHVjODhjXHVkNDVjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWM1YmNcdWM3NGNcdWM3NTggXHVjNzA0XHVjZTU4ICggLTEwMDAwICZsZTsgeGksIHlpICZsZTsgMTAwMDAgKTxcL2xpPlxyXG5cdFx0PGxpPm5pIFx1YjI5NCBcdWFkZjggXHVjNWJjXHVjNzRjIFx1YzcwNFx1YzVkMCBcdWMxMWMgXHVjNzg4XHViMjk0IFx1ZDNhZFx1YWRjNFx1Yzc1OCBcdWMyMTggKCAwICZsZTsgbmkgJmxlOyAxMCApPFwvbGk+XHJcblx0XHQ8bGk+bWlcdWIyOTQgXHVkM2FkXHVhZGM0XHVjNzc0IFx1YWRmOCBcdWM1YmNcdWM3NGNcdWM3NDQgXHViYzFmXHVhY2UwIFx1YjNjNFx1YzU3ZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWQ2OWZcdWMyMTggKCAxICZsZTsgbWkgJmxlOyAyMDAgKTxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVkM2FkXHVhZGM0XHViNGU0XHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWJhYThcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM1YmNcdWM3NGMgXHVjODcwXHVhYzAxXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViY1x1Yzc0YyBcdWM4NzBcdWFjMDFcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDBcdWJkODBcdWQxMzAgXHVjMmRjXHVjNzkxXHVkNTU4XHVjNWVjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjXHVjNzc0XHViYTcwLCBcdWI5Y2NcdWM3N2MgXHVjNWI0XHViNWE0IFx1YzViY1x1Yzc0Y1x1YzczY1x1Yjg1Y1x1YjNjNCBcdWQzYWRcdWFkYzRcdWI0ZTRcdWM3NzQgXHViMmU0IFx1YmFhOFx1Yzc3YyBcdWMyMTggXHVjNWM2XHVjNzQ0IFx1YWNiZFx1YzZiMCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzY5MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1hcmNoIG9mIHRoZSBQZW5ndWlucyIsImRlc2NyaXB0aW9uIjoiPHA+U29tZXdoZXJlIG5lYXIgdGhlIHNvdXRoIHBvbGUsIGEgbnVtYmVyIG9mIHBlbmd1aW5zIGFyZSBzdGFuZGluZyBvbiBhIG51bWJlciBvZiBpY2UgZmxvZXMuIEJlaW5nIHNvY2lhbCBhbmltYWxzLCB0aGUgcGVuZ3VpbnMgd291bGQgbGlrZSB0byBnZXQgdG9nZXRoZXIsIGFsbCBvbiB0aGUgc2FtZSBmbG9lLiBUaGUgcGVuZ3VpbnMgZG8gbm90IHdhbnQgdG8gZ2V0IHdldCwgc28gdGhleSBoYXZlIHVzZSB0aGVpciBsaW1pdGVkIGp1bXAgZGlzdGFuY2UgdG8gZ2V0IHRvZ2V0aGVyIGJ5IGp1bXBpbmcgZnJvbSBwaWVjZSB0byBwaWVjZS4gSG93ZXZlciwgdGVtcGVyYXR1cmVzIGhhdmUgYmVlbiBoaWdoIGxhdGVseSwgYW5kIHRoZSBmbG9lcyBhcmUgc2hvd2luZyBjcmFja3MsIGFuZCB0aGV5IGdldCBkYW1hZ2VkIGZ1cnRoZXIgYnkgdGhlIGZvcmNlIG5lZWRlZCB0byBqdW1wIHRvIGFub3RoZXIgZmxvZS4gRm9ydHVuYXRlbHkgdGhlIHBlbmd1aW5zIGFyZSByZWFsIGV4cGVydHMgb24gY3JhY2tpbmcgaWNlIGZsb2VzLCBhbmQga25vdyBleGFjdGx5IGhvdyBtYW55IHRpbWVzIGEgcGVuZ3VpbiBjYW4ganVtcCBvZmYgZWFjaCBmbG9lIGJlZm9yZSBpdCBkaXNpbnRlZ3JhdGVzIGFuZCBkaXNhcHBlYXJzLiBMYW5kaW5nIG9uIGFuIGljZSBmbG9lIGRvZXMgbm90IGRhbWFnZSBpdC4gWW91IGhhdmUgdG8gaGVscCB0aGUgcGVuZ3VpbnMgZmluZCBhbGwgZmxvZXMgd2hlcmUgdGhleSBjYW4gbWVldC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvcGVuZ3Vpbi5wbmdcIiBzdHlsZT1cImhlaWdodDoyMTZweDsgd2lkdGg6MjA0cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+QSBzYW1wbGUgbGF5b3V0IG9mIGljZSBmbG9lcyB3aXRoIDMgcGVuZ3VpbnMgb24gdGhlbS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMCkgYW5kIGEgZmxvYXRpbmctcG9pbnQgbnVtYmVyIEQgKDAgJmxlOyBEICZsZTsgMTAwIDAwMCksIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgaWNlIHBpZWNlcyBhbmQgdGhlIG1heGltdW0gZGlzdGFuY2UgYSBwZW5ndWluIGNhbiBqdW1wLjxcL2xpPlxyXG5cdDxsaT4mbmJzcDtOIGxpbmVzLCBlYWNoIGxpbmUgY29udGFpbmluZyB4aSwgeWksIG5pIGFuZCBtaSwgZGVub3RpbmcgZm9yIGVhY2ggaWNlIHBpZWNlIGl0cyBYIGFuZCBZIGNvb3JkaW5hdGUsIHRoZSBudW1iZXIgb2YgcGVuZ3VpbnMgb24gaXQgYW5kIHRoZSBtYXhpbXVtIG51bWJlciBvZiB0aW1lcyBhIHBlbmd1aW4gY2FuIGp1bXAgb2ZmIHRoaXMgcGllY2UgYmVmb3JlIGl0IGRpc2FwcGVhcnMgKCZtaW51czsxMCAwMDAgJmxlOyB4aSwgeWkgJmxlOyAxMCAwMDAsIDAgJmxlOyBuaSAmbGU7IDEwLCAxICZsZTsgbWkgJmxlOyAyMDApLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIGNvbnRhaW5pbmcgYSBzcGFjZS1zZXBhcmF0ZWQgbGlzdCBvZiAwLWJhc2VkIGluZGljZXMgb2YgdGhlIHBpZWNlcyBvbiB3aGljaCBhbGwgcGVuZ3VpbnMgY2FuIG1lZXQuIElmIG5vIHN1Y2ggcGllY2UgZXhpc3RzLCBvdXRwdXQgYSBsaW5lIHdpdGggdGhlIHNpbmdsZSBudW1iZXIgLTEuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2007 B번