Earliest Task Start Times

You are given a set of tasks, each with a specified duration, and a list of dependencies between these tasks. A dependency (u, v) means that task v cannot start until task u has finished. Your task is to compute the earliest possible start time for each task, assuming that tasks with no dependencies can start at time 0.

Formally, let \( T \) be the number of tasks and \( durations[i] \) be the time taken by the \( i^{th} \) task. For each dependency \( (u,v) \), task \( v \) cannot start until task \( u \) is finished. The start time of a task is defined as the maximum finish time among all of its prerequisite tasks. If a task has no prerequisites, its start time is \( 0 \).

Your solution should read input from stdin and output the result to stdout.

inputFormat

The input is read from standard input and has the following format:

T
durations[0] durations[1] ... durations[T-1]
D
u1 v1
u2 v2
...
uD vD

Where:

• T is the number of tasks (an integer).
• The next line contains \( T \) space-separated integers representing the durations of the tasks.
• D is the number of dependency pairs.
• Each of the following \( D \) lines contains two integers \( u \) and \( v \) (0-indexed) indicating that task \( v \) depends on task \( u \).

outputFormat

Output a single line containing \( T \) space-separated integers, where the \( i^{th} \) integer is the earliest start time of task \( i \).

## sample

3
2 3 5
2
0 1
1 2

0 2 5

</p>