City Conquest and Sovereignty

In this problem, you are given a 2D map with (n) cities. Each city (i) has unique coordinates ((x_i, y_i)) and (s_i) soldiers. The deterrence exerted by city (i) at any location ((x,y)) is defined as [ \frac{s_i}{(x_i - x)^2 + (y_i - y)^2} ] A city (i) is classified as follows:

1. If no other city (j) has a deterrence at ((x_i, y_i)) greater than (s_i), then the citizens elect their invincible general as king. In this case, city (i) becomes the capital of a Kingdom.

2. Otherwise, let the set of cities (j) for which the deterrence at ((x_i, y_i)) is greater than (s_i) be considered. If there is a unique city (j) that produces the maximum deterrence (i.e. (\frac{s_j}{(x_j-x_i)^2+(y_j-y_i)^2}) is strictly greater than that of any other city and exceeds (s_i)), then city (i) must surrender to city (j). In this case, output that it obeys city (j) as its capital.

3. Otherwise, if two or more cities tie for the maximum deterrence (with their deterrence values exceeding (s_i)), then even if one city attacks, the other will counter, and as a result city (i) will not elect its general as king. In this case, city (i) becomes the capital of a Democracy.

Your task is to determine, for each city, which of these three outcomes occurs.

inputFormat

The input begins with an integer (n) representing the number of cities. Then (n) lines follow, each containing three integers: (x_i), (y_i), and (s_i), denoting the coordinates and the number of soldiers in the (i)-th city.

outputFormat

Output (n) lines. For the (i)-th city, print one of the following:

• "Kingdom" if city \(i\) is the capital of a Kingdom.
• "Democracy" if city \(i\) is the capital of a Democratic nation.
• "City j" (where \(j\) is the 1-indexed identifier of the unique city whose deterrence forced city \(i\) to surrender) if city \(i\) surrenders.

sample

3
0 0 5
3 0 20
0 4 20

Kingdom
Kingdom
Kingdom