The Flight Way

Input

The first line contains $R$ — the maximum direct flight distance (in kilometers, 10 \leq R \leq 50000). The second line contains the number of aerodromes $N$. The next $N$ lines contain the geographic coordinates of the aerodromes. The coordinate format is: first latitude (uppercase letter $N$ or $S$ — North or South, then degrees, minutes, and seconds), then longitude (similar, but using the letter $E$ or $W$ — East or West), all numbers and letters separated by a single space. Degrees and minutes are integers, seconds can have decimal fractions. The last line contains two integers indicating the aerodromes selected as start and finish ($1$-based, i.e., numbering starts from $1$).

Output

Your program should output three lines. The $1$st line should contain one floating-point number — the minimal possible length of the route from start to finish, in kilometers, with accuracy up to meters. The $2$nd line should contain exactly one integer $K$ — the number of intermediate aerodromes on the route. The $3$rd line should contain the list of these intermediate aerodromes in order from start to finish. If there are multiple correct solutions, your program may output any of them. If the plane can fly from start to finish without landings, the $2$nd line should contain $0$ and the $3$rd line should be empty. If the plane cannot reach finish from start, the $1$st line must contain $123456789.000$, the $2$nd — $0$, and the $3$rd must be empty.

Examples