Cho mạng lưới giao thông gồm ~n~ nút giao thông và ~m~ đường nối hai chiều, nút ~i~ có vận tốc giới hạn ~X_i~ (mét/giây). Con đường ~j~ nối hai nút giao thông ~a_j~ và ~b_j~ có độ dài ~l_j~ (mét) và vận tốc giới hạn ~v_j~ (mét/giây). Một phương tiện di chuyển có vận tốc tối đa ~V~ (mét/giây) và gia tốc giới hạn ~A~ (~\text{mét}/\text{giây}^2~).

Quy tắc vận tốc:

• Khi phương tiện đang di chuyển trên con đường thứ ~j~, phương tiện có thể tăng tốc, nhưng vận tốc không được tăng quá ~\min(V, v_j)~;

• Khi phương tiện đi vào một nút giao thông thứ ~i~, phương tiện buộc phải giảm vận tốc về ~X_i~ nếu đang có vận tốc cao hơn. Đặc biệt, khi ~X_i = 0~ phương tiện cần dừng lại hoàn toàn trước khi được phép đi tiếp vào một đường nối nào đó.

• Khi phương tiện muốn đi từ một nút giao thông ~u~ vào con đường ~j~, phương tiện buộc phải giảm vận tốc về còn ~v_j~ nếu đang có vận tốc lớn hơn.

• Thời gian dành cho cả hai trường hợp giảm tốc xem như bằng ~0~.

• Sau khi phương tiện đã giảm tốc cho hợp lý thì được phép đi vào đường nối và có thể bắt đầu tăng tốc.

Yêu cầu: Tính thời gian nhỏ nhất để đi từ nút ~1~ (vận tốc đầu bằng ~0~) đến mọi nút khác bằng phương tiện này.

Nhắc lại định nghĩa vận tốc và gia tốc:

• Một phương tiện di chuyển với vận tốc ~v~ (mét/giây) đi được khoảng cách là ~v \cdot t~ (mét) trong thời gian ~t~ (giây).

• Một phương tiện đang di chuyển với vận tốc ~v~ (mét/giây) và có gia tốc giới hạn là ~A~ (~\text{mét}/\text{giây}^2~) thì có thể tăng vận tốc thành tối đa là ~v + At~ (mét/giây) trong thời gian ~t~ (giây) (không tính đến các vận tốc giới hạn).

• Giả sử một phương tiện đang di chuyển với vận tốc ~v~ (mét/giây) và tiến hành tăng tốc đều với gia tốc là ~a~ (~\text{mét}/\text{giây}^2~) thì sau ~t~ (giây) phương tiện này có vận tốc là ~v + at~ (mét/giây) và khoảng cách đi được từ khi bắt đầu tăng tốc là ~vt + \frac{at^2}{2}~ (mét).

Input

• Dòng đầu chứa ~4~ số nguyên ~n, m, V, A~ ~(2 \le n, m \le 1024; 1 \le V, A \le 32)~.

• Dòng hai chứa ~n~ số nguyên ~X_1, X_2, \dots, X_n~ là vận tốc giới hạn của các nút giao thông.

• ~m~ dòng tiếp theo, dòng thứ ~j~ chứa ~4~ số nguyên ~a_j, b_j, l_j, v_j~ ~(1 \le a_j, b_j \le n; 1 \le l_j \le 3 \cdot 10^7; 1 \le v_j \le 32)~ biểu diễn một con đường nối giữa hai nút giao thông.

Output

• In ra ~n~ số thực ~d_1, d_2, \dots, d_n~ là thời gian tối thiểu để đi từ nút ~1~ đến từng nút giao thông. Nếu không có đường đi thì ~d_i = -1~, sai số cho phép ~10^{-6}~.

Scoring

Sample Input 1

4 3 10 1
1 5 10 15
1 2 8 10
2 3 100 20
3 4 1250 8

Sample Output 1

0.000000 4.000000 15.800000 172.050000