A country consists of \(n\) cities and \(m\) one-way roads. There is a central city with number \(s \). Each city sells a particular sweet (city \(i\) sells sweets of value \(v[i]\)).

You are required to go to city \(d\). If you are currently in city \(x\), then you can randomly select and move to one of the cities that is directly reachable from \(x\) through a single road. You can perform this technique until you reach city \(d\). You must stop once you reach the destination city.

You can buy sweets only once on your way. Determine the highest value \(p\) such that you can take home a sweet whose value is at least \(p\) independent of the path that you take. Print the value of \(p\) for each destination city \(d\) from \(1\) to \(n\).

Note

It is guaranteed that all the cities are reachable from the central city.
You can not select a road that does not lead to the destination.
There are multiple test cases in a single input file.

Input format

First line: An integer \(t\) denoting the number of test cases
For each test case:
- First line: Three integers \(n\), \(m\), and \(s\)
- Next line: \(n\) integers denoting the value of a sweet that is sold in each city
- Next \(m\) lines: Two integers \(u\) and \(v\) denoting a directed road from city \(u\) to \(v\)

Output format

For each test case, print \(n\) space-separated integers denoting the answer to each destination city.

Constraints

\(1 \leq t \leq 3\)

\(1\le n,u,v,s\le10^5\)

\(1\le m\le2*10^5\)

\(1\le v[i]\le10^6\)