출근 전쟁 (Large)

문제

영수는 다음 주에 첫 출근을 한다. 서울의 대중교통은 촘촘하지만, 어떤 사정으로 모든 교통편이 경찰의 검문을 받게 되었다. 지각하지 않으려고 영수는 집에서 회사까지 이어지는 길목마다 교통편 시간표와 예상 지연 시간을 미리 모아 두었다. 회사에 도착할 때까지 걸리는 시간의 기댓값을 구하라.

길목에는 $0$ 번부터 $N-1$ 번까지 번호가 붙어 있다. 교통편 $i$ 는 다음과 같이 움직인다.

출발 길목 $A_i$ 에서 매시 $S_i$ 분에 출발한다. 즉 시각 $S_i$ , $S_i + 60$ , $S_i + 120$ , ...에 출발하고, 시각의 단위는 분이다.
도착 길목 $B_i$ 까지 가는 데 $R_i$ 분이 걸린다.
이동 도중에 경찰의 검문을 받는다. 검문 자체에는 시간이 들지 않지만 $P_i$ %의 확률로 문제가 생겨 $D_i$ 분 동안 지연된다. 지연이 끝나면 같은 검문을 다시 받고, 이때도 $P_i$ %의 확률로 또 $D_i$ 분 지연된다. 검문은 통과할 때까지 무한히 되풀이된다. 지연이 $k$ 번 일어나면 출발부터 도착까지 $R_i + k \times D_i$ 분이 걸린다.
한 번 타면 도착 길목에 닿기 전에 내릴 수 없다.

$P_i$ 가 $100$ 인 교통편은 검문을 끝내 통과하지 못하므로 도착 길목에 닿지 못한다.

영수는 시각 $0$ 에 집이 있는 길목 $H$ 에 있고, 회사는 길목 $O$ 에 있다. 어떤 길목에 있는 시각이 그 길목에서 출발하는 교통편의 출발 시각과 정확히 같으면 기다리지 않고 바로 탄다. 길목에 닿을 때마다 영수는 그 시각을 알고 있고, 남은 시간의 기댓값이 가장 작아지는 교통편을 고른다. 집과 회사가 같은 길목이면 걸리는 시간은 $0$ 이다.

입력

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다. 각 테스트 케이스는 다음 형식이다.

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]

각 테스트 케이스의 첫 줄에는 정수 네 개가 주어진다. $N$ 은 길목의 수, $M$ 은 교통편의 수, $H$ 는 집이 있는 길목 번호, $O$ 는 회사가 있는 길목 번호이다. 이어지는 $M$ 개의 줄에는 교통편 하나의 정보가 정수 여섯 개로 주어진다. 차례대로 출발 길목 $A_i$ , 도착 길목 $B_i$ , 출발 분 $S_i$ , 이동 시간 $R_i$ , 지연 시간 $D_i$ , 지연 확률 $P_i$ 이고, $P_i$ 는 백분율이다.

제한

$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$
모든 $i$ 에 대해 $A_i \ne B_i$
$i < j$ 인 모든 쌍에 대해 $A_i \ne A_j$ 또는 $B_i \ne B_j$

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$ 는 $1$ 부터 시작하는 테스트 케이스 번호이고, $y$ 는 회사에 도착할 때까지 걸리는 시간의 기댓값을 소수점 아래 일곱째 자리까지 반올림한 값이다. 소수점 아래 자리는 항상 일곱 자리를 채운다. 회사에 도착할 수 없으면 $y$ 자리에 소수점 없이 -1을 출력한다.