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

---

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