#include <algorithm>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <string>
#include <tuple>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = long long;

namespace {
constexpr int DAY_START = 6 * 60;
constexpr int DAY_END = 21 * 60;
constexpr int SLOT_STEP = 5;
constexpr int DEADLINE_COUNT = 21;
constexpr int NEG = -1000000000;

constexpr double TOTAL_TIME_LIMIT_SEC = 0.78;
constexpr double SA_MAX_TIME_SEC = 0.66;
constexpr double SA_MARGIN_SEC = 0.05;
constexpr int BEAM_WIDTH = 16;
constexpr int BEAM_DEPTH = 3;
constexpr int BEAM_SCAN_FIRST = 140;
constexpr int BEAM_SCAN_NEXT = 90;
constexpr int WAIT_FIRST_MAX = 240;
constexpr int WAIT_NEXT_MAX = 90;
constexpr int ZERO_WAIT_ALLOW = 60;
constexpr int REBUILD_MAX_LEGS = 14;
constexpr int INIT_SCAN_MAX = 500;
constexpr int ACTIVE_SCAN_MAX = 190;
constexpr int ACTIVE_WAIT_HORIZON = 120;
constexpr int FUTURE_HORIZON = 120;
constexpr int FUTURE_SCAN_MAX = 70;
constexpr int NEAR_PER_CITY = 4;
constexpr int NEAR_TIME_STEP = 10;
constexpr double STEAL_BEAM_GAIN_WEIGHT = 20.0;
constexpr ll MOVE_OVERRIDE_NUM = 10;   // best_move_future * NUM >= best_gain * DEN
constexpr ll MOVE_OVERRIDE_DEN = 80;   // 8倍以上の将来奪取見込みがある時のみ移動優先
constexpr double STEAL_FAST_WEIGHT = 0.08;
constexpr double EDGE_FAST_WEIGHT = 55.0;
constexpr double WAIT_FAST_WEIGHT = 2.2;
constexpr double FILL_FAST_WEIGHT = 1.2;
constexpr double FAST_SKIP_COEF = 1.4;
constexpr int STAGNATE_LIMIT = 40;
constexpr double WAIT_AUG_WEIGHT = 600.0;

struct Flight {
    int a;  // 0-index
    int b;  // 0-index
    int s;  // minutes
    int t;  // minutes
};

struct Candidate {
    int a;
    int b;
    int s;
    int t;
    int edge;
    uint32_t mask;  // 締切ごとの勝利ビット
    ll pair_w;      // 対象ODの人口積
    ll base_gain;   // スクエア単体に対する直行便利得
};

struct PlaneState {
    bool active = false;
    int city = -1;
    int tm = DAY_START;
};

struct FillInfo {
    int rt_time = 1e9;   // 往復1セットに必要な最短時間
    int rt_edge = 0;     // 往復1セットで奪取密度が高いもの
    int one_time = 1e9;  // 片道の最短時間
    int one_edge = 0;    // 片道で奪取密度が高いもの
};

struct XorShift64 {
    uint64_t x;
    explicit XorShift64(uint64_t seed = 88172645463325252ULL) : x(seed ? seed : 88172645463325252ULL) {}
    uint64_t next_u64() {
        x ^= x << 7;
        x ^= x >> 9;
        return x;
    }
    int next_int(int l, int r) {
        return l + (int)(next_u64() % (uint64_t)(r - l + 1));
    }
    double next_double() {
        return (double)((next_u64() >> 11) * (1.0 / 9007199254740992.0));
    }
};

int calc_duration_min(long double dist) {
    long double raw = 60.0L * dist / 800.0L + 40.0L;
    int q = (int)ceill(raw / 5.0L - 1e-12L);
    return q * 5;
}

int parse_time(const string& tok) {
    size_t p = tok.find(':');
    if (p != string::npos) {
        int hh = stoi(tok.substr(0, p));
        int mm = stoi(tok.substr(p + 1));
        return hh * 60 + mm;
    }
    int x = stoi(tok);
    // HHMM 形式にも対応
    if (x >= 600 && x <= 2359 && x % 100 < 60) {
        return (x / 100) * 60 + (x % 100);
    }
    // 分として扱う
    return x;
}

string to_hhmm(int m) {
    char buf[8];
    snprintf(buf, sizeof(buf), "%02d:%02d", m / 60, m % 60);
    return string(buf);
}

vector<int> build_deadlines() {
    vector<int> d(DEADLINE_COUNT);
    for (int k = 0; k < DEADLINE_COUNT; ++k) d[k] = 11 * 60 + 30 * k;
    return d;
}

// ある都市で gap 分の待機があるとき、探索中にどれだけ埋められそうかを近似評価する
double estimate_fill_gain(const FillInfo& fi, int gap, bool need_return) {
    if (gap <= 0) return 0.0;
    if (need_return) {
        if (fi.rt_time > gap || fi.rt_time >= (int)1e9) return 0.0;
        int cnt = gap / fi.rt_time;
        return (double)cnt * (double)fi.rt_edge;
    }
    if (fi.one_time > gap || fi.one_time >= (int)1e9) return 0.0;
    int cnt = gap / fi.one_time;
    return (double)cnt * (double)fi.one_edge;
}

// 1機体の高速近似スコア（差分評価用）
double calc_plane_fast_score(const vector<int>& seq, const vector<Candidate>& cand,
                             const vector<FillInfo>& fill_info) {
    if (seq.empty()) return 0.0;

    double sc = 0.0;

    // 初便までの待機（開始都市は初便の出発都市）
    const auto& first = cand[seq[0]];
    int gap0 = first.s - DAY_START;
    if (gap0 > 0) {
        sc -= WAIT_FAST_WEIGHT * (double)gap0;
        sc += FILL_FAST_WEIGHT * estimate_fill_gain(fill_info[first.a], gap0, true);
    }

    for (int i = 0; i < (int)seq.size(); ++i) {
        const auto& c = cand[seq[i]];
        sc += STEAL_FAST_WEIGHT * (double)c.base_gain;
        sc += EDGE_FAST_WEIGHT * (double)c.edge;

        if (i + 1 < (int)seq.size()) {
            const auto& nx = cand[seq[i + 1]];
            int g = nx.s - c.t;
            if (g > 0) {
                sc -= WAIT_FAST_WEIGHT * (double)g;
                sc += FILL_FAST_WEIGHT * estimate_fill_gain(fill_info[c.b], g, true);
            }
        }
    }

    // 末尾待機
    const auto& last = cand[seq.back()];
    int tail = DAY_END - last.t;
    if (tail > 0) {
        sc -= WAIT_FAST_WEIGHT * (double)tail;
        sc += FILL_FAST_WEIGHT * estimate_fill_gain(fill_info[last.b], tail, false);
    }

    return sc;
}

// 1機体の待機埋め近似スコア（探索目的に組み込む）
double calc_plane_wait_fill_score(const vector<int>& seq, const vector<Candidate>& cand,
                                  const vector<FillInfo>& fill_info) {
    if (seq.empty()) return 0.0;

    double sc = 0.0;
    const auto& first = cand[seq[0]];
    int gap0 = first.s - DAY_START;
    if (gap0 > 0) {
        sc -= WAIT_FAST_WEIGHT * (double)gap0;
        sc += 2.0 * FILL_FAST_WEIGHT * estimate_fill_gain(fill_info[first.a], gap0, true);
    }

    for (int i = 0; i + 1 < (int)seq.size(); ++i) {
        const auto& c = cand[seq[i]];
        const auto& nx = cand[seq[i + 1]];
        int g = nx.s - c.t;
        if (g > 0) {
            sc -= WAIT_FAST_WEIGHT * (double)g;
            sc += 2.0 * FILL_FAST_WEIGHT * estimate_fill_gain(fill_info[c.b], g, true);
        }
    }

    const auto& last = cand[seq.back()];
    int tail = DAY_END - last.t;
    if (tail > 0) {
        sc -= WAIT_FAST_WEIGHT * (double)tail;
        sc += 2.0 * FILL_FAST_WEIGHT * estimate_fill_gain(fill_info[last.b], tail, false);
    }
    return sc;
}

inline uint64_t flight_key(int a, int b, int s) {
    return ((uint64_t)s << 12) | ((uint64_t)a << 6) | (uint64_t)b;
}

// 時間拡張DPで、開始時刻から終了時刻までの便列を最大時間だけ埋める
vector<Flight> build_best_fill_path(int start_city, int start_tm, int end_tm,
                                    const vector<vector<int>>& dur,
                                    const vector<vector<int>>& sq_edge_count,
                                    const unordered_set<uint64_t>& used_keys,
                                    bool need_return) {
    int rem = end_tm - start_tm;
    if (rem <= 0) return {};
    int lim = rem / SLOT_STEP;
    if (lim <= 0) return {};

    int n = (int)dur.size();
    const int NEG_INF = -1000000000;

    vector<vector<int>> best(lim + 1, vector<int>(n, NEG_INF));
    vector<vector<int>> prev_t(lim + 1, vector<int>(n, -1));
    vector<vector<int>> prev_city(lim + 1, vector<int>(n, -1));
    best[0][start_city] = 0;

    for (int t = 0; t <= lim; ++t) {
        int abs_tm = start_tm + t * SLOT_STEP;
        for (int u = 0; u < n; ++u) {
            if (best[t][u] == NEG_INF) continue;
            for (int v = 0; v < n; ++v) {
                if (v == u) continue;
                int d = dur[u][v];
                int dt = d / SLOT_STEP;
                int nt = t + dt;
                if (nt > lim) continue;
                if (used_keys.find(flight_key(u, v, abs_tm)) != used_keys.end()) continue;

                int ne = best[t][u] + sq_edge_count[u][v];
                if (ne > best[nt][v]) {
                    best[nt][v] = ne;
                    prev_t[nt][v] = t;
                    prev_city[nt][v] = u;
                }
            }
        }
    }

    int goal_t = 0;
    int goal_city = -1;
    if (need_return) {
        for (int t = lim; t >= 1; --t) {
            if (best[t][start_city] != NEG_INF) {
                goal_t = t;
                goal_city = start_city;
                break;
            }
        }
    } else {
        for (int t = lim; t >= 1; --t) {
            int best_city = -1;
            int best_edge = NEG_INF;
            for (int v = 0; v < n; ++v) {
                if (best[t][v] > best_edge) {
                    best_edge = best[t][v];
                    best_city = v;
                }
            }
            if (best_edge != NEG_INF) {
                goal_t = t;
                goal_city = best_city;
                break;
            }
        }
    }
    if (goal_t == 0 || goal_city == -1) return {};

    vector<Flight> rev;
    int cur_t = goal_t;
    int cur_city = goal_city;
    while (cur_t > 0) {
        int pt = prev_t[cur_t][cur_city];
        int pc = prev_city[cur_t][cur_city];
        if (pt < 0 || pc < 0) {
            rev.clear();
            break;
        }
        rev.push_back(Flight{pc, cur_city, start_tm + pt * SLOT_STEP, start_tm + cur_t * SLOT_STEP});
        cur_t = pt;
        cur_city = pc;
    }
    if (rev.empty() || cur_t != 0 || cur_city != start_city) return {};
    reverse(rev.begin(), rev.end());
    return rev;
}

// 区間[start_tm, end_tm]を、開始都市に戻る制約付きで最大限埋める
void fill_gap_roundtrips(vector<Flight>& out, int base, int start_tm, int end_tm,
                         const vector<vector<int>>& dur,
                         const vector<vector<int>>& sq_edge_count,
                         unordered_set<uint64_t>& used_keys) {
    auto path =
        build_best_fill_path(base, start_tm, end_tm, dur, sq_edge_count, used_keys, true);
    for (const auto& f : path) {
        out.push_back(f);
        used_keys.insert(flight_key(f.a, f.b, f.s));
    }
}

// 末尾区間[start_tm, DAY_END]を、戻り制約なしで最大限埋める
void fill_tail_chain(vector<Flight>& out, int start_city, int start_tm,
                     const vector<vector<int>>& dur,
                     const vector<vector<int>>& sq_edge_count,
                     unordered_set<uint64_t>& used_keys) {
    auto path = build_best_fill_path(start_city, start_tm, DAY_END, dur, sq_edge_count, used_keys,
                                     false);
    for (const auto& f : path) {
        out.push_back(f);
        used_keys.insert(flight_key(f.a, f.b, f.s));
    }
}

// スクエア便の発着回数が多い都市を返す
int pick_busy_city(const vector<vector<int>>& sq_edge_count) {
    int n = (int)sq_edge_count.size();
    int best_city = 0;
    int best_score = -1;
    for (int v = 0; v < n; ++v) {
        int sc = 0;
        for (int u = 0; u < n; ++u) {
            sc += sq_edge_count[v][u];
            sc += sq_edge_count[u][v];
        }
        if (sc > best_score) {
            best_score = sc;
            best_city = v;
        }
    }
    return best_city;
}

// 既存ルートの前後ギャップを埋めて、待機時間を減らした便列を作る
vector<Flight> densify_route(const vector<int>& route_idx, const vector<Candidate>& cand,
                             const vector<vector<int>>& dur,
                             const vector<vector<int>>& sq_edge_count, int fallback_city,
                             unordered_set<uint64_t>& used_keys) {
    vector<Flight> core;
    core.reserve(route_idx.size());
    for (int ci : route_idx) {
        const auto& c = cand[ci];
        core.push_back(Flight{c.a, c.b, c.s, c.t});
    }

    vector<Flight> out;
    if (core.empty()) {
        fill_tail_chain(out, fallback_city, DAY_START, dur, sq_edge_count, used_keys);
        return out;
    }

    // 初便までの待機を往復で埋める
    fill_gap_roundtrips(out, core[0].a, DAY_START, core[0].s, dur, sq_edge_count, used_keys);

    for (int i = 0; i < (int)core.size(); ++i) {
        out.push_back(core[i]);
        used_keys.insert(flight_key(core[i].a, core[i].b, core[i].s));
        if (i + 1 < (int)core.size()) {
            // 既存2便の間の待機を往復で埋める（出発都市は維持）
            fill_gap_roundtrips(out, core[i].b, core[i].t, core[i + 1].s, dur, sq_edge_count,
                                used_keys);
        }
    }

    // 最終便以降を21:00まで埋める
    fill_tail_chain(out, core.back().b, core.back().t, dur, sq_edge_count, used_keys);
    return out;
}

// 奪取寄与がない便を、連結性を壊さない範囲で削除する
void prune_redundant_won_routes(vector<vector<int>>& routes, const vector<Candidate>& cand, int n) {
    vector<vector<vector<int>>> bit_cnt(
        n, vector<vector<int>>(n, vector<int>(DEADLINE_COUNT, 0)));

    for (const auto& seq : routes) {
        for (int ci : seq) {
            const auto& c = cand[ci];
            if (c.mask == 0) continue;
            for (int k = 0; k < DEADLINE_COUNT; ++k) {
                if ((c.mask >> k) & 1u) bit_cnt[c.a][c.b][k]++;
            }
        }
    }

    bool changed = true;
    while (changed) {
        changed = false;
        for (int p = 0; p < (int)routes.size(); ++p) {
            auto& seq = routes[p];
            for (int i = 0; i < (int)seq.size(); ++i) {
                int ci = seq[i];
                const auto& c = cand[ci];
                if (c.mask == 0) continue;

                bool has_unique = false;
                for (int k = 0; k < DEADLINE_COUNT; ++k) {
                    if (((c.mask >> k) & 1u) && bit_cnt[c.a][c.b][k] == 1) {
                        has_unique = true;
                        break;
                    }
                }
                if (has_unique) continue;

                bool link_ok = true;
                if (i > 0 && i + 1 < (int)seq.size()) {
                    const auto& prv = cand[seq[i - 1]];
                    const auto& nxt = cand[seq[i + 1]];
                    if (prv.b != nxt.a || prv.t > nxt.s) link_ok = false;
                }
                if (!link_ok) continue;

                for (int k = 0; k < DEADLINE_COUNT; ++k) {
                    if ((c.mask >> k) & 1u) bit_cnt[c.a][c.b][k]--;
                }
                seq.erase(seq.begin() + i);
                --i;
                changed = true;
            }
        }
    }
}

// latest[k][dst][src] = 締切kまでにdstへ到着するsrcの最遅出発時刻
vector<vector<vector<int>>> build_latest_tensor(int n, const vector<Flight>& flights,
                                                const vector<int>& deadlines) {
    vector<Flight> fs = flights;
    sort(fs.begin(), fs.end(), [](const Flight& p, const Flight& q) {
        if (p.s != q.s) return p.s > q.s;
        return p.t > q.t;
    });

    vector<vector<vector<int>>> latest(
        DEADLINE_COUNT, vector<vector<int>>(n, vector<int>(n, NEG)));

    for (int k = 0; k < DEADLINE_COUNT; ++k) {
        int dl = deadlines[k];
        for (int dst = 0; dst < n; ++dst) {
            vector<int> cur(n, NEG);
            cur[dst] = dl;
            for (const auto& f : fs) {
                if (f.t <= cur[f.b] && f.s > cur[f.a]) cur[f.a] = f.s;
            }
            latest[k][dst] = std::move(cur);
        }
    }
    return latest;
}

ll calc_exact_score(const vector<vector<int>>& routes, const vector<Candidate>& cand,
                    int n, const vector<int>& deadlines,
                    const vector<vector<vector<int>>>& latest_sq,
                    const vector<pair<int, int>>& eval_pairs,
                    const vector<vector<ll>>& pair_w) {
    vector<Flight> circle;
    for (const auto& seq : routes) {
        for (int ci : seq) {
            const auto& c = cand[ci];
            circle.push_back(Flight{c.a, c.b, c.s, c.t});
        }
    }

    auto latest_ci = build_latest_tensor(n, circle, deadlines);

    ll vci = 0;
    for (int k = 0; k < DEADLINE_COUNT; ++k) {
        for (const auto& pr : eval_pairs) {
            int a = pr.first;
            int b = pr.second;
            if (latest_sq[k][b][a] < latest_ci[k][b][a]) vci += pair_w[a][b];
        }
    }
    return vci;
}

// 1手先を返すためのビーム（評価はスクエア基準の近似）
int beam_pick_next(int start_city, int start_tm, const vector<Candidate>& cand,
                   const vector<int>& all_by_time, const vector<vector<int>>& by_from,
                   const vector<char>& blocked, const vector<FillInfo>& fill_info,
                   XorShift64* rng = nullptr, double rand_amp = 0.0) {
    struct Node {
        int city;
        int tm;
        int depth;
        int first_ci;
        double score;
    };

    vector<Node> beam;
    beam.push_back(Node{start_city, start_tm, 0, -1, 0.0});

    int best_first = -1;
    double best_score = -1e300;

    auto try_expand = [&](const Node& node, int ci, vector<Node>& nxt) {
        if (blocked[ci]) return;
        const auto& c = cand[ci];
        if (c.s < node.tm) return;
        int wait = c.s - node.tm;

        int wait_lim = (node.city == -1 ? WAIT_FIRST_MAX : WAIT_NEXT_MAX);
        if (wait > wait_lim) return;

        ll gain = c.base_gain;
        int d = c.t - c.s;
        double fill_bonus = 0.0;
        if (node.city != -1 && wait > 0) {
            fill_bonus = estimate_fill_gain(fill_info[node.city], wait, true);
        }

        double add = -1e300;
        if (gain > 0) {
            add = STEAL_BEAM_GAIN_WEIGHT * (double)gain + 110.0 * c.edge -
                  1.9 * wait - 0.35 * d + 45.0 * fill_bonus;
        } else {
            // 既に奪取済み（増分なし）になりやすい便は再構築でも採用しない
            if (c.mask != 0) return;
            if (c.edge == 0) return;
            if (wait > ZERO_WAIT_ALLOW) return;
            add = 60.0 * c.edge - 12.0 * wait - 1.1 * d + 30.0 * fill_bonus;
        }

        // 同点近辺でランダムノイズを入れて局所解脱出を強化
        if (rng != nullptr && rand_amp > 0.0) {
            add *= (1.0 + rand_amp * (rng->next_double() - 0.5));
        }

        Node nn;
        nn.city = c.b;
        nn.tm = c.t;
        nn.depth = node.depth + 1;
        nn.first_ci = (node.first_ci == -1 ? ci : node.first_ci);
        nn.score = node.score + add;

        if (nn.first_ci != -1 && nn.score > best_score) {
            best_score = nn.score;
            best_first = nn.first_ci;
        }
        nxt.push_back(nn);
    };

    for (int dep = 0; dep < BEAM_DEPTH; ++dep) {
        vector<Node> nxt;
        nxt.reserve((size_t)beam.size() * 64ULL);

        for (const auto& node : beam) {
            if (node.city == -1) {
                auto it = lower_bound(all_by_time.begin(), all_by_time.end(), node.tm,
                                      [&](int idx, int t0) { return cand[idx].s < t0; });
                int scanned = 0;
                for (; it != all_by_time.end() && scanned < BEAM_SCAN_FIRST; ++it, ++scanned) {
                    try_expand(node, *it, nxt);
                }
            } else {
                const auto& list = by_from[node.city];
                auto it = lower_bound(list.begin(), list.end(), node.tm,
                                      [&](int idx, int t0) { return cand[idx].s < t0; });
                int scanned = 0;
                for (; it != list.end() && scanned < BEAM_SCAN_NEXT; ++it, ++scanned) {
                    try_expand(node, *it, nxt);
                }
            }
        }

        if (nxt.empty()) break;
        sort(nxt.begin(), nxt.end(), [](const Node& a, const Node& b) {
            if (a.score != b.score) return a.score > b.score;
            if (a.tm != b.tm) return a.tm < b.tm;
            return a.city < b.city;
        });
        if ((int)nxt.size() > BEAM_WIDTH) nxt.resize(BEAM_WIDTH);
        beam.swap(nxt);
    }

    return best_first;
}

// 1機体をビームで再構築
vector<int> rebuild_plane_with_beam(
    int p, const vector<vector<int>>& routes, const vector<Candidate>& cand,
    const vector<int>& all_by_time, const vector<vector<int>>& by_from,
    int n, int slot_cnt, const vector<FillInfo>& fill_info, XorShift64* rng = nullptr,
    int keep_prefix = -1, bool diversify = false) {
    (void)n;
    (void)slot_cnt;

    // 他機体で既に使われている候補は再利用しない
    vector<char> blocked(cand.size(), 0);
    for (int q = 0; q < (int)routes.size(); ++q) {
        if (q == p) continue;
        for (int ci : routes[q]) blocked[ci] = 1;
    }

    vector<int> seq;
    int city = -1;
    int tm = DAY_START;

    // 既存ルートの前半を残して後半のみ再構築するモード
    if (keep_prefix < 0) keep_prefix = 0;
    keep_prefix = min(keep_prefix, (int)routes[p].size());
    for (int i = 0; i < keep_prefix; ++i) {
        int ci = routes[p][i];
        if (blocked[ci]) break;
        seq.push_back(ci);
        blocked[ci] = 1;
        city = cand[ci].b;
        tm = cand[ci].t;
    }

    double rand_amp = (diversify ? 0.08 : 0.0);
    int zero_streak = 0;

    for (int leg = (int)seq.size(); leg < REBUILD_MAX_LEGS; ++leg) {
        int ci =
            beam_pick_next(city, tm, cand, all_by_time, by_from, blocked, fill_info, rng, rand_amp);
        if (ci == -1) break;

        const auto& c = cand[ci];
        if (c.base_gain <= 0) {
            ++zero_streak;
        } else {
            zero_streak = 0;
        }
        if (zero_streak >= 3) break;

        seq.push_back(ci);
        blocked[ci] = 1;

        city = c.b;
        tm = c.t;
        if (tm >= DAY_END) break;
    }
    return seq;
}

// 1機体に対する局所近傍（削除/挿入/置換/部分破壊再構築）
vector<int> mutate_plane_local(
    int p, const vector<vector<int>>& routes, const vector<Candidate>& cand,
    const vector<int>& all_by_time, const vector<vector<int>>& by_from,
    const vector<FillInfo>& fill_info, XorShift64& rng) {
    vector<int> seq = routes[p];

    vector<char> blocked(cand.size(), 0), in_seq(cand.size(), 0);
    for (int q = 0; q < (int)routes.size(); ++q) {
        if (q == p) continue;
        for (int ci : routes[q]) blocked[ci] = 1;
    }
    for (int ci : seq) in_seq[ci] = 1;

    auto node_value = [&](const Candidate& c, int prev_tm, int prev_city) -> double {
        int wait = c.s - prev_tm;
        if (wait < 0) return -1e300;
        double fill_bonus = 0.0;
        if (prev_city != -1 && wait > 0) {
            fill_bonus = estimate_fill_gain(fill_info[prev_city], wait, true);
        }
        return STEAL_BEAM_GAIN_WEIGHT * (double)c.base_gain + 95.0 * (double)c.edge -
               2.1 * (double)wait + 32.0 * fill_bonus;
    };

    int op = rng.next_int(0, 4);

    // 削除
    if (op == 0 && !seq.empty()) {
        for (int tr = 0; tr < 8; ++tr) {
            int pos = rng.next_int(0, (int)seq.size() - 1);
            bool ok = true;
            if (pos > 0 && pos + 1 < (int)seq.size()) {
                const auto& prv = cand[seq[pos - 1]];
                const auto& nxt = cand[seq[pos + 1]];
                if (prv.b != nxt.a || prv.t > nxt.s) ok = false;
            }
            if (!ok) continue;
            seq.erase(seq.begin() + pos);
            return seq;
        }
    }

    // 挿入
    if (op == 1 && (int)seq.size() < REBUILD_MAX_LEGS + 4) {
        int g = rng.next_int(0, (int)seq.size());
        int prev_city = -1, prev_tm = DAY_START;
        if (g > 0) {
            const auto& prv = cand[seq[g - 1]];
            prev_city = prv.b;
            prev_tm = prv.t;
        }
        int next_city = -1, next_tm = DAY_END;
        bool has_next = (g < (int)seq.size());
        if (has_next) {
            const auto& nxt = cand[seq[g]];
            next_city = nxt.a;
            next_tm = nxt.s;
        }

        int best_ci = -1;
        double best_sc = -1e300;

        if (prev_city == -1) {
            auto it = lower_bound(all_by_time.begin(), all_by_time.end(), prev_tm,
                                  [&](int idx, int t0) { return cand[idx].s < t0; });
            int scanned = 0;
            for (; it != all_by_time.end() && scanned < BEAM_SCAN_FIRST * 2; ++it, ++scanned) {
                int ci = *it;
                if (blocked[ci] || in_seq[ci]) continue;
                const auto& c = cand[ci];
                if (has_next && (c.b != next_city || c.t > next_tm)) continue;
                double sc = node_value(c, prev_tm, prev_city);
                if (sc > best_sc) {
                    best_sc = sc;
                    best_ci = ci;
                }
            }
        } else {
            const auto& list = by_from[prev_city];
            auto it = lower_bound(list.begin(), list.end(), prev_tm,
                                  [&](int idx, int t0) { return cand[idx].s < t0; });
            int scanned = 0;
            for (; it != list.end() && scanned < BEAM_SCAN_NEXT * 3; ++it, ++scanned) {
                int ci = *it;
                if (blocked[ci] || in_seq[ci]) continue;
                const auto& c = cand[ci];
                if (has_next && (c.b != next_city || c.t > next_tm)) continue;
                double sc = node_value(c, prev_tm, prev_city);
                if (sc > best_sc) {
                    best_sc = sc;
                    best_ci = ci;
                }
            }
        }
        if (best_ci != -1) {
            seq.insert(seq.begin() + g, best_ci);
            return seq;
        }
    }

    // 置換（同OD内で時刻を振り替える）
    if (op == 2 && !seq.empty()) {
        int pos = rng.next_int(0, (int)seq.size() - 1);
        int old_ci = seq[pos];
        const auto& old = cand[old_ci];
        int prev_tm = (pos > 0 ? cand[seq[pos - 1]].t : DAY_START);
        int next_tm = (pos + 1 < (int)seq.size() ? cand[seq[pos + 1]].s : DAY_END);

        int best_ci = old_ci;
        double best_sc = node_value(old, prev_tm, (pos > 0 ? cand[seq[pos - 1]].b : -1));

        const auto& list = by_from[old.a];
        auto it = lower_bound(list.begin(), list.end(), max(prev_tm, old.s - 120),
                              [&](int idx, int t0) { return cand[idx].s < t0; });
        int scanned = 0;
        for (; it != list.end() && scanned < BEAM_SCAN_NEXT * 4; ++it, ++scanned) {
            int ci = *it;
            const auto& c = cand[ci];
            if (c.s > old.s + 120) break;
            if (c.b != old.b) continue;
            if (ci != old_ci && (blocked[ci] || in_seq[ci])) continue;
            if (c.s < prev_tm || c.t > next_tm) continue;
            double sc = node_value(c, prev_tm, (pos > 0 ? cand[seq[pos - 1]].b : -1));
            if (sc > best_sc) {
                best_sc = sc;
                best_ci = ci;
            }
        }
        if (best_ci != old_ci) {
            seq[pos] = best_ci;
            return seq;
        }
    }

    // 部分破壊再構築（局所解脱出）
    if (op == 3) {
        int keep = 0;
        if (!seq.empty()) keep = rng.next_int(0, min((int)seq.size(), 3));
        return rebuild_plane_with_beam(p, routes, cand, all_by_time, by_from, 0, 0, fill_info, &rng,
                                       keep, true);
    }

    // 大きいジャンプ（丸ごと再構築）
    return rebuild_plane_with_beam(p, routes, cand, all_by_time, by_from, 0, 0, fill_info, &rng, 0,
                                   true);
}

}  // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    auto global_start = chrono::steady_clock::now();

    int N, R;
    cin >> N >> R;

    vector<int> x(N), y(N);
    vector<ll> w(N);
    for (int i = 0; i < N; ++i) cin >> x[i] >> y[i] >> w[i];

    int M;
    cin >> M;
    vector<Flight> square;
    square.reserve(M);
    for (int i = 0; i < M; ++i) {
        int a, b;
        string s_tok, t_tok;
        cin >> a >> s_tok >> b >> t_tok;
        int s = parse_time(s_tok);
        int t = parse_time(t_tok);
        square.push_back(Flight{a - 1, b - 1, s, t});
    }

    int K;
    cin >> K;

    vector<int> deadlines = build_deadlines();
    int SLOT_CNT = (DAY_END - DAY_START) / SLOT_STEP + 1;

    // 直行所要時間
    vector<vector<int>> dur(N, vector<int>(N, 0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (i == j) continue;
            long double dx = (long double)x[i] - (long double)x[j];
            long double dy = (long double)y[i] - (long double)y[j];
            long double d = sqrtl(dx * dx + dy * dy);
            dur[i][j] = calc_duration_min(d);
        }
    }

    // スクエア便密度
    vector<vector<int>> sq_edge_count(N, vector<int>(N, 0));
    for (const auto& f : square) sq_edge_count[f.a][f.b]++;

    // 探索中の待機埋め近似で使う都市ごとの埋めやすさ指標
    vector<FillInfo> fill_info(N);
    for (int a = 0; a < N; ++a) {
        long double best_one_ratio = -1.0L;
        long double best_rt_ratio = -1.0L;
        for (int b = 0; b < N; ++b) {
            if (a == b) continue;
            int d1 = dur[a][b];
            int e1 = sq_edge_count[a][b];
            if (d1 > 0) {
                long double r1 = (long double)e1 / (long double)d1;
                if (r1 > best_one_ratio ||
                    (fabsl(r1 - best_one_ratio) < 1e-18L && d1 < fill_info[a].one_time)) {
                    best_one_ratio = r1;
                    fill_info[a].one_time = d1;
                    fill_info[a].one_edge = e1;
                }
            }

            int d2 = dur[b][a];
            int rt = d1 + d2;
            int er = sq_edge_count[a][b] + sq_edge_count[b][a];
            if (rt > 0) {
                long double rr = (long double)er / (long double)rt;
                if (rr > best_rt_ratio ||
                    (fabsl(rr - best_rt_ratio) < 1e-18L && rt < fill_info[a].rt_time)) {
                    best_rt_ratio = rr;
                    fill_info[a].rt_time = rt;
                    fill_info[a].rt_edge = er;
                }
            }
        }
    }

    // 評価対象ODと人口積
    vector<vector<char>> valid_pair(N, vector<char>(N, 0));
    vector<vector<ll>> pair_w(N, vector<ll>(N, 0));
    vector<pair<int, int>> eval_pairs;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (i == j) continue;
            long double dx = (long double)x[i] - (long double)x[j];
            long double dy = (long double)y[i] - (long double)y[j];
            long double d = sqrtl(dx * dx + dy * dy);
            if (d + 1e-12L >= 0.25L * (long double)R) {
                valid_pair[i][j] = 1;
                pair_w[i][j] = w[i] * w[j];
                eval_pairs.push_back({i, j});
            }
        }
    }

    // スクエア側の最遅出発時刻
    auto latest_sq = build_latest_tensor(N, square, deadlines);

    // 候補便生成（スクエアOD + 近距離OD）
    vector<Candidate> cand;
    cand.reserve(M * 9 + N * 8 * 120);
    const int shifts[9] = {0, 5, 10, 15, 20, 25, 30, 35, 40};
    for (const auto& f : square) {
        int a = f.a, b = f.b;
        int d = dur[a][b];
        for (int sh : shifts) {
            int s = f.s + sh;
            int t = s + d;
            if (s < DAY_START || t > DAY_END) continue;

            uint32_t mask = 0;
            if (valid_pair[a][b]) {
                for (int k = 0; k < DEADLINE_COUNT; ++k) {
                    if (t > deadlines[k]) continue;
                    if (s > latest_sq[k][b][a]) mask |= (1u << k);
                }
            }
            ll pw = pair_w[a][b];
            ll bg = pw * (ll)__builtin_popcount(mask);
            cand.push_back(Candidate{a, b, s, t, sq_edge_count[a][b], mask, pw, bg});
        }
    }

    // 待機活用のため、各都市から近い都市への便も候補に入れる
    for (int a = 0; a < N; ++a) {
        vector<pair<int, int>> near;
        near.reserve(N - 1);
        for (int b = 0; b < N; ++b) {
            if (a == b) continue;
            near.push_back({dur[a][b], b});
        }
        sort(near.begin(), near.end());

        int use = min((int)near.size(), NEAR_PER_CITY);
        for (int z = 0; z < use; ++z) {
            int b = near[z].second;
            int d = dur[a][b];
            // あまり長い便は待機埋め用途としては使いにくいので除外
            if (d > 120) continue;

            for (int s = DAY_START; s + d <= DAY_END; s += NEAR_TIME_STEP) {
                int t = s + d;
                uint32_t mask = 0;
                if (valid_pair[a][b]) {
                    for (int k = 0; k < DEADLINE_COUNT; ++k) {
                        if (t > deadlines[k]) continue;
                        if (s > latest_sq[k][b][a]) mask |= (1u << k);
                    }
                }
                ll pw = pair_w[a][b];
                ll bg = pw * (ll)__builtin_popcount(mask);
                cand.push_back(Candidate{a, b, s, t, sq_edge_count[a][b], mask, pw, bg});
            }
        }
    }

    // 重複除去
    sort(cand.begin(), cand.end(), [](const Candidate& p, const Candidate& q) {
        return tie(p.a, p.b, p.s) < tie(q.a, q.b, q.s);
    });
    cand.erase(unique(cand.begin(), cand.end(), [](const Candidate& p, const Candidate& q) {
                  return p.a == q.a && p.b == q.b && p.s == q.s;
              }),
              cand.end());

    // 候補便の索引
    vector<vector<int>> by_from(N);
    vector<int> all_by_time;
    all_by_time.reserve(cand.size());
    for (int i = 0; i < (int)cand.size(); ++i) {
        by_from[cand[i].a].push_back(i);
        all_by_time.push_back(i);
    }
    for (int a = 0; a < N; ++a) {
        sort(by_from[a].begin(), by_from[a].end(), [&](int i, int j) {
            return cand[i].s < cand[j].s;
        });
    }
    sort(all_by_time.begin(), all_by_time.end(), [&](int i, int j) {
        return cand[i].s < cand[j].s;
    });

    // 初期解: 増分奪取を主軸にした全体貪欲
    vector<vector<int>> routes(K);
    vector<PlaneState> ps(K);
    vector<vector<uint32_t>> won_mask(N, vector<uint32_t>(N, 0));
    vector<char> used_ci(cand.size(), 0);

    auto incremental_gain = [&](const Candidate& c) -> ll {
        if (c.pair_w == 0 || c.mask == 0) return 0;
        uint32_t add_bits = c.mask & (~won_mask[c.a][c.b]);
        if (add_bits == 0) return 0;
        return c.pair_w * (ll)__builtin_popcount(add_bits);
    };

    auto future_gain_from = [&](int city, int tm) -> ll {
        const auto& list = by_from[city];
        auto it = lower_bound(list.begin(), list.end(), tm,
                              [&](int idx, int t0) { return cand[idx].s < t0; });
        ll best = 0;
        int checked = 0;
        for (; it != list.end(); ++it) {
            int ci = *it;
            if (used_ci[ci]) continue;
            const auto& c = cand[ci];
            if (c.s > tm + FUTURE_HORIZON) break;
            if (++checked > FUTURE_SCAN_MAX) break;

            ll g = incremental_gain(c);
            if (g > best) best = g;
        }
        return best;
    };

    while (true) {
        ll best_gain = 0;
        int best_wait = 1e9;
        int best_edge = -1;
        int best_p = -1;
        int best_ci = -1;

        ll best_move_future = 0;
        int best_move_wait = 1e9;
        int best_move_edge = -1;
        int best_move_p = -1;
        int best_move_ci = -1;

        int first_inactive = -1;
        for (int p = 0; p < K; ++p) {
            if (!ps[p].active) {
                first_inactive = p;
                break;
            }
        }

        // 未使用機体の初手候補は1回だけ評価する
        if (first_inactive != -1) {
            int scanned = 0;
            for (int idx : all_by_time) {
                if (used_ci[idx]) continue;
                const auto& c = cand[idx];
                int wait = c.s - DAY_START;
                if (wait < 0) continue;
                if (wait > WAIT_FIRST_MAX) break;
                if (++scanned > INIT_SCAN_MAX) break;

                ll gain = incremental_gain(c);
                if (gain > 0) {
                    if (gain > best_gain ||
                        (gain == best_gain && wait < best_wait) ||
                        (gain == best_gain && wait == best_wait && c.edge > best_edge)) {
                        best_gain = gain;
                        best_wait = wait;
                        best_edge = c.edge;
                        best_p = first_inactive;
                        best_ci = idx;
                    }
                } else {
                    if (c.mask != 0) continue;
                    if (wait > ZERO_WAIT_ALLOW) continue;
                    if (c.edge == 0) continue;
                    ll fut = future_gain_from(c.b, c.t);
                    if (fut <= 0) continue;
                    if (fut > best_move_future ||
                        (fut == best_move_future && wait < best_move_wait) ||
                        (fut == best_move_future && wait == best_move_wait &&
                         c.edge > best_move_edge)) {
                        best_move_future = fut;
                        best_move_wait = wait;
                        best_move_edge = c.edge;
                        best_move_p = first_inactive;
                        best_move_ci = idx;
                    }
                }
            }
        }

        // 使用中機体の次手候補を評価
        for (int p = 0; p < K; ++p) {
            if (!ps[p].active) continue;
            int cur = ps[p].city;
            int tm = ps[p].tm;
            const auto& list = by_from[cur];
            auto it = lower_bound(list.begin(), list.end(), tm,
                                  [&](int idx, int t0) { return cand[idx].s < t0; });

            int scanned = 0;
            for (; it != list.end() && scanned < ACTIVE_SCAN_MAX; ++it, ++scanned) {
                int ci = *it;
                if (used_ci[ci]) continue;
                const auto& c = cand[ci];
                int wait = c.s - tm;
                if (wait > ACTIVE_WAIT_HORIZON) break;

                ll gain = incremental_gain(c);
                if (gain > 0) {
                    if (gain > best_gain ||
                        (gain == best_gain && wait < best_wait) ||
                        (gain == best_gain && wait == best_wait && c.edge > best_edge)) {
                        best_gain = gain;
                        best_wait = wait;
                        best_edge = c.edge;
                        best_p = p;
                        best_ci = ci;
                    }
                } else {
                    if (c.mask != 0) continue;
                    if (wait < 0 || wait > ZERO_WAIT_ALLOW) continue;
                    if (c.edge == 0) continue;
                    ll fut = future_gain_from(c.b, c.t);
                    if (fut <= 0) continue;
                    if (fut > best_move_future ||
                        (fut == best_move_future && wait < best_move_wait) ||
                        (fut == best_move_future && wait == best_move_wait &&
                         c.edge > best_move_edge)) {
                        best_move_future = fut;
                        best_move_wait = wait;
                        best_move_edge = c.edge;
                        best_move_p = p;
                        best_move_ci = ci;
                    }
                }
            }
        }

        int pick_p = -1;
        int pick_ci = -1;
        ll pick_gain = 0;
        if (best_p != -1 && best_ci != -1 && best_gain > 0) {
            // 奪取優先: 将来見込みが極端に高い場合のみ0奪取移動を許可
            if (best_move_p != -1 && best_move_ci != -1 &&
                best_move_future * MOVE_OVERRIDE_NUM >= best_gain * MOVE_OVERRIDE_DEN) {
                pick_p = best_move_p;
                pick_ci = best_move_ci;
                pick_gain = 0;
            } else {
                pick_p = best_p;
                pick_ci = best_ci;
                pick_gain = best_gain;
            }
        } else if (best_move_p != -1 && best_move_ci != -1) {
            pick_p = best_move_p;
            pick_ci = best_move_ci;
            pick_gain = 0;
        } else {
            break;
        }

        const auto& c = cand[pick_ci];
        if (!ps[pick_p].active) ps[pick_p].active = true;
        ps[pick_p].city = c.b;
        ps[pick_p].tm = c.t;
        routes[pick_p].push_back(pick_ci);
        used_ci[pick_ci] = 1;

        if (pick_gain > 0) {
            won_mask[c.a][c.b] |= c.mask;
        }
    }

    // 焼きなまし: 1機体をビーム再構築して採用可否を温度で判定
    auto start_tp = chrono::steady_clock::now();
    XorShift64 rng(123456789ULL);

    ll cur_score = calc_exact_score(routes, cand, N, deadlines, latest_sq, eval_pairs, pair_w);
    vector<vector<int>> best_routes = routes;
    ll best_score = cur_score;
    vector<double> fast_plane(K, 0.0), wait_plane(K, 0.0);
    double fast_total = 0.0, wait_total = 0.0;
    for (int p = 0; p < K; ++p) {
        fast_plane[p] = calc_plane_fast_score(routes[p], cand, fill_info);
        wait_plane[p] = calc_plane_wait_fill_score(routes[p], cand, fill_info);
        fast_total += fast_plane[p];
        wait_total += wait_plane[p];
    }
    double best_wait_total = wait_total;

    long double t0 = max(1.0L, fabsl((long double)cur_score) * 0.02L);
    long double t1 = max(1.0L, fabsl((long double)cur_score) * 1e-6L);
    long double ft0 = max(1.0L, fabsl((long double)fast_total) * 0.03L);
    long double ft1 = max(1.0L, fabsl((long double)fast_total) * 1e-5L);
    int stagnate = 0;

    double pre_elapsed =
        chrono::duration<double>(chrono::steady_clock::now() - global_start).count();
    double sa_budget = min(SA_MAX_TIME_SEC, TOTAL_TIME_LIMIT_SEC - pre_elapsed - SA_MARGIN_SEC);
    if (sa_budget < 0.0) sa_budget = 0.0;

    while (sa_budget > 0.0) {
        double elapsed = chrono::duration<double>(chrono::steady_clock::now() - start_tp).count();
        if (elapsed >= sa_budget) break;

        int p = rng.next_int(0, K - 1);
        vector<vector<int>> nxt_routes = routes;
        int mode = rng.next_int(0, 99);
        if (stagnate >= STAGNATE_LIMIT && rng.next_int(0, 99) < 50) mode = 99;
        if (mode < 38) {
            nxt_routes[p] = rebuild_plane_with_beam(p, routes, cand, all_by_time, by_from, N,
                                                    SLOT_CNT, fill_info, &rng, 0, false);
        } else if (mode < 83) {
            nxt_routes[p] =
                mutate_plane_local(p, routes, cand, all_by_time, by_from, fill_info, rng);
        } else {
            int keep = 0;
            if (!routes[p].empty()) keep = rng.next_int(0, min((int)routes[p].size(), 3));
            nxt_routes[p] = rebuild_plane_with_beam(p, routes, cand, all_by_time, by_from, N,
                                                    SLOT_CNT, fill_info, &rng, keep, true);
        }

        if (nxt_routes[p] == routes[p]) continue;

        // 差分評価: 変更機体 p だけ高速再評価して悪手を先に間引く
        double nxt_fast_p = calc_plane_fast_score(nxt_routes[p], cand, fill_info);
        double delta_fast = nxt_fast_p - fast_plane[p];
        double nxt_wait_p = calc_plane_wait_fill_score(nxt_routes[p], cand, fill_info);
        double delta_wait = nxt_wait_p - wait_plane[p];
        if (delta_fast < 0.0) {
            long double rf = (long double)elapsed / (long double)sa_budget;
            long double ftemp = ft0 * pow((double)(ft1 / ft0), (double)rf);
            long double fprob = expl((long double)delta_fast / (FAST_SKIP_COEF * ftemp));
            if (fprob < (long double)rng.next_double()) {
                ++stagnate;
                continue;
            }
        }

        ll nxt_score =
            calc_exact_score(nxt_routes, cand, N, deadlines, latest_sq, eval_pairs, pair_w);
        ll delta = nxt_score - cur_score;
        long double delta_aug = (long double)delta + (long double)(WAIT_AUG_WEIGHT * delta_wait);

        bool accept = false;
        if (delta_aug >= 0) {
            accept = true;
        } else {
            long double r = (long double)elapsed / (long double)sa_budget;
            long double temp = t0 * pow((double)(t1 / t0), (double)r);
            long double prob = expl((long double)delta_aug / temp);
            if (prob > (long double)rng.next_double()) accept = true;
        }

        if (accept) {
            routes.swap(nxt_routes);
            cur_score = nxt_score;
            fast_total += delta_fast;
            wait_total += delta_wait;
            fast_plane[p] = nxt_fast_p;
            wait_plane[p] = nxt_wait_p;
            if (cur_score > best_score || (cur_score == best_score && wait_total > best_wait_total)) {
                best_score = cur_score;
                best_routes = routes;
                best_wait_total = wait_total;
                stagnate = 0;
            } else {
                ++stagnate;
            }
        } else {
            ++stagnate;
        }
    }

    // 探索後に、寄与のない奪取便を削って待機埋めの余地を作る
    prune_redundant_won_routes(best_routes, cand, N);

    // 探索内最適化に加えて、出力前にも隙間埋め後処理を適用
    int busy_city = pick_busy_city(sq_edge_count);
    vector<vector<Flight>> final_flights(K);
    unordered_set<uint64_t> used_keys;
    used_keys.reserve(cand.size() * 2 + 4096);

    // コア便を先に予約し、後から入れる埋め便との衝突を防ぐ
    for (int p = 0; p < K; ++p) {
        for (int ci : best_routes[p]) {
            const auto& c = cand[ci];
            used_keys.insert(flight_key(c.a, c.b, c.s));
        }
    }

    for (int p = 0; p < K; ++p) {
        int fallback_city = busy_city;
        if (!best_routes[p].empty()) {
            fallback_city = cand[best_routes[p][0]].a;
        }
        final_flights[p] =
            densify_route(best_routes[p], cand, dur, sq_edge_count, fallback_city, used_keys);
    }

    for (int p = 0; p < K; ++p) {
        cout << final_flights[p].size() << '\n';
        for (const auto& f : final_flights[p]) {
            cout << (f.a + 1) << ' ' << to_hhmm(f.s) << ' ' << (f.b + 1) << ' ' << to_hhmm(f.t)
                 << '\n';
        }
    }

    return 0;
}