Trên một bản đồ hai chiều có \(n\) thành phố. Thành phố \(i\) nằm tại tọa độ phân biệt \((x_i,y_i)\) và có \(s_i\) binh lính dưới quyền một vị tướng.

Ảnh hưởng của thành phố \(i\) tại vị trí \((x,y)\) bằng \(s_i\) chia cho bình phương khoảng cách từ thành phố ấy đến \((x,y)\). Thành phố \(i\) bị thành phố \(j\) đe dọa nếu ảnh hưởng của \(j\) tại \((x_i,y_i)\) lớn hơn \(s_i\).

• Nếu không bị thành phố nào đe dọa, thành phố \(i\) trở thành kinh đô của một vương quốc.
• Nếu đúng một thành phố \(j\) có ảnh hưởng lớn nhất và ảnh hưởng ấy đe dọa \(i\), thành phố \(i\) đầu hàng \(j\) và từ đó tuân theo cùng kinh đô với \(j\).
• Nếu có ít nhất hai thành phố cùng đạt ảnh hưởng đe dọa lớn nhất, sự nghi kỵ lẫn nhau cứu thành phố \(i\); tuy vậy vị tướng không thể làm vua, nên \(i\) trở thành thủ đô của một nền dân chủ.

Hãy xác định kết quả cuối cùng của mỗi thành phố.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\). Mỗi dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa ba số nguyên \(x_i,y_i,s_i\).

Dữ liệu ra

In \(n\) dòng. Dòng \(i\) là:

• ký tự K nếu thành phố \(i\) là kinh đô của một vương quốc;
• ký tự D nếu thành phố \(i\) là thủ đô của một nền dân chủ;
• chỉ số \(j\) nếu thành phố \(i\) phải đầu hàng và cuối cùng tuân theo thành phố \(j\) làm kinh đô.

Ràng buộc

• \(1\le n\le 1000\).
• \(0\le x_i,y_i,s_i\le 1000\).
• Mọi cặp tọa độ \((x_i,y_i)\) đôi một khác nhau.

Ví dụ

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

K
D
K
3
3