여행 계획 (작은 버전)

도시의 대중교통망(버스망, 트램망, 지하철망 등)을 그래프로 나타내자. 그래프의 정점은 $1, 2, \ldots, n$번으로 번호가 매겨진 정거장에 대응하고, 간선 $(p_i, p_j)$($p_i \ne p_j$)는 정거장 $p_i$와 $p_j$ 사이에 직접 연결이 있음을 뜻한다($1 \le p_i, p_j \le n$).

교통 노선은 $1, 2, \ldots, k$번으로 번호가 매겨진다. $l$번 노선은 차량이 정차하는 정거장의 열 $p_{l,1}, p_{l,2}, \ldots, p_{l,s_l}$과, 이웃한 정거장 사이를 이동하는 데 걸리는 시간 $r_{l,1}, r_{l,2}, \ldots, r_{l,s_l-1}$로 정의된다. $r_{l,1}$은 정거장 $p_{l,1}$에서 $p_{l,2}$로(또는 그 반대로) 가는 데 걸리는 시간이고, $r_{l,2}$는 $p_{l,2}$에서 $p_{l,3}$으로 가는 시간이며, 이런 식으로 이어진다. 한 노선에 속한 정거장은 모두 서로 다르다(즉 $i \ne j$이면 $p_{l,i} \ne p_{l,j}$).

$l$번 노선의 차량은 일정한 배차 간격 $c_l$로 운행하며, $c_l$은 집합 $\{6, 10, 12, 15, 20, 30, 60\}$의 원소이다. 차량은 하루 종일 매시 정각(정각을 $g$시 0분이라 하면 $0 \le g \le 23$)에 정거장 $p_{l,1}$에서 출발하고, 그 뒤로는 배차 간격에 맞춰 정각으로부터 $c_l$분 뒤, $2c_l$분 뒤, ... 에 출발한다. $l$번 노선의 차량은 두 방향, 즉 $p_{l,1}$에서 $p_{l,s_l}$ 방향과 $p_{l,s_l}$에서 $p_{l,1}$ 방향으로 모두 운행한다. $p_{l,s_l}$에서 출발하는 차량의 출발 시각도 $p_{l,1}$에서와 동일하다.

이 교통망에서 출발 정거장 $x$에서 도착 정거장 $y$까지 이동하려고 한다. 이 이동은 항상 가능하며 24시간을 넘기지 않는다고 가정한다. 이동 중에는 원하는 만큼 여러 번 노선을 갈아탈 수 있다. 환승 자체에 걸리는 시간은 $0$이지만, 갈아탈 때 타려는 차량을 기다리는 시간은 고려해야 한다. 목표는 출발 정거장 $x$에서 도착 정거장 $y$까지 가능한 한 빨리 도착하는 것이다.

예를 들어 보자. 아래 그림은 정거장이 $6$개이고 노선이 $1$번과 $2$번 두 개인 교통망을 나타낸다. $1$번 노선의 차량은 정거장 $1, 3, 4, 6$ 사이를, $2$번 노선의 차량은 정거장 $2, 4, 3, 5$ 사이를 운행한다. 배차 간격은 각각 $c_1 = 15$, $c_2 = 20$이다. 정거장 사이의 이동 시간은 각 간선 옆에 적혀 있으며, 노선을 구분하기 위해 $1$번과 $2$번 첨자가 붙어 있다.

23시 30분에 정거장 $5$번에 있고 정거장 $6$번으로 가려 한다고 하자. $10$분을 기다린 뒤 23시 40분에 $2$번 노선을 탈 수 있다. 이때 두 가지 경로가 있다. 첫 번째는 23시 51분에 정거장 $3$번에 도착해 $3$분을 기다린 뒤 23시 54분에 $1$번 노선으로 갈아타 다음 날 0시 16분에 정거장 $6$번에 도착하는 것이다. 두 번째는 $2$번 노선을 계속 타서 0시 8분에 정거장 $4$번에 도착한 뒤 $13$분을 기다려 0시 21분에 $1$번 노선을 타고 0시 31분에 정거장 $6$번에 도착하는 것이다. 따라서 정거장 $6$번에 가장 빨리 도착할 수 있는 시각은 0시 16분이다.

다음을 수행하는 프로그램을 작성하시오.

• 표준 입력에서 교통망, 교통 노선, 출발 정거장 번호 $x$, 도착 정거장 번호 $y$, 그리고 이동을 시작하는 시각의 시와 분 $g_x$, $m_x$를 읽는다.
• 출발 정거장 $x$에서 도착 정거장 $y$까지 이동하는 데 걸리는 가장 짧은 시간을 구한다.
• 도착 정거장 $y$에 도착할 수 있는 가장 빠른 시각의 시 $g_y$와 분 $m_y$를 표준 출력에 쓴다.

표준 입력의 첫째 줄에는 공백 하나로 구분된 여섯 개의 정수가 주어진다.

• 정거장의 수 $n$ ($1 \le n \le 1{,}000$)
• 노선의 수 $k$ ($1 \le k \le 2{,}000$)
• 출발 정거장 번호 $x$ ($1 \le x \le n$)
• 도착 정거장 번호 $y$ ($1 \le y \le n$)
• 이동을 시작하는 시각의 시 $g_x$ ($0 \le g_x \le 23$)
• 이동을 시작하는 시각의 분 $m_x$ ($0 \le m_x \le 59$)

정거장은 $1$번부터 $n$번까지, 노선은 $1$번부터 $k$번까지 번호가 매겨진다. 이어지는 $3k$개의 줄에 각 노선의 정보가 주어지며, 한 노선의 정보는 연속한 세 줄에 걸쳐 주어진다.

• $l$번 노선의 첫째 줄에는 공백으로 구분된 두 정수 $s_l$과 $c_l$이 주어진다. $s_l$은 정거장의 수($2 \le s_l \le n$)이고, $c_l$은 배차 간격($c_l \in \{6, 10, 12, 15, 20, 30, 60\}$)이다.
• $l$번 노선의 둘째 줄에는 서로 다른 $s_l$개의 정수 $p_{l,1}, p_{l,2}, \ldots, p_{l,s_l}$이 공백으로 구분되어 주어진다. 이는 $l$번 노선이 지나는 정거장의 번호를 순서대로 나열한 것이다($1 \le p_{l,i} \le n$).
• $l$번 노선의 셋째 줄에는 $s_l - 1$개의 정수 $r_{l,1}, r_{l,2}, \ldots, r_{l,s_l-1}$이 공백으로 구분되어 주어진다. 이는 이 노선의 이웃한 정거장 사이를 이동하는 데 걸리는 시간(분)이다($1 \le r_{l,i} \le 240$).

모든 노선의 정거장 수의 합은 $4{,}000$을 넘지 않는다(즉 $s_1 + s_2 + \cdots + s_k \le 4{,}000$).

표준 출력의 한 줄에 공백으로 구분된 두 정수를 출력한다. 도착 정거장에 가장 빨리 도착할 수 있는 시각의 시 $g_y$ ($0 \le g_y \le 23$)와 분 $m_y$ ($0 \le m_y \le 59$)이다. 도착 시각이 다음 날로 넘어가더라도 하루($24$시간)로 나눈 나머지에 해당하는 시각을 출력한다.