Countries

This problem explores how mighty countries arise from humble beginnings. Consider a two-dimensional map. On the map there are $n$ cities. Each city $i$ sits at a distinct location with integer coordinates $(x_i, y_i)$ and holds a garrison of $s_i$ soldiers commanded by a general.

The influence that city $i$ exerts on a location $(x, y)$ equals $s_i$ divided by the squared distance between $(x_i, y_i)$ and $(x, y)$ — as if the mass of soldiers in city $i$ pulled on every surrounding location like gravity.

City $i$ is threatened by another city $j$ when the influence city $j$ exerts on city $i$'s own location $(x_i, y_i)$ is strictly greater than $s_i$; then city $j$ could send enough soldiers to overpower every defender of city $i$.

• If no other city threatens city $i$, its grateful citizens crown its general as king and make the city the capital of his kingdom.
• If exactly one threatening city $j$ exerts strictly more influence on $(x_i, y_i)$ than every other city, city $i$ has no choice but to surrender. From then on city $i$ obeys the same capital that city $j$ obeys (its $s_i$ soldiers do not join anyone's army).
• Otherwise city $i$ is saved by the mutual distrust of two or more equally strongest threateners: whichever attacked first would in turn be overpowered by the others. But because its general failed to keep the city safe, the citizens cannot crown him; instead the city becomes the capital of a democracy.

For every city, report which of the three outcomes applies.

The first line contains one integer $n$ ($1 \le n \le 1000$), the number of cities. Each of the next $n$ lines describes one city: line $i+1$ contains three integers $x_i$, $y_i$, $s_i$ ($0 \le x_i, y_i, s_i \le 1000$) separated by single spaces. All cities occupy distinct locations.

Print $n$ lines. Line $i$ gives the outcome for city $i$:

• K if city $i$ is the capital of a kingdom.
• D if city $i$ is the capital of a democracy.
• Otherwise the index $j$ ($1 \le j \le n$) of the city that city $i$ ultimately obeys as its capital, following the chain of surrenders.

Consider the map below, where each dot is a city and its number of soldiers is written above it:

Number the five cities from top to bottom, then left to right. City 3 at $(3, 2)$ is the capital of a kingdom that also contains city 4 at $(1, 1)$ and city 5 at $(2, 1)$. City 1 at $(2, 5)$ forms a kingdom by itself, and city 2 at $(2, 3)$ forms a democracy by itself.