Let' us consider a diagram describing a net of municipal transportation, for example a bus-net, tram-net or underground-net etc. Vertices of the diagram (numbered 1,2,...,n), correspond to stations, edges (p_i,p_j), (were p_i <>p_j) denote that there is a direct connections from the station p_i to the station p_j (1<=p_i, p_j<=n). Transportation lines are numbered 1,2,...,k. The transportation line no. l is defined as a series of stations p_l,1, p_l,2,...,p_l,sl, on which vehicles of the line no. l 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 transportation line no. l vehicles run with certain frequency c_l, where c_l is a number from the set {6, 10, 12, 15, 20, 30, 60}. The vehicles in the transportation line no. l start from the station p_l,1 at each hour of the day and night, g:0, (0<=g<=23), and than according to the frequency of the line i.e. at g:c_l,g:2c_l,... etc. (g:c_l means c_l minutes after hour g). Vehicles of the line l  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 vehicles of the transportation line no. l from the station p_l,sl are the same as from the station p_l,1. 
In such a transportation net we want to make a trip from the start station x to the finish station y. We assume that the trip is possible and will take no longer than 24 hours. During the trip one can change transportation lines as many times as 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 vehicle that we want to get into. Our purpose is to get from the start station x, to the finish station y, as quick as it is possible. 

Example

On the picture below you can see a scheme of the transportation net with 6 stations and two lines: no. 1 and no. 2. Vehicles of the line no. 1 go between stations 1, 3, 4 and 6, vehicles of the line no. 2 go between stations 2, 4, 3 and 5. The frequencies with which the vehicles run are equal to c₁=15 and c₂=20 respectively. The durations of travel between stations are written next to the edges of the net; they are given indices 1 and 2 for particular lines.

Task

Write a program which:

• reads from the text file POD.IN the description of the transportation net, transportation lines, number of the start station x, number of the finish station y, the hour and minute of the beginning of the trip --- g_x and m_x respectively,
• finds the shortest time of the trip from the start station x to the finish station y,
• writes to the text file POD.OUT the earliest possible time of getting to the finish station y --- g_y and m_y (hour and minute respectively).

Input

In the first line of the text file POD.IN there are written six integers, separated by single spaces:

• the number of stations n (1<=n<=1000),
• the number of lines k (1<=k<=2000),
• the number of the start station x (1<=x<=n),
• the number of the finish station y (1<=y<=n),
• the hour of the beginning of the trip g_x (0<=g_x<=23),
• the minute of the beginning of the trip m_x (0<=m_x<=59). 

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 transportation line no. l 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 transportation line no. l 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 transportation line no. l 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₁+s₂+...+s_k<=4000). 

Output

Your program should write in the only line of the text file POD.OUT two integers, separated by a single space: the hour of the earliest possible arrival to the finish station g_y (0<=g_y<=23) and the minute of the earliest possible arrival to the finish station m_y (0<=m_y<=59).

Example

For the input file POD.IN:

6 2 5 6 23 30
4 15
1 3 4 6
9 12 10
4 20
5 3 4 2
11 17 11

0 16

Print friendly version