Thầy Hùng là chỉ huy trưởng của một công trình xây nhà lớn. Để hoàn thành ngôi nhà, cần thực hiện \(N\) công đoạn được đánh số từ \(1\) đến \(N\). Công đoạn \(i\) cần một khoảng thời gian thực hiện là \(d_i\) ngày (mỗi công đoạn có thể có thời gian khác nhau). Giữa các công đoạn có \(M\) ràng buộc phụ thuộc: ràng buộc \((u, v)\) nghĩa là công đoạn \(u\) phải được hoàn thành trước khi công đoạn \(v\) được bắt đầu.

Do quy trình thi công được lên kế hoạch bài bản, các ràng buộc phụ thuộc đảm bảo không tạo vòng khép kín (không có chuỗi ràng buộc quay lại chính nó).

Thầy Hùng muốn biết: với kế hoạch hiện tại, thời điểm sớm nhất (tính từ ngày khởi công) mà mỗi công đoạn có thể hoàn thành là ngày thứ bao nhiêu? Hãy giúp thầy tính ra \(N\) con số ứng với từng công đoạn.

Lưu ý:

• Có thể có nhiều công đoạn đầu tiên (không phụ thuộc ai), ta giả định chúng đều được bắt đầu ngay ngày \(0\) và chạy song song với nhau.
• Công đoạn thứ \(i\) được bắt đầu vào ngày muộn nhất trong số các ngày hoàn thành của các công đoạn mà nó phụ thuộc, rồi cộng thêm \(d_i\) ngày để hoàn thành.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^4\), \(0 \le M \le 5 \cdot 10^4\)).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa một số nguyên dương \(d_i\) (\(1 \le d_i \le 10^4\)).
• \(M\) dòng cuối, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le N\), \(u \ne v\)) mô tả ràng buộc phụ thuộc: \(u\) phải xong trước khi \(v\) bắt đầu.

Định dạng đầu ra

• Một dòng duy nhất chứa \(N\) số nguyên, là thời điểm sớm nhất hoàn thành công đoạn \(1, 2, \dots, N\), theo đúng thứ tự, cách nhau bởi một dấu cách.

Ví dụ

Input:

4 3
3
2
4
1
1 2
1 3
2 4

Output:

3 5 7 6

Giải thích:

• Công đoạn \(1\) (3 ngày) bắt đầu ngày \(0\), xong ngày \(3\).
• Công đoạn \(2\) (2 ngày) phụ thuộc \(1\), bắt đầu ngày \(3\), xong ngày \(5\).
• Công đoạn \(3\) (4 ngày) phụ thuộc \(1\), bắt đầu ngày \(3\), xong ngày \(7\).
• Công đoạn \(4\) (1 ngày) phụ thuộc \(2\), bắt đầu ngày \(5\), xong ngày \(6\).

Ràng buộc

• \(1 \le N \le 10^4\)
• \(0 \le M \le 5 \cdot 10^4\)
• \(1 \le d_i \le 10^4\)
• Các ràng buộc đảm bảo không có vòng khép kín.
• Đảm bảo đồ thị ít nhất có một công đoạn đầu tiên (bán bậc vào bằng \(0\)).