#include <bits/stdc++.h>
using namespace std;
# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")



struct City { double x, y; long long w; };
struct Flight { int a; int dep; int b; int arr; }; // dep/arr in minutes from midnight
struct InFlight { int a; int dep; int arr; }; // used in flights-by-arrival lists

inline string fmt_time(int t){
    int hh = t / 60;
    int mm = t % 60;
    char buf[6];
    sprintf(buf, "%02d:%02d", hh, mm);
    return string(buf);
}
inline int parse_time(const string &s){
    int hh = (s[0]-'0')*10 + (s[1]-'0');
    int mm = (s[3]-'0')*10 + (s[4]-'0');
    return hh*60 + mm;
}

const int START = 6*60;   // 360
const int END   = 21*60;  // 1260
const int INF_NEG = -1000000000;

using Schedule = vector<vector<Flight>>;

// Build list of target arrival times: 11:00..21:00 step 30
static inline vector<int> build_target_times() {
    vector<int> T;
    for (int t = 11*60; t <= 21*60; t += 30) T.push_back(t);
    return T;
}

// Precompute travel time matrix (5-minute-ceiled formula)
static vector<vector<int>> build_travel_matrix(const vector<City> &cities) {
    int N = (int)cities.size();
    vector<vector<int>> travel(N, vector<int>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (i == j) { travel[i][j] = 0; continue; }
            double dx = cities[i].x - cities[j].x;
            double dy = cities[i].y - cities[j].y;
            double d = hypot(dx, dy);
            double raw = 60.0 * d / 800.0 + 40.0;
            int tt = (int)ceil(raw / 5.0) * 5;
            travel[i][j] = tt;
        }
    }
    return travel;
}

// Greedy extend from (cur, time) for a single plane using travel matrix
static vector<Flight> greedy_extend_from(const vector<City> &cities, const vector<vector<int>> &travel, int cur, int time) {
    vector<Flight> res;
    int N = (int)cities.size();
    while (true) {
        int best = -1, best_tt = INT_MAX;
        for (int j = 0; j < N; ++j) {
            if (j == cur) continue;
            int tt = travel[cur][j];
            if (time + tt > END) continue;
            if (tt < best_tt || (tt == best_tt && j < best)) {
                best_tt = tt; best = j;
            }
        }
        if (best == -1) break;
        int dep = time;
        int arr = dep + best_tt;
        res.push_back({cur, dep, best, arr});
        cur = best;
        time = arr;
    }
    return res;
}

// Build initial schedule as hub <-> top25 (or up to available) round-robin
static Schedule build_initial(const vector<City> &cities, int K, const vector<vector<int>> &travel) {
    int N = (int)cities.size();
    int hub = 0;
    for (int i = 1; i < N; ++i) if (cities[i].w > cities[hub].w) hub = i;
    vector<pair<long long,int>> vec;
    vec.reserve(N);
    for (int i = 0; i < N; ++i) if (i != hub) vec.emplace_back(cities[i].w, i);
    sort(vec.begin(), vec.end(), [](const auto &A, const auto &B){
        if (A.first != B.first) return A.first > B.first;
        return A.second < B.second;
    });
    int needSpokes = 25;
    int topCount = min((int)vec.size(), needSpokes);
    vector<int> targets; targets.reserve(topCount);
    for (int i = 0; i < topCount; ++i) targets.push_back(vec[i].second);

    Schedule schedules(K);
    if (topCount == 0) return schedules;

    for (int k = 0; k < K; ++k) {
        int target = targets[k % topCount];
        int cur = hub;
        int time = START;
        auto &sch = schedules[k];
        while (true) {
            int next = (cur == hub) ? target : hub;
            int tt = travel[cur][next];
            int dep = time;
            int arr = dep + tt;
            if (arr > END) break;
            sch.push_back({cur, dep, next, arr});
            cur = next;
            time = arr;
        }
    }
    return schedules;
}

// Build flights-by-arrival (fba) from schedules
static vector<vector<InFlight>> build_fba_from_schedules(const Schedule &schedules, int N) {
    vector<vector<InFlight>> fba(N);
    for (const auto &sch : schedules) {
        for (const auto &f : sch) {
            fba[f.b].push_back({f.a, f.dep, f.arr});
        }
    }
    return fba;
}
// Build fba from generic flights vector
static vector<vector<InFlight>> build_fba_from_flights(const vector<Flight> &flights, int N) {
    vector<vector<InFlight>> fba(N);
    for (const auto &f : flights) fba[f.b].push_back({f.a, f.dep, f.arr});
    return fba;
}

// Compute latest deps for a single (dest, target T) using current fba (reverse BFS)
static vector<int> compute_latest_dep_one(int N, int dest, int T, const vector<vector<InFlight>> &fba) {
    vector<int> L(N, INF_NEG);
    deque<int> dq;
    L[dest] = T;
    dq.push_back(dest);
    while (!dq.empty()) {
        int v = dq.front(); dq.pop_front();
        const auto &vec = fba[v];
        for (int i = 0; i < (int)vec.size(); ++i) {
            const InFlight &inf = vec[i];
            if (inf.arr <= L[v]) {
                int u = inf.a;
                if (L[u] < inf.dep) {
                    L[u] = inf.dep;
                    dq.push_back(u);
                }
            }
        }
    }
    return L;
}

// Compute latest deps for all (dest,ti) — used initially for s_ci and s_sq
static vector<vector<vector<int>>> compute_latest_deps_all_from_fba(int N, const vector<vector<InFlight>> &fba, const vector<int> &Tlist) {
    int D = N;
    int TT = (int)Tlist.size();
    vector<vector<vector<int>>> res(D, vector<vector<int>>(TT, vector<int>(N, INF_NEG)));
    for (int dest = 0; dest < D; ++dest) {
        for (int ti = 0; ti < TT; ++ti) {
            res[dest][ti] = compute_latest_dep_one(N, dest, Tlist[ti], fba);
        }
    }
    return res;
}

// Compute share-rate S given s_sq and s_ci
static long double compute_share_rate(const vector<vector<vector<int>>> &s_sq_all, const vector<vector<vector<int>>> &s_ci_all,
                               const vector<pair<int,int>> &ODlist, const vector<int> &Tlist,
                               const vector<City> &cities) {
    long double v_ci = 0.0L, v_sq = 0.0L;
    int TT = (int)Tlist.size();
    for (const auto &od : ODlist) {
        int u = od.first;
        int v = od.second;
        long long weight = cities[u].w * cities[v].w;
        for (int ti = 0; ti < TT; ++ti) {
            int s_sq = s_sq_all[v][ti][u];
            int s_ci = s_ci_all[v][ti][u];
            if (s_sq < s_ci) v_ci += (long double)weight;
            else v_sq += (long double)weight;
        }
    }
    if (v_ci + v_sq <= 0.0L) return 0.0L;
    return v_ci / (v_ci + v_sq);
}

// Apply neighbor change to schedules: modify schedules in-place for one plane.
// Returns tuple: (changed?, plane_index, oldFlights, newFlights)
static tuple<bool,int,vector<Flight>,vector<Flight>> apply_random_neighbor_return_changes(Schedule &schedules, const vector<City> &cities, const vector<vector<int>> &travel, mt19937_64 &rng) {
    int K = schedules.size();
    uniform_int_distribution<int> pick_plane(0, max(0, K-1));
    int k = pick_plane(rng);
    vector<Flight> &sch = schedules[k];
    int n = (int)sch.size();
    uniform_int_distribution<int> opdist(0,1);
    int op = opdist(rng);

    vector<Flight> oldFlights = sch; // backup of old flights for this plane
    if (n == 0) {
        int hub = 0;
        for (int i = 1; i < (int)cities.size(); ++i) if (cities[i].w > cities[hub].w) hub = i;
        vector<Flight> newsch = greedy_extend_from(cities, travel, hub, START);
        if (!newsch.empty()) {
            sch = std::move(newsch);
            return {true, k, oldFlights, sch};
        } else return {false, -1, oldFlights, vector<Flight>()};
    }

    if (op == 0) {
        // change destination of random flight p (minimal change)
        uniform_int_distribution<int> pick_pos(0, n-1);
        int p = pick_pos(rng);
        int cur; int time;
        if (p == 0) { cur = sch[0].a; time = sch[0].dep; }
        else { cur = sch[p-1].b; time = sch[p-1].arr; }
        vector<int> cand; cand.reserve(cities.size());
        int N = (int)cities.size();
        for (int j = 0; j < N; ++j) {
            if (j == cur) continue;
            int tt = travel[cur][j];
            if (time + tt <= END) cand.push_back(j);
        }
        if (cand.empty()) return {false, -1, oldFlights, vector<Flight>()};
        int cur_b = sch[p].b;
        vector<int> cand2; cand2.reserve(cand.size());
        for (int v : cand) if (v != cur_b) cand2.push_back(v);
        if (cand2.empty()) return {false, -1, oldFlights, vector<Flight>()};
        uniform_int_distribution<int> pick_cand(0, (int)cand2.size()-1);
        int newdest = cand2[pick_cand(rng)];
        sch.erase(sch.begin() + p, sch.end());
        int tt = travel[cur][newdest];
        int dep = time;
        int arr = dep + tt;
        sch.push_back({cur, dep, newdest, arr});
        int cur_city = newdest;
        int cur_time = arr;
        // try to preserve suffix where possible
        for (int j = p+1; j < (int)oldFlights.size(); ++j) {
            const Flight &orig = oldFlights[j];
            int required_tt = travel[orig.a][orig.b];
            if (orig.a == cur_city && orig.dep >= cur_time && orig.arr - orig.dep == required_tt) {
                sch.push_back(orig);
                cur_city = orig.b;
                cur_time = orig.arr;
            } else {
                vector<Flight> tail = greedy_extend_from(cities, travel, cur_city, cur_time);
                sch.insert(sch.end(), tail.begin(), tail.end());
                break;
            }
        }
        return {true, k, oldFlights, sch};
    } else {
        // shift departure of random flight p by +/-5
        uniform_int_distribution<int> pick_pos(0, n-1);
        int p = pick_pos(rng);
        int prev_arr = (p==0) ? START : sch[p-1].arr;
        int dep = sch[p].dep;
        int tt = sch[p].arr - sch[p].dep;
        vector<int> cand_dep;
        if (dep - 5 >= prev_arr) cand_dep.push_back(dep - 5);
        if (dep + 5 + tt <= END) cand_dep.push_back(dep + 5);
        if (cand_dep.empty()) return {false, -1, oldFlights, vector<Flight>()};
        uniform_int_distribution<int> pickd(0, (int)cand_dep.size()-1);
        int new_dep = cand_dep[pickd(rng)];
        int new_arr = new_dep + tt;
        int a_orig = sch[p].a;
        int b_orig = sch[p].b;
        sch.erase(sch.begin() + p, sch.end());
        sch.push_back({a_orig, new_dep, b_orig, new_arr});
        int cur_city = b_orig;
        int cur_time = new_arr;
        for (int j = p+1; j < (int)oldFlights.size(); ++j) {
            const Flight &orig = oldFlights[j];
            int required_tt = travel[orig.a][orig.b];
            if (orig.a == cur_city && orig.dep >= cur_time && orig.arr - orig.dep == required_tt) {
                sch.push_back(orig);
                cur_city = orig.b;
                cur_time = orig.arr;
            } else {
                vector<Flight> tail = greedy_extend_from(cities, travel, cur_city, cur_time);
                sch.insert(sch.end(), tail.begin(), tail.end());
                break;
            }
        }
        return {true, k, oldFlights, sch};
    }
}

// helper: remove a single inflight entry matching (a,dep,arr) from fba[b]; returns true if removed
static bool remove_inflight_from_fba(vector<vector<InFlight>> &fba, const InFlight &inf, int b) {
    auto &vec = fba[b];
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        if (it->a == inf.a && it->dep == inf.dep && it->arr == inf.arr) {
            *it = vec.back();
            vec.pop_back();
            return true;
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, R;
    if (!(cin >> N >> R)) return 0;
    vector<City> cities(N);
    for (int i = 0; i < N; ++i) {
        long long xi, yi, wi;
        cin >> xi >> yi >> wi;
        cities[i].x = (double)xi;
        cities[i].y = (double)yi;
        cities[i].w = wi;
    }
    int M; cin >> M;
    vector<Flight> square_flights; square_flights.reserve(M);
    for (int i = 0; i < M; ++i) {
        int a, b; string s_str, t_str;
        cin >> a >> s_str >> b >> t_str;
        int smin = parse_time(s_str);
        int tmin = parse_time(t_str);
        square_flights.push_back({a-1, smin, b-1, tmin});
    }
    int K; cin >> K;

    // prepare
    vector<int> Tlist = build_target_times();
    int TT = (int)Tlist.size();

    vector<vector<int>> travel = build_travel_matrix(cities);

    // OD list (distance >= 0.25R)
    vector<pair<int,int>> ODlist; ODlist.reserve(N*N/2);
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) if (i!=j) {
        double d = hypot(cities[i].x - cities[j].x, cities[i].y - cities[j].y);
        if (d + 1e-9 >= 0.25 * (double)R) ODlist.emplace_back(i,j);
    }

    // build s_sq_all from square_flights: use fba of square flights
    vector<vector<InFlight>> fba_sq = build_fba_from_flights(square_flights, max(1,N));
    vector<vector<vector<int>>> s_sq_all = compute_latest_deps_all_from_fba(N, fba_sq, Tlist);

    // initial schedules
    Schedule schedules = build_initial(cities, K, travel);

    // build fba_current from schedules
    vector<vector<InFlight>> fba_cur = build_fba_from_schedules(schedules, max(1,N));

    // compute initial s_ci_all
    vector<vector<vector<int>>> s_ci_all = compute_latest_deps_all_from_fba(N, fba_cur, Tlist);

    long double best_score = compute_share_rate(s_sq_all, s_ci_all, ODlist, Tlist, cities);
    Schedule best_sched = schedules;

    // random
    mt19937_64 rng((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());

    // time limit
    const double TIME_LIMIT = 0.95; // seconds
    const long double T0 = 1.0L, Tmin = 1e-3L;

    auto tstart = chrono::high_resolution_clock::now();
    long long iter = 0;

    while (true) {
        auto now = chrono::high_resolution_clock::now();
        double elapsed = chrono::duration_cast<chrono::duration<double>>(now - tstart).count();
        if (elapsed > TIME_LIMIT) break;
        long double frac = elapsed / TIME_LIMIT;
        if (frac > 1.0) frac = 1.0;
        long double T = T0 * (1.0L - frac) + Tmin * frac;

        ++iter;

        // propose neighbor, get changed plane and old/new flights
        auto tup = apply_random_neighbor_return_changes(schedules, cities, travel, rng);
        bool changed = get<0>(tup);
        int plane = get<1>(tup);
        vector<Flight> oldFlights = get<2>(tup);
        vector<Flight> newFlights = get<3>(tup);
        if (!changed) continue;

        // BEFORE updating fba_cur, decide affected (dest,ti) candidates using old s_ci_all
        int changed_count = (int)oldFlights.size() + (int)newFlights.size();
        vector<vector<char>> affected(N, vector<char>(TT, 0));
        // use old s_ci_all
        for (const Flight &f : oldFlights) {
            int b = f.b;
            int arr_old = f.arr;
            for (int dest = 0; dest < N; ++dest) {
                for (int ti = 0; ti < TT; ++ti) {
                    if (!affected[dest][ti] && s_ci_all[dest][ti][b] >= arr_old) affected[dest][ti] = 1;
                }
            }
        }
        for (const Flight &f : newFlights) {
            int b = f.b;
            int arr_new = f.arr;
            for (int dest = 0; dest < N; ++dest) {
                for (int ti = 0; ti < TT; ++ti) {
                    if (!affected[dest][ti] && s_ci_all[dest][ti][b] >= arr_new) affected[dest][ti] = 1;
                }
            }
        }

        // Now update fba_cur: remove oldFlights, add newFlights
        bool remove_ok = true;
        for (const Flight &f : oldFlights) {
            InFlight inf{f.a, f.dep, f.arr};
            bool r = remove_inflight_from_fba(fba_cur, inf, f.b);
            if (!r) {
                // shouldn't happen; but we'll continue
                remove_ok = false;
            }
        }
        for (const Flight &f : newFlights) {
            fba_cur[f.b].push_back({f.a, f.dep, f.arr});
        }

        // For all affected (dest,ti), recompute L_new and update s_ci_all[dest][ti] if changed
        for (int dest = 0; dest < N; ++dest) {
            for (int ti = 0; ti < TT; ++ti) {
                if (!affected[dest][ti]) continue;
                vector<int> Lnew = compute_latest_dep_one(N, dest, Tlist[ti], fba_cur);
                // compare Lnew with s_ci_all[dest][ti]
                bool diff = false;
                for (int c = 0; c < N; ++c) {
                    if (Lnew[c] != s_ci_all[dest][ti][c]) { diff = true; break; }
                }
                if (diff) {
                    s_ci_all[dest][ti].swap(Lnew); // update
                }
            }
        }

        // Evaluate new score
        long double new_score = compute_share_rate(s_sq_all, s_ci_all, ODlist, Tlist, cities);

        bool accept = false;
        if (new_score > best_score) {
            accept = true;
            best_score = new_score;
            best_sched = schedules;
        } else {
            long double diff = new_score - best_score; // <= 0
            long double prob = expl(diff / max((long double)1e-18, T));
            uniform_real_distribution<long double> ud(0.0L, 1.0L);
            if (ud(rng) < prob) accept = true;
            else accept = false;
        }

        if (!accept) {
            // revert schedules and fba_cur and s_ci_all (we need to undo fba changes and s_ci changes)
            // revert schedules
            schedules[plane] = oldFlights;
            // revert fba_cur: remove newFlights additions, re-add oldFlights
            for (const Flight &f : newFlights) {
                // remove one matching inflight from fba_cur[f.b]
                InFlight inf{f.a, f.dep, f.arr};
                bool r = remove_inflight_from_fba(fba_cur, inf, f.b);
                (void)r;
            }
            for (const Flight &f : oldFlights) {
                fba_cur[f.b].push_back({f.a, f.dep, f.arr});
            }
            // recompute s_ci_all for affected (dest,ti) back to previous values:
            // Easiest correct way: recompute L_old for affected (dest,ti) using fba constructed from reverting; this restores s_ci_all
            for (int dest = 0; dest < N; ++dest) {
                for (int ti = 0; ti < TT; ++ti) {
                    if (!affected[dest][ti]) continue;
                    vector<int> Lold = compute_latest_dep_one(N, dest, Tlist[ti], fba_cur);
                    s_ci_all[dest][ti].swap(Lold);
                }
            }
        }
        // otherwise accept: s_ci_all is already updated and fba_cur already reflects new flights
    }

    // Output best solution in required format
    for (int k = 0; k < K; ++k) {
        if (k < (int)best_sched.size()) {
            const auto &sch = best_sched[k];
            cout << sch.size() << '\n';
            for (const auto &f : sch) {
                cout << (f.a + 1) << " " << fmt_time(f.dep) << " " << (f.b + 1) << " " << fmt_time(f.arr) << '\n';
            }
        } else {
            cout << 0 << '\n';
        }
    }

    // diagnostics
    auto tend = chrono::high_resolution_clock::now();
    double total_elapsed = chrono::duration_cast<chrono::duration<double>>(tend - tstart).count();
    cerr.setf(std::ios::fixed); cerr<<setprecision(6);
    cerr << "elapsed_seconds: " << total_elapsed << " iterations: " << iter << '\n';

    return 0;
}