A country contains $n$ cities and $m$ train lines. The $i^{th}$ train line works as follows:

A ticket of trains that run on this train line costs $c_i$ dollars. A train on this train line starts its journey from $f_i$ city and ends at $e_i$ city. The total running duration of the train is $t_i$ hours. It departures periodically at every $h_i$ hours. For example, the first train departure at $0$ time, then another train departs at $h_i$, another in $2h_i$, and so on.

Note: You can wait in cities for a train.

The total cost of a path, that takes $H$ hours and costs $C$ dollars, is defined as $A \times H + B \times C$. Initially, you are in city $1$ and you must reach city $n$. Determine the minimum cost to complete this journey.

Input format

• First line: Four integers $n$, $m$, $A$, and $B$ denoting the number of cities, number of train lines, and two parameters that are used in the cost function
• Next $m$ lines: Describes train lines such that the $i^{th}$ line contains the description of the $i^{th}$ train line $f_i$, $e_i$, $t_i$, $c_i$, and $h_i$

Note:

• The train lines are not bidirectional.
• There might be several train lines between the two cities.
• There might be a train line from a city to the same city.

Output format

Print the path from city $1$ to city $n$ that allows you to complete the journey in the minimum cost. Also, print the train lines that you are using in the order. It is guaranteed that there exists a path from city $1$ to city $n$. It is not allowed and inefficient to use the same train line twice.

Constraints

$1 \le n,m \le 10^6\\ 0 \le A, B \le 100\\ 1 \le f_i, e_i \le n\\ 1 \le t_i, c_i, h_i \le 10^6\\ If A = 0,\ then\ B \neq 0$

Test generation and scoring

• In $25\%$ of the test cases, $n \le 1000$
• Value of $n$, $m$, $A$, and $B$ are arbitrary
• Other parts of the input are randomly-generated