There was once a travelling merchant who traded bread by travelling on $M$ routes between $N$ cities, with the $j$-th route leading from city $a_j$ to $b_j$, in only that direction. Unfortunately, one day the merchant was robbed of their fortune of bread money. Furious, the local police decided to give chase and catch the robber.

To avoid getting caught, the robber wants to repeatedly travel along the routes between cities. In fact, as long as they are at a city with at least one outgoing route, they will always travel along one of the outgoing routes to the city it leads to. If they ever reach a city with no outgoing routes, they will be cornered and caught by the police.

Furthermore, some cities have police stations ($p_i=1$ if there is a police station in city $i$, and $p_i=0$ otherwise). In cities with a police station, the police can choose an outgoing route (if one exists) and force the robber to take it. For cities without a police station, the robber can freely choose any route leading from that city. Police stations have no other effects on how the robber is caught.

For each of the $N$ cities where the robber could have started from, determine if the police will eventually catch the robber, assuming both the police and robber act optimally.

Constraints

$1\le N\le 5\times {10}^5$

$0\le M\le 5\times {10}^5$

$p_i\in \{0,1\}$

$1\le a_j,b_j\le N$

Subtask 1 [30%]

$a_j\le b_j$ for all $j$.

Subtask 2 [15%]

$p_i=0$ for all $i$.

Subtask 3 [15%]

$p_i=1$ for all $i$.

Subtask 4 [20%]

$1\le N\le 2\times {10}^3$

$0\le M\le 2\times {10}^3$

Subtask 5 [20%]

No additional constraints.

Input Specification

The first line contains $2$ integers $N$ and $M$.

The next line contains $N$ integers $p_i$ $(1\le i\le N)$.

The next $M$ lines each contain $2$ integers $a_j$ and $b_j$. Note that $a_j$ and $b_j$ are not necessarily distinct.

Output Specification

On a single line, output $N$ space-separated integers, where the $i$-th is the answer if the robber were to start at city $i$. The answer is $1$ if the robber will be caught and $0$ otherwise.

Sample Input

5 7
1 0 1 0 1
1 2
2 1
2 3
3 2
1 4
2 4
5 5

Sample Output

1 0 0 1 0

Explanation

If the robber started at city $1$, then the police can force them to city $4$ where they are caught.

If the robber started at either of city $2$ or $3$, then they can avoid being caught by always heading to city $3$ when they are at city $2$.

If the robber started at city $4$, then they are caught immediately.

If the robber started at city $5$, then the police can only force them to keep taking the route from city $5$ back to city $5$ itself, and this does not fall under the definition of being caught.