P7639 [BalticOI 2006] COUNTRIES (Day 1)

任何一个国家都是由弱小而拼搏斗争逐渐强大崛起的。

考虑地区的二维地图，在这张地图上有 $n$ 个城市。每个城市 $i$ 在地图上都有一个独特的坐标（$x_i$,$y_i$）。每个城市在一个将军的指挥下有 $s_i$ 个士兵。 城市 $i$ 对另一个位置（$x$,$y$）的威慑为 $s_i$ 除于它和（$x$,$y$）间距离的平方。这就好像城市 $i$ 中的大量士兵对它周围所有地图位置施加了威慑。如果城市 $j$ 对（$x_i$,$y_i$）的城市 $i$ 的威慑超过其士兵数 $s_i$：城市 $j$ 可以派遣足够的士兵前去制服保卫城市 $i$ 的士兵，那么城市 $i$ 就被城市 $j$ 所威胁。如果城市 $i$ 没有受到任何其他城市 $j$ 的威胁，那么心存感激的市民将选出其无敌的将军作为他们的国王，并将他们的城市变成他的王国的首都。 另一方面，如果一些城市 $j$ 对（$x_i$,$y_i$）的城市 $i$ 的威胁比另一个城市 $k$ 对城市 $i$ 的威胁更具威慑，那么城市 $i$ 的居民别无选择：城市 $i$ 只能向城市 $j$ 投降。从今以后，城市 $i$ 必须服从城市 $j$ 所服从的首都；然而城市 $i$ 的士兵并没有加入城市 $j$ 或其首都的军队。除此之外，城市 $i$ 会因为 $j$ 和 $k$ 两个对它具有同等威胁的城市之间相互防备而得救：如果其中一个城市攻击并征服城市 $i$，那么另一个城市将会前来攻击并战胜先前刚战斗完而疲惫不堪的攻击方士兵。但这种情况下，城市 $i$ 的居民们将不再选举他们的将军为他们的国王，因为他未能履行他的职责保护城市免受威胁。因此，他们必须把他们的城市变成一个民主国家的首都。 你的任务是编写一个程序，将地图上的城市信息作为输入，并为每个城市 $i$ 输出三种结果之一: - 它是一个王国的首都。 - 它是一个民主国家的首都。 - 它服从城市 $j$ 作为它的首都。

第一行由一个整数 $n$ 组成，表示城市数。接下来的 $n$ 行给出这 $n$ 个城市的信息，每行给出一个城市的。第 $i+1$ 行以三个整数 $x_i$，$y_i$，$s_i$ 表示城市 $i$ 的信息，这三个整数由单个空格字符分隔。

输出由 $n$ 行组成，其中第 $i$ 行由城市 $i$ 的结果组成: - 字母 $\texttt{K}$ 表示城市 $i$ 是一个王国的首都。 - 字母 $\texttt{D}$ 表示城市 $i$ 是一个民主国家的首都。 - 正整数 $j$ 表示城市 $i$ 不得不投降而服从其首都的城市 $j$ 。

#### 数据规模与约定 对于 $100 \%$ 的数据，$1 \le n \le 1000$，$0 \le x_i,y_i,s_i \le 1000$，$1 \le j \le n$。 #### 样例说明 考虑以下地图，其中每个点代表一个城市，上面给出了它的士兵数量：  也就是说，位置（$3$,$2$）上的城市 $3$ 是一个王国的首都，它还包括位置（$1$,$1$）上的城市 $4$ 和位置（$2$,$1$）上的城市 $5$。另一方面，位于位置（$2$,$5$）的城市 $1$ 自己形成了一个王国，而位于位置（$2$,$3$）的城市 $2$ 自己形成了一个民主国家。 #### 题目说明 来源于 [Baltic Olympiad in Informatics 2006](https://www.cs.helsinki.fi/group/boi2006/) 的 [Day 1:Countries](https://www.cs.helsinki.fi/group/boi2006/tasks/countries.pdf)。 由 @[求学的企鹅](/user/271784) 翻译整理。