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>(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 p
L,1, p
L,2,..., p
L,sL, on which vehicles of the L-th line stop, and durations r
L,1, r
L,2,...,r
L,sL-1 of traveling between stations--- r
L,1 is the time necessary to get from the station p
L,1 to the station p
L,2, or vice versa (i.e. from the station p
L,2 to the station p
L,1); r
L,2 is the time necessary to get from the station p
L,2 to p
L,3, etc. All the stations of a line are different (i.e. i != j, implies p
L,i != p
L,j). In the L-th transportation line, buses run with certain frequency c
L, and c
L 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 p
L,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:c
L means c
L minutes after hour g). Buses of the L-th line run in two directions: from the station p
L,1 to p
L,sL, and from the station p
L,sL to p
L,1. The hours of departure of the buses of the L-th transportation line from the station p
L,sL are the same as from the station p
L,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.
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: s
L, the number of stations (2<= s
L <=N), and c
L - the frequency with which the vehicles run (c
L belongs to: {6, 10, 12, 15, 20, 30, 60}).
In the second line describing the L-th transportation line, there are s
L different integers, separated by single spaces: p
L,1,p
L,2,...,p
L,sL --- the numbers of consecutive stations on the transportation line NO. L (1<= p
L,i <=N, for 1<= i <=s
L).In the third line describing the L-th transportation line, there are written s
L-1 integers separated by single spaces: r
L,1, r
L,2,..., r
L,sL-1 --- the times (in minutes) necessary to go between the consecutive stations of this transportation line (1<= r
L,i <=240, for 1<= i <=s
L-1).
The total number of stations on all transportation lines is not greater than 4000 (i.e. s
1+s
2+...+s
K <= 4000).
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.