Dragging

Taeyoung and Seunghan went abroad for the year-end holiday. While wandering around, they realized that lunchtime was not far away.

Lunchtime starts in exactly $K$ hours. The two want to eat at the best restaurant they can reach. The problem is that their food tastes are opposite. Taeyoung likes food that is saltier, and Seunghan likes food that is less salty.

The town has $N$ restaurants connected by $M$ roads. Every road takes exactly 10 minutes to travel. Two restaurants may be connected by more than one road, and a road may start and end at the same restaurant. Each restaurant sells exactly one dish. The saltiness of the dish at restaurant $i$ is the integer $C_i$.

Neither of them is willing to give in, and their strength is evenly matched. So for the remaining $K$ hours, they move according to these rules. For the first 20 minutes, Taeyoung drags Seunghan along. For the next 10 minutes, Seunghan drags Taeyoung along. For the next 10 minutes, Taeyoung drags Seunghan along. For the next 20 minutes, Seunghan drags Taeyoung along. These four steps repeat until $K$ hours have passed. For example, with 120 minutes left, the four steps run twice, giving $(20+10+10+20)+(20+10+10+20)$ minutes.

During the time a person is dragging the other, that person may stay still. However, at the end of each turn, both must be at a restaurant. They cannot stop halfway along a road.

Both have a map of the town and move under the rules above, choosing whatever is best for themselves. Taeyoung moves toward the dish with the highest saltiness he can reach, and Seunghan moves toward the dish with the lowest saltiness he can reach. They are currently at restaurant 1. Find the saltiness of the dish that Taeyoung and Seunghan end up eating.

The first line contains $N$, $M$, and $K$ separated by spaces. ($1 \le N \le 2 \times 10^5$, $0 \le M \le 5 \times 10^5$, $0 \le K \le 5 \times 10^5$)

The second line contains $C_1, C_2, \ldots, C_N$ separated by spaces. ($0 \le C_i \le 10^9$)

From the third line through line $M+2$, each line contains two positive integers $S_i$ and $E_i$, meaning restaurant $S_i$ and restaurant $E_i$ are connected by a road. ($1 \le S_i, E_i \le N$)

Print the saltiness of the dish that Taeyoung and Seunghan end up eating on the first line.