Travel Plan (Small)

Consider a diagram of a public transportation network, for example a bus network, tram network, or underground network. The vertices of the diagram, numbered $1, 2, \ldots, n$, correspond to stations, and an edge $(p_i, p_j)$ with $p_i \ne p_j$ means there is a direct connection between stations $p_i$ and $p_j$ ($1 \le p_i, p_j \le n$).

Transportation lines are numbered $1, 2, \ldots, k$. Line $l$ is defined by the sequence of stations $p_{l,1}, p_{l,2}, \ldots, p_{l,s_l}$ where its vehicles stop, together with the travel times $r_{l,1}, r_{l,2}, \ldots, r_{l,s_l-1}$ between consecutive stations: $r_{l,1}$ is the time to go from station $p_{l,1}$ to $p_{l,2}$ (or back), $r_{l,2}$ is the time from $p_{l,2}$ to $p_{l,3}$, and so on. All stations on one line are distinct (that is, $i \ne j$ implies $p_{l,i} \ne p_{l,j}$).

Vehicles on line $l$ run with a fixed frequency $c_l$, where $c_l$ belongs to the set $\{6, 10, 12, 15, 20, 30, 60\}$. Vehicles depart station $p_{l,1}$ at the top of every hour throughout the whole day (an hour mark being minute $0$ of hour $g$ with $0 \le g \le 23$), and then, following the frequency, at $c_l$ minutes, $2c_l$ minutes, and so on after each hour mark. Vehicles of line $l$ run in both directions, from $p_{l,1}$ toward $p_{l,s_l}$ and from $p_{l,s_l}$ toward $p_{l,1}$. The departure times from $p_{l,s_l}$ are the same as from $p_{l,1}$.

In this network we want to travel from a start station $x$ to a finish station $y$. Assume the trip is always possible and takes no longer than 24 hours. During the trip you may change lines as many times as you like. A change itself takes $0$ time, but you must account for the time spent waiting for the vehicle you want to board. The goal is to reach the finish station $y$ from the start station $x$ as early as possible.

For example, the picture below shows a network with $6$ stations and two lines, $1$ and $2$. Vehicles of line $1$ run between stations $1, 3, 4, 6$, and vehicles of line $2$ run between stations $2, 4, 3, 5$. The frequencies are $c_1 = 15$ and $c_2 = 20$. The travel times between stations are written next to the edges, with subscripts $1$ and $2$ to indicate the line.

Suppose that at 23:30 you are at station $5$ and want to reach station $6$. You wait $10$ minutes and then board line $2$ at 23:40. There are two options. In the first, you reach station $3$ at 23:51, wait $3$ minutes, change to line $1$ at 23:54, and arrive at station $6$ at 0:16 the next day. In the second, you stay on line $2$ and reach station $4$ at 0:08, wait $13$ minutes, board line $1$ at 0:21, and arrive at station $6$ at 0:31. Hence the earliest time to reach station $6$ is 0:16.

Write a program that:

• reads from standard input the transportation network, the lines, the start station number $x$, the finish station number $y$, and the hour and minute of the beginning of the trip, $g_x$ and $m_x$;
• finds the shortest travel time from the start station $x$ to the finish station $y$;
• writes to standard output the earliest possible arrival time at the finish station $y$, that is the hour $g_y$ and minute $m_y$.

The first line of standard input contains six integers separated by single spaces:

• the number of stations $n$ ($1 \le n \le 1{,}000$),
• the number of lines $k$ ($1 \le k \le 2{,}000$),
• the start station number $x$ ($1 \le x \le n$),
• the finish station number $y$ ($1 \le y \le n$),
• the hour of the beginning of the trip $g_x$ ($0 \le g_x \le 23$),
• the minute of the beginning of the trip $m_x$ ($0 \le m_x \le 59$).

Stations are numbered from $1$ to $n$, and lines from $1$ to $k$. The following $3k$ lines describe the lines; each description takes three consecutive lines.

• The first line describing line $l$ contains two integers: $s_l$, the number of stations ($2 \le s_l \le n$), and $c_l$, the frequency ($c_l \in \{6, 10, 12, 15, 20, 30, 60\}$).
• The second line describing line $l$ contains the $s_l$ distinct integers $p_{l,1}, p_{l,2}, \ldots, p_{l,s_l}$, the numbers of the consecutive stations on line $l$ ($1 \le p_{l,i} \le n$).
• The third line describing line $l$ contains the $s_l - 1$ integers $r_{l,1}, r_{l,2}, \ldots, r_{l,s_l-1}$, the times in minutes to travel between consecutive stations of the line ($1 \le r_{l,i} \le 240$).

The total number of stations over all lines is at most $4{,}000$ (that is, $s_1 + s_2 + \cdots + s_k \le 4{,}000$).

Print a single line with two integers separated by a single space: the hour $g_y$ ($0 \le g_y \le 23$) and the minute $m_y$ ($0 \le m_y \le 59$) of the earliest possible arrival at the finish station. If the arrival falls on the next day, print the clock time taken modulo one full day (24 hours).