시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 36 7 5 71.429%

문제

우리는 복잡한 태양계에서 무지 멀리 떨어져 있는 두 물체에 대한 중력효과를 계산하고 싶지 않을 뿐더러 계산해도 무시할 정도로 작아서 컴퓨터만 고생한다. 그래서 우리는 k보다 작은 거리에 있는 두 물체만 고려하고 싶다. 우주에서 n개의 점이 주어져 있다면 두 물체 사이의 거리가 k보다 작은 경우는 얼마나 있는가?

입력

각 테스트 케이스에 대해, 맨 첫줄은 두개의 정수, n (2≤n≤100,000) 과 k (1≤k≤109) 로 이루어져 있는데 n은 점의 개수고 k는 허용되는 최대 거리다. 다음 n줄은 각각 세개의 정수, x, y, z (-109≤x,y,z≤109) 로 이루어져 있고 (x,y,z)가 한 점이다. 각 테스트 케이스에 대해 중복되는 점은 없고 거리가 k이하인 경우가 100,000가지를 넘지 않는다고 하자. 입력의 마지막은 두개의 0만 주어진다.

출력

각 테스트 케이스에 대해 각 줄에 k보다 작은 거리에 있는 점들의 쌍의 개수를 출력한다.

예제 입력 1

7 2
0 0 0
1 0 0
1 2 0
1 2 3
1000 1000 1000
1001 1001 1000
1001 999 1001
7 3
0 0 0
1 0 0
1 2 0
1 2 3
-1000 1000 -1000
-1001 1001 -1000
-1001 999 -1001
7 4
0 0 0
1 0 0
1 2 0
1 2 3
1000 -1000 1000
1001 -1001 1000
1001 -999 1001
0 0

예제 출력 1

3
6
9
W3sicHJvYmxlbV9pZCI6Ijk0ODIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWFlNGNcdWM2YjQgXHViOWNjXHVjNzIwXHVjNzc4XHViODI1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2YjBcdWI5YWNcdWIyOTQmbmJzcDtcdWJjZjVcdWM3YTFcdWQ1NWMgXHVkMGRjXHVjNTkxXHVhY2M0XHVjNWQwXHVjMTFjIFx1YmIzNFx1YzljMCBcdWJhNDBcdWI5YWMgXHViNWE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWI0NTAgXHViYjNjXHVjY2I0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM5MTFcdWI4MjVcdWQ2YThcdWFjZmNcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHVhY2UwIFx1YzJmNlx1YzljMCBcdWM1NGFcdWM3NDQgXHViZmQwXHViMzU0XHViN2VjIFx1YWNjNFx1YzBiMFx1ZDU3NFx1YjNjNCBcdWJiMzRcdWMyZGNcdWQ1NjAgXHVjODE1XHViM2M0XHViODVjIFx1Yzc5MVx1YzU0NFx1YzExYyBcdWNlZjRcdWQ0ZThcdWQxMzBcdWI5Y2MgXHVhY2UwXHVjMGRkXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVjNmIwXHViOWFjXHViMjk0IGtcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YWM3MFx1YjlhY1x1YzVkMCBcdWM3ODhcdWIyOTQgXHViNDUwIFx1YmIzY1x1Y2NiNFx1YjljYyBcdWFjZTBcdWI4MjRcdWQ1NThcdWFjZTAgXHVjMmY2XHViMmU0LiBcdWM2YjBcdWM4ZmNcdWM1ZDBcdWMxMWMgblx1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNFx1YmE3NCBcdWI0NTAgXHViYjNjXHVjY2I0IFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWFjMDAga1x1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzViY1x1YjljOFx1YjA5OCBcdWM3ODhcdWIyOTRcdWFjMDA/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1YjllOCBcdWNjYWJcdWM5MDRcdWM3NDAgXHViNDUwXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCwmbmJzcDtuICgyJmxlO24mbGU7MTAwLDAwMCkmbmJzcDtcdWFjZmMgayAoMSZsZTtrJmxlOzEwPHN1cD45PFwvc3VwPikgXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTRcdWIzNzAgblx1Yzc0MCBcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHVhY2UwIGtcdWIyOTQgXHVkNWM4XHVjNmE5XHViNDE4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWFjNzBcdWI5YWNcdWIyZTQuIFx1YjJlNFx1Yzc0YyBuXHVjOTA0XHVjNzQwIFx1YWMwMVx1YWMwMSBcdWMxMzhcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4LCZuYnNwO3gsIHksJm5ic3A7eiAoLTEwPHN1cD45PFwvc3VwPiZsZTt4LHkseiZsZTsxMDxzdXA+OTxcL3N1cD4pIFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwICh4LHkseilcdWFjMDAgXHVkNTVjIFx1YzgxMFx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YzkxMVx1YmNmNVx1YjQxOFx1YjI5NCBcdWM4MTBcdWM3NDAgXHVjNWM2XHVhY2UwIFx1YWM3MFx1YjlhY1x1YWMwMCBrXHVjNzc0XHVkNTU4XHVjNzc4IFx1YWNiZFx1YzZiMFx1YWMwMCAxMDAsMDAwXHVhYzAwXHVjOWMwXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5XHVjNzQwIFx1YjQ1MFx1YWMxY1x1Yzc1OCAwXHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVhYzAxIFx1YzkwNFx1YzVkMCZuYnNwO2tcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YWM3MFx1YjlhY1x1YzVkMCBcdWM3ODhcdWIyOTQgXHVjODEwXHViNGU0XHVjNzU4IFx1YzMwZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk0ODIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTdGFyIFNpbXVsYXRpb25zIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBtYXNzaXZlIHNpbXVsYXRpb25zIG9mIHN0YXIgc3lzdGVtcywgd2UgZG9uJnJzcXVvO3Qgd2FudCB0byBoYXZlIHRvIG1vZGVsIHRoZSBncmF2aXRhdGlvbmFsIGVmZmVjdHMgb2YgcGFpcnMgb2YgYm9kaWVzIHRoYXQgYXJlIHRvbyBmYXIgYXdheSBmcm9tIGVhY2ggb3RoZXIsIGJlY2F1c2UgdGhhdCB3aWxsIHRha2UgZXhjZXNzIGNvbXB1dGluZyBwb3dlciAoYW5kIHRoZWlyIGVmZmVjdHMgb24gZWFjaCBvdGhlciBhcmUgbmVnbGlnaWJsZSkuIFdlIHdhbnQgdG8gb25seSBjb25zaWRlciB0aGUgZWZmZWN0cyB0d28gb2JqZWN0cyBoYXZlIG9uIGVhY2ggb3RoZXIgaWYgdGhlIEV1Y2xpZGVhbiBkaXN0YW5jZSBiZXR3ZWVuIHRoZW0gaXMgbGVzcyB0aGFuIGsuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgbGlzdCBvZiBuIHBvaW50cyBpbiBzcGFjZSwgaG93IG1hbnkgaGF2ZSBhIGRpc3RhbmNlIG9mIGxlc3MgdGhhbiBrIGZyb20gZWFjaCBvdGhlcj88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZXJlIHdpbGwgYmUgc2V2ZXJhbCB0ZXN0IGNhc2VzIGluIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugd2lsbCBiZWdpbiB3aXRoIGEgbGluZSB3aXRoIHR3byBpbnRlZ2VycywgbiAoMiZsZTtuJmxlOzEwMCwwMDApIGFuZCBrICgxJmxlO2smbGU7MTA8c3VwPjk8XC9zdXA+KSwgd2hlcmUgbiBpcyB0aGUgbnVtYmVyIG9mIHBvaW50cywgYW5kIGsgaXMgdGhlIGRlc2lyZWQgbWF4aW11bSBkaXN0YW5jZS4gT24gZWFjaCBvZiB0aGUgZm9sbG93aW5nIG4gbGluZXMgd2lsbCBiZSB0aHJlZSBpbnRlZ2VycyB4LCB5IGFuZCB6ICgtMTA8c3VwPjk8XC9zdXA+JmxlO3gseSx6JmxlOzEwPHN1cD45PFwvc3VwPikgd2hpY2ggYXJlIHRoZSAoeCx5LHopIGNvb3JkaW5hdGVzIG9mIG9uZSBwb2ludC4gV2l0aGluIGEgdGVzdCBjYXNlLCB0aGVyZSB3aWxsIGJlIG5vIGR1cGxpY2F0ZSBwb2ludHMuIFNpbmNlIHN0YXIgc3lzdGVtcyBhcmUgZ2VuZXJhbGx5IHNwYXJzZSwgaXQgaXMgZ3VhcmFudGVlZCB0aGF0IG5vIG1vcmUgdGhhbiAxMDAsMDAwIHBhaXJzIG9mIHBvaW50cyB3aWxsIGJlIHdpdGhpbiBrIG9mIGVhY2ggb3RoZXIuIFRoZSBpbnB1dCB3aWxsIGVuZCB3aXRoIGEgbGluZSB3aXRoIHR3byAwcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiB1bmlxdWUgcGFpcnMgb2YgcG9pbnRzIHRoYXQgYXJlIGxlc3MgdGhhbiBrIGFwYXJ0IGZyb20gZWFjaCBvdGhlci4gT3V0cHV0IG5vIHNwYWNlcywgYW5kIGRvIG5vdCBzZXBhcmF0ZSBhbnN3ZXJzIHdpdGggYmxhbmsgbGluZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d