Castle

Memory limit: 32 MB

Megachip IV the Splendid, the king of Byteotia, intends to give his pretty daughter, princess Ada, away in marriage. He asked her what husband she wanted to have. The princess answered that she expected her future spouse to be wise, and also neither parsimonious nor squandering. The king pondered on what trials the candidates should be put to in order to choose the best one for his daughter. After long musings he found that it would serve best to use a castle he had built for entertainment of the inhabitants of Byteotia. The castle contains a large number of chambers where treasures of the kingdom are gathered. The chambers, connected by corridors, may be visited by the subjects to admire the wonderful things exhibited there. To visit a chamber one has to pay a certain amount of bytealers (a bytealer is a monetary unit of Byteotia). A visit in the castle begins in the entrance chamber.

The king handed a purse to every candidate for a princess' husband. There was the same amount of bytealers in each purse. He asked each candidate to choose his way of visiting some number of the castle's chambers starting from the entrance one and ending in the one the princess stays in. Each candidate was required to spend on his tour exactly the sum that was in his purse. Squanderers that spent too much money on their way did not reach the princess' chamber. On the other hand the parsimonious candidates appeared there with nonempty purses, and the princess sent them away to empty their purses.

Unfortunately, till now no candidate has managed to cope with the king's task, and the princess is still looking forward to her perfect match. Why don't you want to be put to the test? You may write a program that would help the poor princess.

Task

Write a program which:

• reads from the standard input the description of the castle, the number of the chamber the princess stays in, and the sum in the purse,
• calculates the sequence of chambers one should walk through from the entrance one to the princess' one in order to spend exactly the whole contents of the purse,
• writes the found tour to the standard output.

You may assume that for the test data such a tour always exists. If there are more than one such a tour, your program should calculate arbitrary one of them.

Input

In the first line of the standard input there are five positive integers , , , , , , , , , separated by single spaces. The number is the number of chambers, and is the number of corridors. The chambers are numbered from to . The number is the number of the entrance chamber, and is the number of the princess' chamber. The number is the sum of bytealers in the purse. In the second line there are positive integers , , separated by single spaces. The number is the charge for (each) entering the chamber of number . In the following lines there are pairs of positive integers , , (, ), one pair per line, the numbers are separated by a single space. Each such a pair states that a corridor connects chambers and .

Output

Your program should write in the first (and only) line of the standard output a sequence of positive integers separated by single spaces. The sequence denotes the numbers of successive chambers one should visit, starting from the entrance one and ending in the princess' one, to spend exactly the whole contents of his purse.

Example

For the input data:

5 6 3 4 9
1 2 3 4 5
2 4
5 4
1 5
1 2
2 3
3 1

the correct result is:

3 2 4

Task author: Zbigniew Czech.