Thành phố \(S\) có \(N\) thị trấn nhỏ, thị trấn \(i\) có \(C[i]\) người dân sinh sống và giữa 2 thành phố có tối đa một con đường một chiều đi từ thành phố này đến thành phố kia.
Hiện nay thành phố đang chịu ảnh hưởng nghiêm trọng của dịch bệnh, mỗi người dân bị hạn chế đi ra ngoài, bởi vậy nên chính quyền thành phố phải cử bộ đội đi cung cấp nhu yếu phẩm cho mọi người. Giả sử các anh bộ đội xuất phát tại thị trấn \(i\), họ sẽ thông qua những con đường một chiều để đi đến những thị trấn khác, thăm và phát nhu yếu phẩm cho tất cả người dân sinh sống trên thị trấn họ đi qua (lưu ý: mỗi người dân chỉ được thăm và phát nhu yếu phẩm 1 lần).

Yêu cầu đặt ra là với mỗi thị trấn xuất phát, thì có thể thăm và phát nhu yếu phẩm cho tối đa bao nhiêu người dân?

Input

• Dòng đầu tiên gồm 2 số \(N\) và \(M\), tương ứng số thị trấn trong thành phố \(S\), và số con đường một chiều
• Dòng tiếp theo gồm \(N\) số nguyên tương ứng số dân sinh sống tại từng thị trấn
• \(M\) dòng tiếp theo, mỗi dòng gồm 2 số \(u\) và \(v\), tương ứng có con đường từ thị trấn \(u\) đến thị trấn \(v\)

Output

• Gồm một dòng duy nhất ghi \(N\) số nguyên, số thứ \(u\) tương ứng với số người dân tối đa có thể được thăm và phát nhu yếu phẩm nếu như xuất phát tại thị trấn \(u\). Các số cách nhau bởi 1 khoảng trắng.

Scoring

• 30% số tests có \(1 \le N, M \le 1000\)
• 70% số tests có \(1 \le N, M \le 100000\)

Example

7 8
1 2 3 4 5 6 7
1 2
2 3
3 4
4 5
5 2
5 6
5 7
4 7

22 21 21 21 21 6 7