국가

이 문제는 강력한 국가가 어떻게 미약한 시작에서 생겨나는지를 다룬다. 2차원 지도를 생각하자. 지도 위에는 $n$개의 도시가 있다. 각 도시 $i$는 서로 다른 위치인 정수 좌표 $(x_i, y_i)$에 있으며, 한 명의 장군이 지휘하는 $s_i$명의 병사를 보유한다.

도시 $i$가 위치 $(x, y)$에 미치는 영향력은 $s_i$를 $(x_i, y_i)$와 $(x, y)$ 사이 거리의 제곱으로 나눈 값이다. 마치 도시 $i$의 병사들이 만드는 질량이 주변 모든 위치를 중력처럼 끌어당기는 것과 같다.

도시 $i$는, 다른 도시 $j$가 도시 $i$의 위치 $(x_i, y_i)$에 미치는 영향력이 $s_i$보다 클 때 도시 $j$로부터 위협받는다. 이때 도시 $j$는 도시 $i$를 지키는 모든 병사를 제압할 만큼의 병사를 보낼 수 있다.

• 어느 도시도 도시 $i$를 위협하지 않으면, 감사한 시민들은 그 장군을 왕으로 추대하고 도시를 그 왕국의 수도로 삼는다.
• 도시 $i$를 위협하는 도시 중 정확히 한 도시 $j$가 다른 모든 도시보다 $(x_i, y_i)$에 더 큰 영향력을 미치면, 도시 $i$는 항복할 수밖에 없다. 그 뒤로 도시 $i$는 도시 $j$가 따르는 수도와 같은 수도를 따른다. (다만 도시 $i$의 $s_i$명의 병사는 그 어느 군대에도 합류하지 않는다.)
• 그 외의 경우, 도시 $i$는 똑같이 가장 강하게 위협하는 둘 이상의 도시들의 상호 불신 덕분에 살아남는다. 어느 하나가 먼저 공격해 제압하면, 지친 그 공격자를 나머지가 다시 제압하기 때문이다. 그러나 장군이 도시를 지키지 못했으므로 시민들은 그를 왕으로 추대할 수 없고, 대신 도시를 민주주의의 수도로 삼는다.

각 도시에 대해 세 결과 중 어느 것인지 출력하라.

첫 줄에는 도시의 수를 나타내는 정수 $n$ ($1 \le n \le 1000$)이 주어진다. 이어지는 $n$개의 줄은 각각 한 도시를 설명한다. $i+1$번째 줄에는 세 정수 $x_i$, $y_i$, $s_i$ ($0 \le x_i, y_i, s_i \le 1000$)가 공백 하나로 구분되어 주어진다. 모든 도시의 위치는 서로 다르다.

$n$개의 줄을 출력한다. $i$번째 줄에는 도시 $i$의 결과를 출력한다.

• 도시 $i$가 왕국의 수도이면 문자 K.
• 도시 $i$가 민주주의의 수도이면 문자 D.
• 그 외에는 도시 $i$가 (항복의 연쇄를 따라) 최종적으로 따르게 되는 수도의 번호 $j$ ($1 \le j \le n$).

아래 지도를 보자. 각 점은 도시이고, 병사의 수가 그 위에 적혀 있다.

다섯 도시를 위에서 아래로, 그 다음 왼쪽에서 오른쪽 순서로 번호를 매긴다. 위치 $(3, 2)$의 도시 3은 왕국의 수도이며, 위치 $(1, 1)$의 도시 4와 위치 $(2, 1)$의 도시 5도 이 왕국에 속한다. 위치 $(2, 5)$의 도시 1은 홀로 왕국을 이루고, 위치 $(2, 3)$의 도시 2는 홀로 민주주의를 이룬다.