+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- It is the well-known annual day *"Tavalbao"* , *Shengdebao*'s birthday! In his birthday he has received gifts from all his friends and relatives. One particular present appeared the most interesting, A digraph (Directed Graph) which has $n$ vertices and $m$ directed edges. On vertex $i$ number $a_i$ is written. After his birthday party *Shengdebao* got bored and started traversing the graph. He decided to start from an arbitrary vertex $v$ and start traversing some edges in their directions. While doing so, he wanted to keep track of a number $x$. Initially number $x$ is equal to $a_v$ (the label written on the starting vertex) after passing an edge $a \to b$ he will write $a_b$ after the last digit of $x$. For example if he starts from vertex $2$ with label $123$ and goes to vertex $1$ with label $78$ we will have $x = 12378$. He intends to traverse over a walk (this walk can contain repeated edges or vertices) and write down number $x$ so that $x$ has exactly $k$ digits, since $k$ is his favorite number, and between all the available ways, $x$ should be **maximized**. You're *Shengdebao*'s friend so give the guy a hand and help him! # ورودی In the first line numbers $n , m , k$ are given denoting the number of vertices , edges and *Shengdebao*'s favorite number in order. Next line contains $n$ integers one after another, $i$th integer is equal to $a_i$. (the number written on vertex $i$) Afterwards $m$ lines each consisting of two integers $u , v$ are given showing edge $u \to v$ exists in the graph. $$ 1 \le u,v \le n $$ $$ n,m,k \le 1\ 000 $$ $$1 \le a_i \le 100\ 000 $$ The graph can contain loops or multiple edges. # خروجی In the only line of output display the $k$ digit number $x$ that is maximized. Display $-1$ if no answer exists! # مثال ## ورودی نمونه ۱ ``` 5 4 3 4 12 3 1 1 1 2 2 3 1 4 4 5 ``` ## خروجی نمونه ۱ ``` 412 ``` ## ورودی نمونه ۲ ``` 3 3 8 1 2 3 1 2 2 3 3 1 ``` ## خروجی نمونه ۲ ``` 31231231 ``` ## ورودی نمونه ۳ ``` 3 3 8 12 251 3200 1 2 2 3 3 1 ``` ## خروجی نمونه ۳ ``` -1 ```