• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

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