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$