Byteotia 的国王，伟大的 Megachip 四世，打算将他美丽的女儿 Ada 公主许配给人。他问她想要一个什么样的丈夫。公主回答说，她希望未来的配偶既聪明，又既不吝啬也不挥霍。国王思考着应该对候选人进行怎样的考验，以便为女儿挑选出最合适的人选。经过长期的沉思，他觉得最好利用他为 Byteotia 居民娱乐而建造的一座城堡。城堡里有大量的房间，里面收集了王国的珍宝。这些房间由走廊连接，臣民们可以前去参观，欣赏那里展出的奇珍异宝。每参观一个房间，必须支付一定数量的 Byte 币（Byte 币是 Byteotia 的货币单位）。城堡的参观从入口房间开始。

国王给每位公主丈夫的候选人发了一个钱包。每个钱包里装有相同数量的 Byte 币。他要求每位候选人选择一条路线，参观城堡中的若干个房间，从入口房间开始，到公主所在的房间结束。每位候选人都必须在旅途中恰好花光钱包里的所有钱。挥霍无度、在途中花钱太多的候选人无法到达公主的房间。另一方面，吝啬的候选人到达时钱包里还有余钱，公主会把他们打发走，让他们去花光钱包。

不幸的是，到目前为止，还没有候选人能够完成国王的任务，公主仍然在期待着她的完美伴侣。你为什么不来接受这个考验呢？你可以编写一个程序来帮助这位可怜的公主。

任务

编写一个程序：

• 从标准输入读取城堡的描述、公主所在的房间编号以及钱包中的金额。
• 计算一条从入口房间到公主房间的房间序列，使得沿途的花费恰好等于钱包中的全部金额。
• 将找到的路线输出到标准输出。

你可以假设对于测试数据，这样的路线总是存在的。如果存在多条满足条件的路线，你的程序只需输出其中任意一条。

输入格式

第一行包含五个正整数 $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 1\,000$），它们之间用单个空格分隔。其中 $n$ 表示房间的数量，$m$ 表示走廊的数量。房间从 $1$ 到 $n$ 进行编号。$e$ 是入口房间的编号，$p$ 是公主所在房间的编号。$b$ 是钱包中 Byte 币的总数。

第二行包含 $n$ 个正整数 $c_1,c_2,\ldots,c_n$（$1 \le c_i \le 1\,000$），它们之间用单个空格分隔。其中 $c_i$ 表示（每次）进入编号为 $i$ 的房间所需支付的费用。

接下来的 $m$ 行中，每行包含一对正整数 $x$, $y$（$x\ne y$, $1 \le x,y \le n$），用单个空格分隔。每一对表示有一条走廊连接房间 $x$ 和 $y$。

输出格式

输出仅一行，包含一个由正整数组成的序列，数与数之间用单个空格分隔。该序列表示依次访问的房间编号，从入口房间开始，到公主所在的房间结束，使得沿途的总花费恰好等于钱包中的全部金额。

样例

输入样例 1

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

输出样例 1

3 2 4