작업 순서

N개의 작업에 수행 시간과 선행 관계가 있다. 선행 작업이 모두 끝나야 해당 작업을 시작할 수 있다. 각 작업이 완료되는 최소 시간을 구한다.

위상 정렬 + DP로 각 작업의 최소 시작 시간을 구한 뒤, 수행 시간을 더해 완료 시간을 구한다.

입력

첫째 줄에 작업 수 N과 간선 수 M이 주어진다.

둘째 줄에 각 작업의 수행 시간이 공백으로 구분되어 주어진다.

다음 M개 줄에 선행 관계 A B가 주어진다 (A가 끝나야 B를 시작할 수 있다).

• 1 ≤ N ≤ 10,000
• 0 ≤ M ≤ 100,000
• 1 ≤ 수행 시간 ≤ 1,000

출력

각 작업이 완료되는 최소 시간을 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1

5 5
5 2 3 8 4
1 2
1 3
3 4
2 4
4 5

예제 출력 1

5
7
8
16
20