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 <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

#include <complex>
typedef complex<double> Point;

int HtoS(int h, int m, int s) {
  return h * 3600 + m * 60 + s;
}
string StoH(double sec) {
  int h = (int)sec / 3600;
  int m = (int)sec % 3600 / 60;
  double ms =  sec - (h * 3600 + m * 60);
  char str[1000];
  sprintf(str, "%02d %02d %02d.%08d", h, m, (int)ms, (int)((ms - (int)ms) * 100000000 + 0.5));
  return str;
}

struct State {
  int use;
  double t;
  Point p;
  int last;
  State() {;}
  State(int use, double t, Point p, int last) : use(use), t(t), p(p), last(last) {;}
  bool operator<(const State &rhs) const {
    return t > rhs.t;
  }
};

const double SPEED_N = 80.0 / 60.0;
const double SPEED_C = 50.0 / 60.0;
Point sp, ep;
int startTime;
int endTime;
int n;
vector<Point> route[20];
vector<double> ts[20];

int bisect(State state, int target) {
  int lower = 0;
  int upper = 1 << 20;
  while (lower != upper) {
    int mid = (lower + upper) / 2;
    int cycle = mid / ts[target].size();
    int index = mid % ts[target].size();
    double et = cycle * ts[target].back() + ts[target][index] + startTime;
    Point p = route[target][(index + 1) % route[target].size()];
    if (abs(state.p - p) / SPEED_N - (et - state.t) <= -EPS) {
      upper = mid;
    } else {
      lower = mid + 1;
      if (et >= endTime) { break; }
    }
  }
  return lower;
}

pair<double, Point> calc(State state, int target) {
  int from = bisect(state, target);
  double lower;
  double upper;
  {
    int cycle = from / ts[target].size();
    int index = from % ts[target].size();
    lower = cycle * ts[target].back() + startTime;
    if (index != 0) {
      lower += ts[target][index - 1];
    }
    upper = cycle * ts[target].back() + ts[target][index] + startTime + EPS * 10;
  }
  double stime = lower;
  pair<double, Point> ret(endTime + 1, Point(0, 0));
  if (lower > endTime) { return ret; }
  from %= ts[target].size();
  Point vect = route[target][(from + 1) % route[target].size()] - route[target][from];
  vect /= abs(vect);
  bool ok = false;
  REP(i, 50) {
    double mid = (lower + upper) / 2.0;
    double t = mid - stime;
    Point tp = route[target][from] + vect * (t * SPEED_C);
    if (abs(state.p - tp) / SPEED_N <= mid - state.t) {
      upper = mid;
      ret = make_pair(mid, tp);
      ok = true;
    } else {
      lower = mid;
    }
  }
  double t = lower - stime;
  Point tp = route[target][from] + vect * (t * SPEED_C);
  //cout << abs(state.p - tp) / SPEED_N << " " << lower - state.t << endl;
  assert(ok);
  return ret;
}

bool visit[1 << 14][15];
double times[1 << 14][15];
int main() {
  int test;
  scanf("%d", &test);
  double sx, sy, ex, ey;
  while (scanf("%lf %lf %lf %lf", &sx, &sy, &ex, &ey) > 0) {
    sp = Point(sx, sy);
    ep = Point(ex, ey);
    {
      int h, m, s;
      scanf("%d:%d:%d", &h, &m, &s);
      startTime = HtoS(h, m, s);
      scanf("%d:%d:%d", &h, &m, &s);
      endTime = HtoS(h, m, s);
    }
    scanf("%d", &n);
    REP(i, n) {
      route[i].clear();
      ts[i].clear();
      int k;
      scanf("%d", &k);
      REP(j, k) {
        int x, y;
        scanf("%d %d", &x, &y);
        route[i].push_back(Point(x, y));
      }
      double pt = 0.0;
      REP(j, k) {
        ts[i].push_back(pt + abs(route[i][j] - route[i][(j + 1) % route[i].size()]) / SPEED_C);
        pt = ts[i].back();
      }
    }

    REP(i, 1 << 14) REP(j, 15) { times[i][j] = endTime + EPS * 2; }
    MEMSET(visit, false);
    priority_queue<State> que;
    que.push(State(0, startTime, sp, 14));
    pair<int, double> ans(-1, -1e+100);
    while (!que.empty()) {
      State state = que.top();
      que.pop();
      if (visit[state.use][state.last]) { continue; }
      //cout << state.use << " " << state.last << " "<< state.t << endl;
      visit[state.use][state.last] = true;
      {
        double et = state.t + abs(state.p - ep) / SPEED_N;
        if (et > endTime) { continue; }
        pair<int, double> lans(__builtin_popcount(state.use), -et);
        ans = max(ans, lans);
      }
      REP(i, n) {
        if ((state.use >> i) & 1) { continue; }
        int nuse = state.use | (1 << i);
        if (visit[nuse][i]) { continue; }
        pair<double, Point> next = calc(state, i);
        if (next.first - times[nuse][i] > EPS) { continue; }
        times[nuse][i] = next.first;
        que.push(State(nuse, next.first, next.second, i));
      }
    }
    printf("%d\n%s\n", ans.first, StoH(-ans.second).c_str());
  }
}