P7639 [BalticOI 2006] COUNTRIES (Day 1)

Any country grows from being weak to becoming strong through hard struggle.

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.

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 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.

#### 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](https://www.cs.helsinki.fi/group/boi2006/tasks/countries.pdf) of the [Baltic Olympiad in Informatics 2006](https://www.cs.helsinki.fi/group/boi2006/). Translated and organized by @[求学的企鹅](/user/271784). Translated by ChatGPT 5