Lost in Space

William Robinson은 음악실에서 완전히 어리둥절했다. 가방에서 트라이앵글을 찾을 수 없었기 때문이다. 그는 전날 밤에 트라이앵글을 준비했음이 확실했다. 그날 아침 일찍 스쿨버스에 올라탈 때 트라이앵글이 쨍그랑 울리던 소리도 기억하고 있었다. 아니다, 꿈은 아니었다. 그의 트라이앵글은 아주 독특했다. 어느 두 변도 길이가 같지 않았고, 그래서 그가 가장 좋아하는 독특한 소리가 났다. 그는 음악 선생님 Mr. Smith에게 자신의 트라이앵글이 아마도 그 외계인들에게 훔쳐져 깊은 우주로 던져졌을 것이라고 주장했다.

여러분의 임무는 Will이 우주에서 트라이앵글을 찾도록 돕는 것이다. 그의 트라이앵글은 외계인들에 의해 보이지 않게 되었지만, 꼭짓점이 있을 수 있는 후보 위치들은 어떻게든 알려져 있다. 그중 어느 세 개가 그의 트라이앵글을 만드는지 말해야 한다. 웜홀을 지나면서 트라이앵글은 크기가 변했을 수 있다. 하지만 그런 경우에도 모든 변이 똑같이 늘어나거나 줄어든 것으로 알려져 있다. 즉, 변환된 트라이앵글은 원래 트라이앵글과 닮음이다.

입력의 첫 번째 줄에는 정수가 하나 있으며, 이는 데이터 세트의 수이다. 각 데이터 세트는 Will의 경우와 같은 사건 하나에 대한 데이터를 제공한다. 데이터 세트는 최소 하나, 최대 열 개가 주어진다.

각 데이터 세트의 첫 번째 줄에는 원래 트라이앵글의 변 길이를 센티미터 단위로 나타내는 소수 셋이 있다. 원래 트라이앵글의 세 꼭짓점은 P, Q, R로 이름 붙는다. 첫 줄에 주어지는 소수 셋은 차례로 변 QR, RP, PQ의 길이에 해당한다. 이들은 하나 이상의 공백 문자로 구분된다.

데이터 세트의 두 번째 줄에는 꼭짓점 후보로 고려할 공간상의 점 개수를 나타내는 정수가 있다. 점은 최소 세 개, 최대 서른 개가 고려된다.

데이터 세트의 나머지 줄에는 후보 점들의 좌표가 광년 단위로 주어진다. 각 줄에는 x, y, z 좌표에 해당하는 소수 셋이 하나 이상의 공백 문자로 구분되어 있다. 점은 등장 순서대로 1부터 번호가 매겨진다.

주어진 점 중 세 개로 만들어지는 모든 삼각형 가운데 원래 트라이앵글과 닮은 것은 하나뿐이다. 즉, 어느 두 변의 길이 비율이 원래의 대응하는 비율과 0.01퍼센트 미만의 오차로 같다. 다른 삼각형은 일부 비율이 원래와 적어도 0.1퍼센트 이상 다르다.

좌표계의 원점은 지구 중심이 아니라 우리 은하의 중심이다. 여기에서는 음수 좌표 값이 나올 수 있다. 모두 우리 은하 안이나 근처에 있으므로 좌표 값은 십만 광년 미만이다. 상대론적 효과는 고려할 필요가 없다. 즉, 우리는 유클리드 공간에 있다고 가정해도 된다. 계산에서 1광년은 9.461 × 10^12 킬로미터와 같다고 가정해도 된다.

뒤따르는 데이터 세트가 있다면, 앞선 데이터 세트의 마지막 줄 바로 다음 줄부터 시작한다.

각 데이터 세트마다 한 줄을 출력한다. 그 줄에는 닮은 삼각형의 세 꼭짓점 번호를 공백 문자 하나로 구분하여 담는다. 번호는 P, Q, R 순서로 보고한다.