Description

NJU这个月又开展了一年一度的运动会，其中有一个项目是双人布袋跳接力赛，规定两个人一组共同装入一个布袋，挑选不同的路径前往指定的终点，并且每到达一个接力点有一个人等待和其中一个同学交接，前往下一个接力点，其中交接的时间不计，并且每位同学最多参与两段路程。布袋跳的速度只与两人的总体重成反比，最早到达指定点的队伍获胜。为保证游戏的正常进行，指定点均能顺利到达且只有一种最佳方案。现在，你和你室友参加了这个比赛项目，请你帮忙自己的队伍选择最佳的策略最早到达指定点。

Format

Input

第一行包含交接点的总数\(n\)，路径条数\(m\)，以及起点处两位学生的体重\(w_1\)，\(w_2\)，其中\(0<n, m\leq 50\)。
接下来\(n\)个整数为分别站在编号为\(1\sim n\)的交接点处的学生的体重。
接下来\(m\)行为每条单向路径的起点编号、终点编号，以及路径的长度。0为全程起点的编号。所有学生体重以及路径长度小于\(10^4\)且均为正整数。
最后输入指定的终点的编号\(t\)，\(0<t\leq n\)。

Output

按顺序输出最快到达指定点\(t\)的路径编号序列，其中起点为0，终点为\(t\)，编号间以空格隔开。

Sample

Input

4 6 7 10
5 9 7 6
0 1 5
0 2 5
1 2 2
2 4 4
2 3 6
4 3 2
3

Output

0 2 4 3

Limitation

1s, 1024KiB for each test case.

Hint

对于样例中的情形，体重为7和10的同学先前往2号交接点，将10换下后7和9前往4号交接点，这时7已经走了两段路程，于是将7换下，6和9共同前往指定点3.