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