Campus

All buildings in the newly built campus of the Humanities University of Jaromír Jágr (HUJAJÁ) are to be intreconnected via cutting edge technology quantum cables. There will be a connection between any two buildings. The connection need not to be direct, the signal travelling from building x to building y may go through any number of other buildings. A connection is always automatically bi-directional. The exact cost of construction of a direct connection between any two buildings is known and also it can be easily calculated by a special function, which we provide for convenience in the input section bellow .

The management of the university also wants to choose some buildings in the campus which will be connected, this time using standard technology only, to the city backbone network which lies entirely outside the campus. Although the buildings have not been chosen yet their number K is known in advance and is fixed. The connection to the backbone will be completely funded by the city, consequently its cost is of no immediate interest to the university.

The university has won a state grant, which will partially pay for construction of the campus network in the following manner. The grant specifies an integer discount constant 0 ≤ D ≤ 100. Suppose there will be a quantum cable directly connecting buildings b₁ and b₂. If any of the buidings b₁, b₂ will be among the chosen buildings connected to the city backbone then D/100 of the cost of the connection between b₁ and b₂ will be subsidized by the grant.

The university management wants to complete the whole project as economically as possible from their point of view. This means that they have to choose K buildings connecting the campus to the backbone so that the cost of construction of the campus quantum network including the grant support is minimal.

Input

Input is a single text line with five nonnegative integers separated by one or more spaces. First two numbers N and K represent the number of buildings in the campus and the number of buildings to be connected to the backbone, respectively.
The cost of constructing a direct quantum cable connection between two buildings in the campus is specified by next two integers p₁ and p₂. The buildings in the campus are labeled 0, 1, ... , N−1. Any pair of buildings (b₁, b₂) is uniquely identified by its identifier number
ID(b₁,b₂) = 1 + min(b₁, b₂) + max(b₁, b₂) ×(max(b₁, b₂) − 1)/2.
The cost of the direct connection of the pair (b₁, b₂) is then calculated as c(b₁,b₂) = (p₁ × ID(b₁,b₂)) mod p₂.
The last value D on the input line specifies the discount constant.
For input values holds: 2 ≤ N ≤ 100, 1 ≤ K ≤ 2, p₁ ≤ 10⁹, 2 ≤ p₂ ≤ 10⁹, 0 ≤ D ≤ 100.

Output

The output consists of two text lines. The first line contains two numbers A and B. Number A is the cost of optimal campus cable connection without the state grant support (or equivalently with the grant support specifying D = 0). Number B is the cost of optimal campus cable connection supported by the state grant. Both number A and B are decimal fractions always with two fraction digits after the decimal dot.
The second line of the output specifies the set of buildings which will be connected to the backbone. Each building is represented by its number in the campus and the numbers are printed in ascending order. If there is more than one possibility to choose the buildings then the second output line specifies the set represented by the lexicographically smallest possible sequence of numbers of buildings.
All output values are separated by at least one space.

Implementation note

Check whether 4-byte integer will always sufficiently represent the cost of the connection between two buildings.

Example 1

Input:

4 1 3 13 10 

Output:

10.00 9.30 
3 

Example 2

Input:

5 2 4 17 40 

Output:

15.00 9.00 
1 4 

Example 3

Input:

100 2 1024 133117 80 

Output:

168892.00 106976.20 
0 51 

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout a stderr is available to him/her.

Public data