펭귄들의 행진

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

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

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

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

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

얼음 조각 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을 출력한다.