성

바이트국의 국왕 메가칩 4세는 딸 아다 공주를 시집보내려 한다. 어떤 남편을 원하느냐는 물음에 공주는 지혜롭고 인색하지도 낭비하지도 않는 사람이길 바란다고 답했다. 국왕은 이런 사윗감을 가려내기 위해, 백성들을 위해 지어 둔 성을 이용해 후보들을 시험하기로 했다.

성에는 왕국의 보물이 전시된 방이 여러 개 있다. 방들은 복도로 연결되어 있고, 두 방 사이에 복도가 있을 때에만 그 사이를 오갈 수 있다. 방에 들어갈 때마다 정해진 바이트달러(바이트국의 화폐 단위)를 내야 하며, 같은 방에 다시 들어가면 그만큼 또 내야 한다. 방문은 항상 입구 방에서 시작하고, 입구 방에 들어갈 때에도 그 방의 입장료를 낸다.

국왕은 모든 후보에게 같은 금액이 든 지갑을 하나씩 주었다. 각 후보는 입구 방에서 출발해 공주가 있는 방까지 이동하되, 그 과정에서 지갑에 든 금액을 정확히 다 써야 한다. 너무 많이 쓴 후보는 공주에게 닿지 못하고, 돈이 남은 채 도착한 후보는 되돌려 보내진다. 경로는 같은 방을 여러 번 지날 수 있으며, 지날 때마다 입장료를 낸다.

성의 구조, 공주가 있는 방, 지갑에 든 금액이 주어질 때, 입구 방에서 공주의 방까지 이동하면서 드는 입장료의 합이 지갑의 금액과 정확히 같아지는 경로 하나를 출력하는 프로그램을 작성하라. 입력으로 주어지는 자료에는 그런 경로가 항상 하나 이상 존재한다.

첫째 줄에 다섯 개의 양의 정수 $n$, $m$, $e$, $p$, $b$가 공백 하나로 구분되어 주어진다. 이때 $1 \le n \le 100$, $1 \le m \le 4950$, $1 \le e, p \le n$, $1 \le b \le 1000$이다. $n$은 방의 수, $m$은 복도의 수이며, 방은 $1$번부터 $n$번까지 번호가 매겨져 있다. $e$는 입구 방의 번호, $p$는 공주가 있는 방의 번호이고, $b$는 지갑에 든 바이트달러의 액수다.

둘째 줄에는 $n$개의 양의 정수 $c_1, c_2, \ldots, c_n$이 공백 하나로 구분되어 주어진다($1 \le c_i \le 1000$). $c_i$는 $i$번 방에 들어갈 때 내는 입장료다.

다음 $m$개의 줄에는 각각 두 양의 정수 $x$, $y$가 공백 하나로 구분되어 주어진다($x \ne y$, $1 \le x, y \le n$). 이는 $x$번 방과 $y$번 방을 잇는 복도가 있음을 뜻한다.

한 줄에, 조건을 만족하는 경로 하나에 포함된 방 번호들을 공백 하나로 구분해 출력한다. 이 경로는 입구 방 $e$에서 시작해 공주의 방 $p$에서 끝나며, 지나는 모든 방(같은 방을 여러 번 지나면 그만큼 여러 번 더한다)의 입장료 합이 정확히 $b$가 되어야 한다.

가능한 경로가 여러 개라면 사전순으로 가장 앞서는 것을 출력한다. 두 경로를 방 번호의 수열로 보고 앞에서부터 비교하여, 처음으로 달라지는 자리에서 방 번호가 더 작은 쪽이 사전순으로 앞선다.