Problem: Natsume loves big cats. On Natsume's school road, there is a house commonly known as a cat mansion. The house is famous for having a lot of cats, and Natsume often encountered her cats in front of this house on her way to school and played with them. One day, Natsume learned a shocking fact. It was that the owner of the cat house often abused his cats when he was in a bad mood. Natsume, who couldn't forgive the owner of the cat house, decided to steal the cats while he was away in order to save them.

Natsume observed the behavior pattern of the owner of the cat mansion and decided to steal the cats at the timing when he went out every week. The cat mansion is represented as a two-dimensional plane, and the position of each cat at the time when the jujube sneaks into the mansion is known. The cats are always traveling on a fixed route at a speed of 50 meters per minute. On the other hand, jujube can move at speeds of up to 80 meters per minute. Natsume invades from a certain place in the mansion, moves in the mansion, and exits from the escape exit by the time the master returns. When you reach the same point as the cat, you can hold the cat. The time it takes to do this is negligible. Natsume can carry as many cats as she wants, and even if she holds any number of cats, her movement speed will not slow down, but she must escape from the mansion before her husband returns.

Unfortunately, Natsume may not be able to steal all the cats in the cat house. However, in order to make as many cats happy as possible, I decided to steal as many cats as possible. Also, if you can steal the same number of cats, escape from the mansion as soon as possible to reduce the risk of being caught by the mansion owner.

Given the time and location of the jujube invading the mansion, the time of the mansion owner's return, the location of the escape exit, and the initial location and patrol route of the cat. Write a program that tells you how many cats Natsume can steal and at what time you can escape the mansion.

Notes on Submission

Multiple datasets are given in the above format. The first line of input data gives the number of datasets. Create a program that outputs the output for each data set in order in the above format.



Input

On the first line of input, the x and y coordinates of the entry point are given, separated by a single space character. The second line is also given the location of the escape exit. The third line gives the time when Natsume entered the mansion, and the fourth line gives the time when the owner of the mansion returns in the 24-hour HH: MM: SS format.

The fifth line is the total number of cats m, and the following m lines are given the behavior pattern of each cat. Line 5 + i (i = 1, 2, ..., m) corresponds to the i-th cat's patrol route. The natural number ki is given at the beginning of each line, followed by the traverse route of the cat as a sequence of ki x, y coordinate values. The cat's patrol route is a line segment connecting these consecutive points and the last and first points. When Natsume invades the mansion, the cat is at the first point given and will continue to move at a constant speed on the patrol route. Consecutive points on a given route cannot have the same coordinates.

The start time and goal time are guaranteed to be on the same day. There is always a way for Natsume to escape before her husband returns. All numbers on the same line are separated by a single space character.

The number of cats is 1 or more and 14 or less, the number of points representing the cat's patrol route is 2 or more and 1000 or less, and all coordinate values ​​are guaranteed to be integers whose absolute values ​​do not exceed 100000. The unit of coordinate values ​​is all meters.

Output

On the first line, print the maximum number of cats that Natsume can steal. On the second line, answer in the form of HH MM SS.nnnnnn (blank delimited) the time when you can reach the escape exit earliest among the methods for stealing as many cats as possible. Output 6 digits after the decimal point of the second. There should be no error exceeding 10-6 seconds.

It is guaranteed that the maximum number of encounters will not change even if the return time of the master changes by ± 1 ms.

Example

Input

2
0 0
0 0
15:00:00
18:00:00
1
4 0 7199 1125 7199 1125 8324 0 8324
0 0
0 0
15:00:00
18:00:00
1
4 0 7201 1125 7201 1125 8326 0 8326


Output

1
17 59 59.076923
0
15 00 00.000000

Solution (in CPP):

Solution:
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <complex>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>
using namespace std;
const double EPS = 1e-8;
const double INF = 1e12;
#define EQ(n,m) (abs((n)-(m)) < EPS)
#define X real()
#define Y imag()
typedef complex<double> P;
typedef vector<P> VP;

//ループにおいてcが区間[a,b]に入るか
bool in_range(double a, double b, double c){
    if(a < b) return a<=c && c<=b;
    return c<b || a<c;
}

const double vn = 80.0/60.0; //velocity of natsume (m/s)
const double vc = 50.0/60.0; //velocity of cat (m/s)

//出発座標と現在時刻、巡回ルートと累積和を与え、
//捕まえる座標と時刻を返す
pair<P, double> fastest_catch(P s, double time, VP &route, vector<double> &sumtime){
    int n = route.size();
    //前・後の切れ目になる時刻
    double divtime = time +abs(s -route[0])/vn +sumtime.back()/2;
    divtime = fmod(divtime, sumtime.back());
    
    //二分探索でどの頂点間かを求める
    int sidx, lb=0, ub;
    auto itr = lower_bound(sumtime.begin(), sumtime.end(), divtime);
    if(EQ(*itr, divtime)){
        sidx = itr -sumtime.begin();
        ub = n;
    }else{
        sidx = (itr -sumtime.begin() +n-1) %n;
        ub = n+1;
    }
    int count = 0;
    while(ub -lb > 1){
        if(count++ >10) break;
        int mid = (ub +lb)/2;
        int mididx = (sidx +mid) %n;
        double t = time +abs(s -route[mididx])/vn;
        t = fmod(t, sumtime.back());
        if(in_range(divtime, sumtime[mididx], t)){
            ub = mid;
        }else{
            lb = mid;
        }
    }

    P a=route[(sidx+lb)%n], b=route[(sidx+ub)%n];
    P ab = (b-a)/abs(b-a);
    double dlb=0, dub=abs(a-b);
    for(int rep=0; rep<40; rep++){
        double mid = (dlb +dub) /2.0;
        P midP = a +mid*ab;
        double t = time +abs(s -midP)/vn;
        t = fmod(t, sumtime.back());
        if(in_range(divtime, fmod(sumtime[(sidx+lb)%n] +mid/vc, sumtime.back()), t)){
            dub = mid;
        }else{
            dlb = mid;
        }
    }
    P midP = a +dlb*ab;
    return make_pair(midP, time +abs(s -midP)/vn);
}

int bitcount(int n){
    n = (n & 0x55555555) + (n >> 1 & 0x55555555);
    n = (n & 0x33333333) + (n >> 2 & 0x33333333);
    n = (n & 0x0f0f0f0f) + (n >> 4 & 0x0f0f0f0f);
    n = (n & 0x00ff00ff) + (n >> 8 & 0x00ff00ff);
    return (n & 0x0000ffff) + (n >>16 & 0x0000ffff);
}

int main(){
    int dataset;
    cin >> dataset;
    for(int rep=0; rep<dataset; rep++){
        P s,g;
        {
            int sx,sy,gx,gy;
            cin >> sx >> sy >> gx >> gy;
            s = P(sx, sy);
            g = P(gx, gy);
        }
        int begintime,endtime;
        {
            int hh,mm,ss;
            scanf("%d:%d:%d", &hh, &mm, &ss);
            begintime = hh*3600 +mm*60 +ss;
            scanf("%d:%d:%d", &hh, &mm, &ss);
            endtime = hh*3600 +mm*60 +ss;
        }
        double tlimit = endtime -begintime;

        int n;
        cin >> n;
        //巡回ルート
        vector<VP> route(n);
        for(int i=0; i<n; i++){
            int size;
            cin >> size;
            route[i].resize(size);
            for(int j=0; j<size; j++){
                int x,y;
                cin >> x >> y;
                route[i][j] = P(x, y);
            }
        }
        //各頂点までにかかる時間の累積和
        vector<vector<double> > sumtime(n);
        for(int i=0; i<n; i++){
            int size = route[i].size();
            sumtime[i].resize(size +1);
            sumtime[i][0] = 0;
            for(int j=0; j<size; j++){
                sumtime[i][j+1] = sumtime[i][j] + abs(route[i][j] -route[i][(j+1)%size]) /vc;
            }
        }

        //dp[i][j] = (集合iを確保,最後にjをとったときの最短時刻)
        vector<vector<double> > dp(1<<n, vector<double>(n, INF));
        vector<vector<P> > pos(1<<n, vector<P>(n));
        for(int i=0; i<n; i++){
            auto ret = fastest_catch(s, 0, route[i], sumtime[i]);
            pos[1<<i][i] = ret.first;
            dp[1<<i][i] = ret.second;
        }

        int maxnum = 0;
        double mintime = abs(s -g) /vn;
        for(int i=1; i<(1<<n); i++){
            for(int j=0; j<n; j++){
                if(dp[i][j] == INF) continue;
                //ここから出口に直行しても間に合わないなら打ち切り
                double time = dp[i][j] +abs(pos[i][j] -g)/vn;
                if(time > tlimit) continue;
                //スコア更新(なるべく多く、なるべく早く)
                if(bitcount(i) == maxnum && time < mintime){
                    mintime = time;
                }else if(bitcount(i) > maxnum){
                    maxnum = bitcount(i);
                    mintime = time;
                }
                
                for(int k=0; k<n; k++){
                    if(i>>k & 1) continue;
                    auto ret = fastest_catch(pos[i][j], dp[i][j], route[k], sumtime[k]);
                    if(ret.second < dp[i|(1<<k)][k]){
                        pos[i|(1<<k)][k] = ret.first;
                        dp[i|(1<<k)][k] = ret.second;
                    }
                }
            }
        }

        int integer_part = begintime +mintime +EPS;
        double fractional_part = begintime +mintime -integer_part;
        int hh = integer_part /3600;
        integer_part %= 3600;
        int mm = integer_part /60;
        double ss = integer_part %60 +fractional_part;
        printf("%d\n", maxnum);
        printf("%02d %02d %09.6f\n", hh, mm, ss);
    }
    return 0;
}