Description

Consider a 2D map of a region. There are $n$ cities on this map. Each city $i$ has a unique coordinate $(x_i, y_i)$. Each city has $s_i$ soldiers under the command of a general.

The intimidation (threat) that city $i$ exerts on another position $(x, y)$ equals $s_i$ divided by the square of the distance between it and $(x, y)$. You can think of it as the many soldiers in city $i$ exerting intimidation on all nearby positions on the map. If the intimidation from city $j$ to city $i$ at $(x_i, y_i)$ exceeds its number of soldiers $s_i$ (meaning city $j$ can send enough soldiers to subdue the soldiers defending city $i$), then city $i$ is threatened by city $j$. If city $i$ is not threatened by any other city $j$, then the grateful citizens will elect their invincible general as their king, and make their city the capital of his kingdom.

On the other hand, if some city $j$ threatens city $i$ at $(x_i, y_i)$ more than another city $k$ does, then the residents of city $i$ have no choice: city $i$ can only surrender to city $j$. From then on, city $i$ must obey the capital that city $j$ obeys; however, the soldiers of city $i$ do not join the army of city $j$ or its capital. In addition, city $i$ can be saved because two cities $j$ and $k$ that threaten it equally will guard against each other: if one city attacks and conquers city $i$, the other will come to attack and defeat the attacker’s soldiers, who have just fought and are exhausted. But in this case, the residents of city $i$ will no longer elect their general as king, because he failed in his duty to protect the city from threats. Therefore, they must make their city the capital of a democratic country.

Your task is to write a program that takes the map’s city information as input, and for each city $i$ outputs one of the following three results:

• It is the capital of a kingdom.
• It is the capital of a democratic country.
• It obeys city $j$ as its capital.

Input Format

The first line contains an integer $n$, the number of cities. The next $n$ lines give the information of these $n$ cities. Line $i+1$ contains three integers $x_i$, $y_i$, $s_i$ describing city $i$, separated by single spaces.

Output Format

Output consists of $n$ lines. Line $i$ contains the result for city $i$:

• The letter $\texttt{K}$ means city $i$ is the capital of a kingdom.
• The letter $\texttt{D}$ means city $i$ is the capital of a democratic country.
• A positive integer $j$ means city $i$ must surrender and obey city $j$ as its capital.

5
2 5 14
2 3 2
3 2 7
1 1 2
2 1 3

K
D
K
3
3

Hint

Constraints

For $100\%$ of the testdata, $1 \le n \le 1000$, $0 \le x_i, y_i, s_i \le 1000$, $1 \le j \le n$.

Sample Explanation

Consider the following map, where each point represents a city, and the number above it is the number of soldiers:
That is, city $3$ at position $(3, 2)$ is the capital of a kingdom, and it also includes city $4$ at position $(1, 1)$ and city $5$ at position $(2, 1)$. On the other hand, city $1$ at position $(2, 5)$ forms a kingdom by itself, and city $2$ at position $(2, 3)$ forms a democratic country by itself.

Problem Notes

From Day 1: Countries of the Baltic Olympiad in Informatics 2006.
Translated and organized by @求学的企鹅.

Translated by ChatGPT 5