Trung tâm điều phối giao hàng \(S\) cần vận chuyển hàng hóa đến các điểm giao nhận trong thành phố. Có tổng cộng \(N\) điểm (bao gồm cả trung tâm \(S\)), được đánh số từ \(1\) đến \(N\).

Mỗi điểm \(i\) được xác định bởi 3 thông số: tọa độ địa lý \((X_i, Y_i)\) và mật độ dân cư \(P_i\) (\(P_i > 0\)).

Thành phố rất đông đúc, thời gian di chuyển (tính bằng phút) giữa hai điểm \(U\) và \(V\) phụ thuộc vào bình phương khoảng cách địa lý và sự tương tác dân cư giữa hai khu vực. Gọi \(C(U, V)\) là số lượng chữ số của tích \(P_U \times P_V\) trong hệ thập phân. Thời gian di chuyển được tính bằng công thức:

Để đảm bảo an toàn và tránh kẹt xe, xe giao hàng chỉ được phép đi trên tuyến đường trực tiếp nối giữa \(U\) và \(V\) nếu thời gian di chuyển \(W(U, V)\) không vượt quá ngưỡng giới hạn \(K\) phút. Nếu \(W(U, V) > K\), tuyến đường này bị cấm, tài xế buộc phải đi vòng qua các điểm trung gian khác.

Yêu cầu: Hãy tìm thời gian ngắn nhất để di chuyển từ trung tâm \(S\) đến tất cả các điểm giao nhận trong thành phố.

Input

• Dòng đầu tiên chứa ba số nguyên \(N, S, K\).

  • \(N\): Tổng số địa điểm.
  • \(S\): Chỉ số của trung tâm điều phối (\(1 \le S \le N\)).
  • \(K\): Ngưỡng thời gian giới hạn cho một tuyến đường trực tiếp.

• \(N\) dòng tiếp theo: Dòng thứ \(i\) chứa ba số nguyên \(X_i, Y_i, P_i\) biểu diễn thông số của điểm \(i\).

Output

• Ghi ra một dòng duy nhất chứa \(N\) số nguyên, các số cách nhau bởi một khoảng trắng.
• Số thứ \(i\) thể hiện thời gian ngắn nhất để di chuyển từ trung tâm \(S\) đến điểm \(i\). Nếu không có bất kỳ cách nào để đi đến điểm \(i\), in ra -1.

Example

3 1 20 
0 0 5 
2 0 2 
5 0 25 

0 8 26

Ràng buộc

• \(1 \le N \le 5000\)
• \(1 \le S \le N\)
• \(1 \le K \le 10^{15}\)
• \(X_i, Y_i \in [-10^6, +10^6]\)
• \(1 \le P_i \le 10^9\)