질질 끌기

태영이와 승한이는 연말을 맞아 해외 여행을 떠났다. 여행지를 돌아다니던 둘은 점심시간이 얼마 남지 않았다는 것을 깨달았다.

점심시간은 정확히 $K$시간 뒤에 시작된다. 둘은 갈 수 있는 곳 중 가장 괜찮은 음식점에서 식사하고 싶다. 문제는 둘의 음식 취향이 정반대라는 것이다. 태영이는 음식이 짤수록 좋아하고, 승한이는 음식이 싱거울수록 좋아한다.

마을에는 $N$개의 음식점이 있고, 이들은 $M$개의 길로 연결되어 있다. 모든 길을 지나는 데 정확히 10분이 걸린다. 두 음식점을 잇는 길이 여러 개 있을 수도 있고, 한 음식점에서 출발해 같은 음식점으로 돌아오는 길이 있을 수도 있다. 각 음식점은 음식을 정확히 하나만 판매하며, $i$번 음식점이 파는 음식의 짠 정도는 정수 $C_i$로 나타낸다.

둘은 상대에게 양보할 생각이 전혀 없고 힘이 팽팽하다. 그래서 남은 $K$시간 동안 다음 규칙에 따라 이동한다. 처음 20분 동안은 태영이가 승한이를 질질 끌고 간다. 다음 10분 동안은 승한이가 태영이를 끌고 간다. 그다음 10분 동안은 태영이가 승한이를 끌고 간다. 마지막으로 20분 동안은 승한이가 태영이를 끌고 간다. 이 네 단계가 총 $K$시간 동안 반복된다. 예를 들어 120분이 남았다면 네 단계를 두 번 반복해 $(20+10+10+20)+(20+10+10+20)$분이 지난다.

자신이 상대를 끌고 가는 시간에는 움직이지 않고 멈춰 있을 수도 있다. 하지만 각 차례가 끝날 때는 둘 모두 반드시 어떤 음식점에 있어야 한다. 길 중간에 멈춰 설 수는 없다.

둘은 마을 지도를 가지고 있고, 위 규칙대로 움직이되 자신에게 가장 이득이 되는 방향으로 움직인다. 태영이는 도달할 수 있는 음식 중 짠 정도가 가장 높은 음식을 향해, 승한이는 가장 싱거운 음식을 향해 움직인다. 둘은 현재 1번 음식점에 있다. 이때 태영이와 승한이가 먹게 될 음식의 짠 정도를 구하라.

첫 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어진다. ($1 \le N \le 2 \times 10^5$, $0 \le M \le 5 \times 10^5$, $0 \le K \le 5 \times 10^5$)

둘째 줄에 $C_1, C_2, \ldots, C_N$이 공백으로 구분되어 주어진다. ($0 \le C_i \le 10^9$)

셋째 줄부터 $M+2$번째 줄까지 각 줄에 두 자연수 $S_i$와 $E_i$가 주어진다. 이는 $S_i$번 음식점과 $E_i$번 음식점이 도로로 연결되어 있다는 뜻이다. ($1 \le S_i, E_i \le N$)

태영이와 승한이가 먹게 될 음식의 짠 정도를 첫 줄에 출력한다.