Problem Description
Now I'm in my school and I want to go back home as on time. However my bicycle has been stolen, which means I have to take buses. Let's consider the bus-net as a diagram. Vertices of the diagram (numbered 1, 2,..., N), correspond to stations, edges (pi != pj), denote that there is a direct connections from the station pi to the station pj (1<= pi, pj <= N). Transportation lines are numbered 1, 2,..., K. The L-th transportation line is defined as a series of stations pL,1, pL,2,..., pL,sL, on which vehicles of the L-th line stop, and durations rL,1, rL,2,...,rL,sL-1 of traveling between stations--- rL,1 is the time necessary to get from the station pL,1 to the station pL,2, or vice versa (i.e. from the station pL,2 to the station pL,1); rL,2 is the time necessary to get from the station pL,2 to pL,3, etc. All the stations of a line are different (i.e. i != j, implies pL,i != pL,j). In the L-th transportation line, buses run with certain frequency cL, and cL is a number from the set {6, 10, 12, 15, 20, 30, and 60}. The buses in the L-th transportation line, start from the station pL,1 at each hour of the day and night, g:0, (0<= g <=23), and then according to the frequency of the line i.e. at g:cL, g:2cL,... etc. (g:cL means cL minutes after hour g). Buses of the L-th line run in two directions: from the station pL,1 to pL,sL, and from the station pL,sL to pL,1. The hours of departure of the buses of the L-th transportation line from the station pL,sL are the same as from the station pL,1. In such a bus-net, we want to have a trip from the start station X which is near my school to the finish station Y which is near my home. During the trip one can change transportation lines, if he/she wants to. Say, the time of a change is equal to 0, however, while changing the line we have to take under consideration the time of waiting for the bus that we want to get into. Because of my poor memory, I can only change the line in no more than T (1<= T <= 20) times. And your task is to find a way from the start station X, to the finish station Y in W (0<= W <= 1440) minutes and change the lines as few as possible, if there are many ways to go back home and change the same least times of bus, choose the quickest one.
Input
In the first line there are written 8 integers, separated by single spaces:
N (1<= N <=200, number of stations), K (1<= K <=300, number of lines), X (1<= X <=N, the start station), Y (1<= Y <=N, X != Y, the finish station), GX (0<= GX <=23, the hour of the beginning of the trip), MX (0 <= MX <= 59, the minute of the beginning of the trip), W (0<= W <= 1440, the minute you must go back home within), T (1<= T <= 20, the times of changing line).
The stations are numbered from 1 to N, the transportation lines from 1 to K. In the following 3K lines the transportation lines are described - the description of each of them takes three consecutive lines.
In the first line describing the L-th transportation line, there are written two integers, separated by a single space: sL, the number of stations (2<= sL <=N), and cL - the frequency with which the vehicles run (cL belongs to: {6, 10, 12, 15, 20, 30, 60}).
In the second line describing the L-th transportation line, there are sL different integers, separated by single spaces: pL,1,pL,2,...,pL,sL --- the numbers of consecutive stations on the transportation line NO. L (1<= pL,i <=N, for 1<= i <=sL).In the third line describing the L-th transportation line, there are written sL-1 integers separated by single spaces: rL,1, rL,2,..., rL,sL-1 --- the times (in minutes) necessary to go between the consecutive stations of this transportation line (1<= rL,i <=240, for 1<= i <=sL-1).
The total number of stations on all transportation lines is not greater than 4000 (i.e. s1+s2+...+sK <= 4000).
Output
Your program should write in the only line with three integers, separated by a single space: the least times you change the lines, the hour of the earliest possible arrival to the finish station GY (0<= GY <=23) and the minute of the earliest possible arrival to the finish station MY (0<= MY <=59). If I can't go back home within W minutes anyway, puts "NO" in a single line.
Sample Input
6 2 5 6 23 30 1440 20
4 15
1 3 4 6
9 12 10
4 20
5 3 4 2
11 17 11
Sample Output
1 0 16
