#include <algorithm>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

struct XorShift64 {
    uint64_t x = 88172645463325252ULL;

    uint64_t next() {
        x ^= x << 7;
        x ^= x >> 9;
        return x;
    }

    uint64_t next(uint64_t mod) {
        if (mod == 0) return 0;
        return next() % mod;
    }

    double next_double() {
        return static_cast<double>(next()) / static_cast<double>(numeric_limits<uint64_t>::max());
    }
};

struct Timer {
    chrono::steady_clock::time_point start = chrono::steady_clock::now();

    double elapsed_sec() const {
        const auto now = chrono::steady_clock::now();
        return chrono::duration<double>(now - start).count();
    }
};

struct Flight {
    int from = -1;
    int to = -1;
    int dep = -1;
    int arr = -1;

    bool operator==(const Flight& other) const {
        return from == other.from &&
               to == other.to &&
               dep == other.dep &&
               arr == other.arr;
    }
};

struct EvalResult {
    double metric = 0.0;  // approx contest score: 1e6 * share
    unsigned long long win_weight = 0;
    vector<vector<unsigned long long>> loss_pair_weight;
};

struct State {
    vector<vector<Flight>> planes;
    EvalResult eval;
};

class Solver {
public:
    void solve() {
        read_input();
        precompute();

        timer_ = Timer();
        State current = build_initial_state();
        State best = current;

        const double start_temp = 3000.0;
        const double end_temp = 20.0;

        long long iterations = 0;
        long long accepted = 0;

        while (timer_.elapsed_sec() < kTimeLimitSec - 0.01) {
            iterations++;

            State candidate;
            if (!propose_neighbor(current, candidate)) {
                continue;
            }

            candidate.eval = evaluate(candidate.planes);
            const double diff = candidate.eval.metric - current.eval.metric;

            const double progress = min(1.0, timer_.elapsed_sec() / kTimeLimitSec);
            const double temp = start_temp * pow(end_temp / start_temp, progress);

            bool accept = false;
            if (diff >= 0.0) {
                accept = true;
            } else {
                const double prob = exp(diff / max(1e-9, temp));
                accept = (rng_.next_double() < prob);
            }

            if (accept) {
                accepted++;
                current = std::move(candidate);
                if (current.eval.metric > best.eval.metric) {
                    best = current;
                }
            }
        }

        output_state(best);

        cerr << fixed << setprecision(2)
             << "[info] iters=" << iterations
             << " accepted=" << accepted
             << " final=" << current.eval.metric
             << " best=" << best.eval.metric
             << " time=" << timer_.elapsed_sec() << "s\n";
    }

private:
    static constexpr int kStartMin = 6 * 60;
    static constexpr int kEndMin = 21 * 60;
    static constexpr int kNegInf = -1'000'000'000;
    static constexpr double kTimeLimitSec = 0.9;
    static constexpr double kSingleDfsLimitSec = 0.001;  // per rebuild DFS

    int N_ = 0;
    int R_ = 0;
    int M_ = 0;
    int K_ = 0;

    vector<int> xs_;
    vector<int> ys_;
    vector<unsigned long long> ws_;

    vector<Flight> square_flights_;

    vector<vector<double>> dist_;
    vector<vector<int>> dur_;
    vector<vector<char>> eligible_pair_;

    vector<int> target_times_;  // 11:00..21:00, 30-min step
    unsigned long long total_weight_ = 0;

    vector<int> square_latest_;  // flattened [q][dst][src]

    XorShift64 rng_;
    Timer timer_;

    static string strip_bom(string s) {
        if (s.size() >= 3) {
            const unsigned char b0 = static_cast<unsigned char>(s[0]);
            const unsigned char b1 = static_cast<unsigned char>(s[1]);
            const unsigned char b2 = static_cast<unsigned char>(s[2]);
            if (b0 == 0xEF && b1 == 0xBB && b2 == 0xBF) {
                return s.substr(3);
            }
        }
        return s;
    }

    static int parse_time(const string& s) {
        // "HH:MM"
        const int hh = stoi(s.substr(0, 2));
        const int mm = stoi(s.substr(3, 2));
        return hh * 60 + mm;
    }

    static string format_time(int minutes) {
        const int hh = minutes / 60;
        const int mm = minutes % 60;
        ostringstream oss;
        oss << setfill('0') << setw(2) << hh << ":" << setw(2) << mm;
        return oss.str();
    }

    int latest_idx(int q, int dst, int src) const {
        return (q * N_ + dst) * N_ + src;
    }

    int calc_flight_duration(int i, int j) const {
        if (i == j) return 0;
        const double dx = static_cast<double>(xs_[i] - xs_[j]);
        const double dy = static_cast<double>(ys_[i] - ys_[j]);
        const double d = sqrt(dx * dx + dy * dy);
        const double raw = 60.0 * d / 800.0 + 40.0;
        const int dur = static_cast<int>(ceil((raw - 1e-12) / 5.0)) * 5;
        return dur;
    }

    void read_input() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);

        string first;
        cin >> first;
        first = strip_bom(first);
        N_ = stoi(first);
        cin >> R_;

        xs_.resize(N_);
        ys_.resize(N_);
        ws_.resize(N_);
        for (int i = 0; i < N_; i++) {
            cin >> xs_[i] >> ys_[i] >> ws_[i];
        }

        cin >> M_;
        square_flights_.reserve(M_);
        for (int i = 0; i < M_; i++) {
            int a, b;
            string s, t;
            cin >> a >> s >> b >> t;
            --a;
            --b;
            square_flights_.push_back(Flight{a, b, parse_time(s), parse_time(t)});
        }

        cin >> K_;
    }

    void precompute() {
        dist_.assign(N_, vector<double>(N_, 0.0));
        dur_.assign(N_, vector<int>(N_, 0));
        eligible_pair_.assign(N_, vector<char>(N_, 0));

        const double threshold = 0.25 * static_cast<double>(R_);

        for (int i = 0; i < N_; i++) {
            for (int j = 0; j < N_; j++) {
                const double dx = static_cast<double>(xs_[i] - xs_[j]);
                const double dy = static_cast<double>(ys_[i] - ys_[j]);
                const double d = sqrt(dx * dx + dy * dy);
                dist_[i][j] = d;
                dur_[i][j] = calc_flight_duration(i, j);
                if (d >= threshold - 1e-12) {
                    eligible_pair_[i][j] = 1;
                }
            }
        }

        target_times_.clear();
        for (int t = 11 * 60; t <= 21 * 60; t += 30) {
            target_times_.push_back(t);
        }

        total_weight_ = 0;
        for (int i = 0; i < N_; i++) {
            for (int j = 0; j < N_; j++) {
                if (!eligible_pair_[i][j]) continue;
                const unsigned long long w = ws_[i] * ws_[j];
                for (int q = 0; q < static_cast<int>(target_times_.size()); q++) {
                    (void)q;
                    total_weight_ += w;
                }
            }
        }

        square_latest_ = compute_latest_departure(square_flights_);
    }

    vector<int> compute_latest_departure(const vector<Flight>& flights) const {
        vector<Flight> sorted = flights;
        sort(sorted.begin(), sorted.end(), [](const Flight& a, const Flight& b) {
            if (a.dep != b.dep) return a.dep > b.dep;
            return a.arr > b.arr;
        });

        const int Q = static_cast<int>(target_times_.size());
        vector<int> latest(Q * N_ * N_, kNegInf);

        vector<int> dp(N_, kNegInf);
        for (int q = 0; q < Q; q++) {
            const int deadline = target_times_[q];
            for (int dst = 0; dst < N_; dst++) {
                fill(dp.begin(), dp.end(), kNegInf);
                dp[dst] = deadline;

                for (const Flight& f : sorted) {
                    if (f.arr <= dp[f.to]) {
                        dp[f.from] = max(dp[f.from], f.dep);
                    }
                }

                for (int src = 0; src < N_; src++) {
                    latest[latest_idx(q, dst, src)] = dp[src];
                }
            }
        }

        return latest;
    }

    EvalResult evaluate(const vector<vector<Flight>>& planes) const {
        vector<Flight> all;
        size_t total_legs = 0;
        for (const auto& plane : planes) total_legs += plane.size();
        all.reserve(total_legs);
        for (const auto& plane : planes) {
            for (const Flight& f : plane) {
                all.push_back(f);
            }
        }

        const vector<int> circle_latest = compute_latest_departure(all);

        EvalResult res;
        res.loss_pair_weight.assign(N_, vector<unsigned long long>(N_, 0));

        unsigned long long win = 0;
        const int Q = static_cast<int>(target_times_.size());

        for (int src = 0; src < N_; src++) {
            for (int dst = 0; dst < N_; dst++) {
                if (!eligible_pair_[src][dst]) continue;

                const unsigned long long w = ws_[src] * ws_[dst];
                for (int q = 0; q < Q; q++) {
                    const int sq = square_latest_[latest_idx(q, dst, src)];
                    const int ci = circle_latest[latest_idx(q, dst, src)];
                    if (sq < ci) {
                        win += w;
                    } else {
                        res.loss_pair_weight[src][dst] += w;
                    }
                }
            }
        }

        res.win_weight = win;
        if (total_weight_ == 0) {
            res.metric = 0.0;
        } else {
            res.metric = static_cast<double>(
                (static_cast<long double>(win) * 1'000'000.0L) /
                static_cast<long double>(total_weight_)
            );
        }
        return res;
    }

    bool validate_plane(const vector<Flight>& plane) const {
        for (int i = 0; i < static_cast<int>(plane.size()); i++) {
            const Flight& f = plane[i];
            if (f.from < 0 || f.from >= N_ || f.to < 0 || f.to >= N_ || f.from == f.to) return false;
            if (f.dep < kStartMin || f.dep > kEndMin || f.arr < kStartMin || f.arr > kEndMin) return false;
            if (f.dep % 5 != 0 || f.arr % 5 != 0) return false;
            if (f.arr - f.dep != dur_[f.from][f.to]) return false;
            if (f.arr < f.dep) return false;

            if (i > 0) {
                const Flight& prev = plane[i - 1];
                if (prev.to != f.from) return false;
                if (prev.arr > f.dep) return false;
            }
        }
        return true;
    }

    int pick_weighted_index(const vector<double>& weights) {
        double sum = 0.0;
        int fallback = -1;
        for (int i = 0; i < static_cast<int>(weights.size()); i++) {
            if (weights[i] > 0.0) {
                sum += weights[i];
                fallback = i;
            }
        }

        if (fallback < 0) {
            return static_cast<int>(rng_.next(weights.size()));
        }

        const double r = rng_.next_double() * sum;
        double acc = 0.0;
        for (int i = 0; i < static_cast<int>(weights.size()); i++) {
            if (weights[i] <= 0.0) continue;
            acc += weights[i];
            if (acc >= r) return i;
        }
        return fallback;
    }

    int choose_start_city(const EvalResult& eval) {
        vector<unsigned long long> row_loss(N_, 0);
        unsigned long long max_row = 1;
        for (int i = 0; i < N_; i++) {
            unsigned long long s = 0;
            for (int j = 0; j < N_; j++) s += eval.loss_pair_weight[i][j];
            row_loss[i] = s;
            max_row = max(max_row, s);
        }

        vector<double> weights(N_, 0.0);
        for (int i = 0; i < N_; i++) {
            const double row_ratio = static_cast<double>(row_loss[i]) / static_cast<double>(max_row);
            weights[i] = static_cast<double>(ws_[i]) * (1.0 + 3.0 * row_ratio);
        }

        return pick_weighted_index(weights);
    }

    struct MoveCandidate {
        bool stop = false;
        int to = -1;
        int dep = -1;
        int arr = -1;
        double weight = 0.0;
    };

    vector<MoveCandidate> make_move_candidates(
        int city,
        int now,
        int depth,
        bool has_target,
        int target_city,
        int target_time,
        bool force_direct,
        const EvalResult& eval,
        unsigned long long max_loss
    ) {
        vector<MoveCandidate> cands;
        const int limit = has_target ? target_time : kEndMin;
        const double threshold = 0.25 * static_cast<double>(R_);

        if (!has_target && depth >= 1) {
            // 非目標区間はある程度伸びたら終了候補も許可
            const double stop_w = 0.3 + 0.1 * min(depth, 6);
            cands.push_back(MoveCandidate{true, -1, -1, -1, stop_w});
        }

        static const int waits[] = {0, 5, 10, 15, 20, 30};

        const int to_begin = force_direct ? target_city : 0;
        const int to_end = force_direct ? target_city + 1 : N_;

        for (int to = to_begin; to < to_end; to++) {
            if (to == city) continue;

            const int d = dur_[city][to];
            if (now + d > limit) continue;

            for (int wait : waits) {
                const int dep = now + wait;
                const int arr = dep + d;
                if (arr > limit) continue;
                if (dep > kEndMin || arr > kEndMin) continue;

                if (has_target) {
                    // 三角不等式 + 固定オーバーヘッドより、直行が最短時間近似として十分強い。
                    if (arr + dur_[to][target_city] > target_time) {
                        continue;
                    }
                }

                const long double pop_score = static_cast<long double>(ws_[city]) * static_cast<long double>(ws_[to]);
                const double loss_ratio = static_cast<double>(eval.loss_pair_weight[city][to]) /
                                          static_cast<double>(max_loss);
                const double loss_score = 1.0 + 5.0 * loss_ratio;
                const double wait_score = 1.0 / (1.0 + static_cast<double>(wait) / 5.0);

                double dist_score = 1.0;
                if (dist_[city][to] >= threshold) {
                    dist_score = threshold / dist_[city][to];
                }

                double target_score = 1.0;
                if (has_target) {
                    const double d_goal = dist_[to][target_city];
                    target_score = 1.0 + threshold / (threshold + d_goal);
                    if (to == target_city) target_score *= 1.8;
                }

                double weight = static_cast<double>(pop_score) * loss_score * wait_score * dist_score * target_score;
                if (weight <= 0.0) weight = 1e-9;

                cands.push_back(MoveCandidate{false, to, dep, arr, weight});
            }
        }

        return cands;
    }

    bool build_route_segment(
        int start_city,
        int start_time,
        bool has_target,
        int target_city,
        int target_time,
        const EvalResult& eval,
        int max_depth,
        int max_nodes,
        vector<Flight>& out
    ) {
        out.clear();
        vector<Flight> path;
        const double dfs_start_elapsed = timer_.elapsed_sec();

        unsigned long long max_loss = 1;
        for (int i = 0; i < N_; i++) {
            for (int j = 0; j < N_; j++) {
                max_loss = max(max_loss, eval.loss_pair_weight[i][j]);
            }
        }

        int visited_nodes = 0;

        function<bool(int, int, int)> dfs = [&](int city, int now, int depth) -> bool {
            const double remain_global = kTimeLimitSec - timer_.elapsed_sec();
            const double dfs_elapsed = timer_.elapsed_sec() - dfs_start_elapsed;

            // 1回の再構築DFSの局所時間上限。接続が必要なら直行接続だけ試して、無理なら即失敗。
            if (dfs_elapsed >= kSingleDfsLimitSec) {
                if (has_target) {
                    if (city == target_city && now <= target_time) return true;
                    const int dep = now;
                    const int arr = dep + dur_[city][target_city];
                    if (dep <= kEndMin && arr <= target_time && arr <= kEndMin) {
                        path.push_back(Flight{city, target_city, dep, arr});
                        return true;
                    }
                    return false;
                }
                return true;
            }

            if (remain_global < 0.015) {
                if (has_target) {
                    if (city == target_city && now <= target_time) return true;
                    const int dep = now;
                    const int arr = dep + dur_[city][target_city];
                    if (dep <= kEndMin && arr <= target_time && arr <= kEndMin) {
                        path.push_back(Flight{city, target_city, dep, arr});
                        return true;
                    }
                    return false;
                }
                return true;
            }

            if (has_target) {
                if (city == target_city && now <= target_time) return true;
                if (now > target_time) return false;
                if (now + dur_[city][target_city] > target_time) return false;
            } else {
                if (now >= kEndMin - 5) return true;
                if (depth >= max_depth) return true;
            }

            if (visited_nodes++ >= max_nodes) {
                if (has_target) {
                    return city == target_city && now <= target_time;
                }
                return true;
            }

            bool force_direct = false;
            if (has_target) {
                const int rem = target_time - now;
                if (rem <= dur_[city][target_city] + 10 || remain_global < 0.04) {
                    force_direct = true;
                }
            } else {
                if (remain_global < 0.03) {
                    return true;
                }
            }

            vector<MoveCandidate> cands = make_move_candidates(
                city,
                now,
                depth,
                has_target,
                target_city,
                target_time,
                force_direct,
                eval,
                max_loss
            );

            if (cands.empty()) {
                return !has_target;
            }

            while (!cands.empty()) {
                vector<double> weights;
                weights.reserve(cands.size());
                for (const auto& c : cands) weights.push_back(c.weight);
                const int pick = pick_weighted_index(weights);

                const MoveCandidate cand = cands[pick];
                cands[pick] = cands.back();
                cands.pop_back();

                if (cand.stop) {
                    if (!has_target) return true;
                    continue;
                }

                path.push_back(Flight{city, cand.to, cand.dep, cand.arr});
                if (dfs(cand.to, cand.arr, depth + 1)) {
                    return true;
                }
                path.pop_back();
            }

            return false;
        };

        const bool ok = dfs(start_city, start_time, 0);
        if (ok) {
            out = std::move(path);
        }
        return ok;
    }

    State build_initial_state() {
        State state;
        state.planes.assign(K_, {});

        state.eval = evaluate(state.planes);  // empty schedule baseline

        for (int p = 0; p < K_; p++) {
            vector<Flight> route;
            bool ok = false;

            for (int trial = 0; trial < 8; trial++) {
                const int start_city = choose_start_city(state.eval);
                const int max_depth = 8 + static_cast<int>(rng_.next(8));
                ok = build_route_segment(
                    start_city,
                    kStartMin,
                    false,
                    -1,
                    -1,
                    state.eval,
                    max_depth,
                    1200,
                    route
                );
                if (ok && !route.empty()) break;
            }

            if (!ok || route.empty()) {
                // Fallback: 単発1便
                const int a = choose_start_city(state.eval);
                int b = -1;
                for (int i = 0; i < N_; i++) {
                    if (i == a) continue;
                    if (kStartMin + dur_[a][i] > kEndMin) continue;
                    if (b < 0 || ws_[i] > ws_[b]) b = i;
                }
                if (b < 0) {
                    b = (a + 1) % N_;
                }
                route.push_back(Flight{a, b, kStartMin, kStartMin + dur_[a][b]});
            }

            if (!validate_plane(route)) {
                // 万一の保険
                const int a = 0;
                const int b = 1 % N_;
                route.clear();
                route.push_back(Flight{a, b, kStartMin, kStartMin + dur_[a][b]});
            }

            state.planes[p] = std::move(route);
            state.eval = evaluate(state.planes);
        }

        return state;
    }

    bool propose_neighbor(const State& current, State& out) {
        out = current;

        for (int attempt = 0; attempt < 10; attempt++) {
            const int p = static_cast<int>(rng_.next(K_));
            const vector<Flight>& base = current.planes[p];
            const int m = static_cast<int>(base.size());

            int l = 0;
            int r = m;
            bool keep_suffix = false;

            const int mode_roll = static_cast<int>(rng_.next(100));
            if (m == 0 || mode_roll < 25) {
                // 全破壊
                l = 0;
                r = m;
                keep_suffix = false;
            } else if (mode_roll < 60) {
                // 後半を再構築
                l = static_cast<int>(rng_.next(m + 1));
                r = m;
                keep_suffix = false;
            } else {
                // 中区間を再構築して後続へ接続
                l = static_cast<int>(rng_.next(m + 1));
                if (l == m) l = m - 1;
                int len = 1 + static_cast<int>(rng_.next(max(1, m - l)));
                r = min(m, l + len);
                keep_suffix = (r < m) && (rng_.next(100) < 75);
            }

            vector<Flight> prefix(base.begin(), base.begin() + l);
            vector<Flight> suffix;
            if (keep_suffix) {
                suffix.assign(base.begin() + r, base.end());
            }

            int start_city = -1;
            int start_time = -1;

            if (!prefix.empty()) {
                start_city = prefix.back().to;
                start_time = prefix.back().arr;
            } else {
                const bool reuse_original_start = (!base.empty() && rng_.next(100) < 40);
                start_city = reuse_original_start ? base.front().from : choose_start_city(current.eval);
                start_time = kStartMin;
            }

            bool has_target = false;
            int target_city = -1;
            int target_time = -1;
            if (!suffix.empty()) {
                has_target = true;
                target_city = suffix.front().from;
                target_time = suffix.front().dep;
            }

            vector<Flight> middle;
            const int max_depth = has_target ? 12 : (8 + static_cast<int>(rng_.next(8)));
            const int max_nodes = has_target ? 600 : 500;

            const bool ok = build_route_segment(
                start_city,
                start_time,
                has_target,
                target_city,
                target_time,
                current.eval,
                max_depth,
                max_nodes,
                middle
            );
            if (!ok) continue;

            vector<Flight> merged;
            merged.reserve(prefix.size() + middle.size() + suffix.size());
            for (const auto& f : prefix) merged.push_back(f);
            for (const auto& f : middle) merged.push_back(f);
            for (const auto& f : suffix) merged.push_back(f);

            if (merged.empty()) continue;
            if (!validate_plane(merged)) continue;
            if (merged == base) continue;

            out.planes[p] = std::move(merged);
            return true;
        }

        return false;
    }

    void output_state(const State& state) const {
        for (int p = 0; p < K_; p++) {
            const auto& route = state.planes[p];
            cout << route.size() << '\n';
            for (const Flight& f : route) {
                cout << (f.from + 1) << ' '
                     << format_time(f.dep) << ' '
                     << (f.to + 1) << ' '
                     << format_time(f.arr) << '\n';
            }
        }
    }
};

int main() {
    Solver solver;
    solver.solve();
    return 0;
}