Castle

Megachip IV the Splendid, king of Byteotia, wants to marry off his daughter, princess Ada. When he asked what kind of husband she wanted, she said her future spouse should be wise, and neither stingy nor wasteful. To find such a man, the king decided to test each candidate using a castle he had built for the people of Byteotia.

The castle has many chambers where the kingdom's treasures are displayed. Chambers are joined by corridors, and one may move between two chambers only if a corridor connects them. Entering a chamber costs a fixed number of bytealers (the currency of Byteotia); every time you enter a chamber you pay its charge again. A visit always begins in the entrance chamber, and its charge is paid as well.

The king gave every candidate a purse holding the same amount of bytealers. Each candidate must walk from the entrance chamber to the chamber where the princess waits and, along the way, spend exactly the amount in the purse. A candidate who spends too much never reaches the princess; a candidate who arrives with money left over is sent back. A walk may pass through the same chamber more than once, and every visit is charged.

Given the castle, the princess' chamber and the amount in the purse, write a program that prints a walk from the entrance chamber to the princess' chamber whose total charge equals exactly the amount in the purse. The test data always admit at least one such walk.

The first line contains five positive integers $n$, $m$, $e$, $p$, $b$ separated by single spaces, where $1 \le n \le 100$, $1 \le m \le 4950$, $1 \le e, p \le n$ and $1 \le b \le 1000$. Here $n$ is the number of chambers and $m$ the number of corridors; chambers are numbered from $1$ to $n$. Chamber $e$ is the entrance and chamber $p$ is the princess' chamber, and $b$ is the amount of bytealers in the purse.

The second line contains $n$ positive integers $c_1, c_2, \ldots, c_n$ with $1 \le c_i \le 1000$, separated by single spaces; $c_i$ is the charge for entering chamber $i$.

Each of the next $m$ lines contains two positive integers $x$ and $y$ ($x \ne y$, $1 \le x, y \le n$) separated by a single space, meaning a corridor joins chambers $x$ and $y$.

Print, on a single line, the chamber numbers of one valid walk separated by single spaces: the walk starts at the entrance chamber $e$, ends at the princess' chamber $p$, and its total charge (summed over every chamber it enters, counting repeated visits) equals exactly $b$.

If several walks are possible, print the lexicographically smallest one. Compare two walks as sequences of chamber numbers: at the first position where they differ, the walk with the smaller chamber number there is the smaller walk.