Commute War (Large)

Yeongsu starts his first job next week. Seoul has dense public transit, but for some reason the police now inspect every service. To avoid being late, Yeongsu collected the timetable and the expected delay of every service along the junctions between his home and the office. Find the expected time it takes him to reach the office.

The junctions are numbered $0$ through $N-1$. Service $i$ runs like this.

• It leaves its origin junction $A_i$ at minute $S_i$ of every hour, that is at times $S_i$, $S_i + 60$, $S_i + 120$, ..., where time is measured in minutes.
• The ride to its destination junction $B_i$ takes $R_i$ minutes.
• The police inspect the vehicle during the ride. The inspection itself takes no time, but with probability $P_i$% something is wrong and the vehicle is delayed by $D_i$ minutes. When the delay ends the same inspection happens again, and again it delays the vehicle by $D_i$ minutes with probability $P_i$%. The inspection repeats without limit until it passes. If the delay happens $k$ times, the ride takes $R_i + k \times D_i$ minutes from departure to arrival.
• Once Yeongsu boards, he cannot get off before the destination junction.

A service with $P_i = 100$ never passes the inspection, so it never reaches its destination junction.

Yeongsu is at junction $H$, where his home is, at time $0$, and the office is at junction $O$. If he is at a junction exactly at the departure time of a service leaving that junction, he boards it without waiting. Every time he reaches a junction he knows the current time, and he takes the service that minimizes the expected remaining time. If the home and the office are the same junction, the time is $0$.

The first line has the number of test cases $T$. Each test case has the following form.

N M H O
A[0] B[0] S[0] R[0] D[0] P[0]
...
A[M-1] B[M-1] S[M-1] R[M-1] D[M-1] P[M-1]

The first line of a test case has four integers. $N$ is the number of junctions, $M$ is the number of services, $H$ is the junction of the home, and $O$ is the junction of the office. Each of the next $M$ lines describes one service with six integers, in order: the origin junction $A_i$, the destination junction $B_i$, the departure minute $S_i$, the ride time $R_i$, the delay $D_i$, and the delay probability $P_i$ given as a percentage.

Limits

• $1 \le T \le 100$
• $2 \le N \le 100$
• $0 \le M \le N \times (N - 1)$
• $0 \le H, O, A_i, B_i < N$
• $0 \le S_i \le 59$
• $1 \le R_i \le 100$
• $1 \le D_i \le 100$
• $0 \le P_i \le 100$
• $A_i \ne B_i$ for every $i$
• $A_i \ne A_j$ or $B_i \ne B_j$ for every pair with $i < j$

For each test case, print one line of the form Case #x: y. $x$ is the test case number starting from $1$, and $y$ is the expected time to reach the office, rounded to seven decimal places. Always print seven digits after the decimal point. If the office cannot be reached, print -1 in place of $y$, with no decimal point.