#include <bits/stdc++.h>
using namespace std;

// Constants
const int N = 47;
const int R = 1000;
const int M_FLIGHTS = 400;
const int K = 25;
const int TIME_MIN = 360;  // 06:00 in minutes
const int TIME_MAX = 1260; // 21:00 in minutes
const int TIME_SLOTS = 181; // (1260-360)/5 + 1
const int NUM_TARGETS = 21; // 11:00, 11:30, ..., 21:00
const int NEG_INF = -1000000;

// Globals
int cx[N], cy[N], cw[N]; // city coords and population
int sq_a[M_FLIGHTS], sq_b[M_FLIGHTS], sq_s[M_FLIGHTS], sq_t[M_FLIGHTS]; // square flights
double dist_table[N][N];
int flight_time[N][N]; // in minutes, 0 if same city
bool valid_pair[N][N]; // distance >= 250

// target arrival times: 11:00=660, 11:30=690, ..., 21:00=1260
int target_times[NUM_TARGETS];

// s_sq[i][j][t] = latest departure from i to reach j by target_times[t] using Square only
int s_sq[N][N][NUM_TARGETS];

// Random
mt19937 rng(42);

int parse_time(const string& s) {
    int h = stoi(s.substr(0, 2));
    int m = stoi(s.substr(3, 2));
    return h * 60 + m;
}

string format_time(int t) {
    char buf[6];
    sprintf(buf, "%02d:%02d", t / 60, t % 60);
    return string(buf);
}

int calc_flight_time(double d) {
    double raw = 60.0 * d / 800.0 + 40.0;
    int rounded = (int)ceil(raw / 5.0) * 5;
    return rounded;
}

// Compute s_sq for all (i, j, t_idx) using reverse Dijkstra from j at time target_times[t_idx]
void compute_square_dijkstra() {
    // Build adjacency: for each flight, it goes from sq_a to sq_b, depart sq_s, arrive sq_t
    // Reverse: from sq_b at time sq_t, we can reach sq_a at time sq_s (latest departure = sq_s)
    // We want: for each destination j and target time T, find latest departure from each city i

    // For each (j, t_idx):
    //   Initialize best[j] = target_times[t_idx]
    //   Use max-heap (latest departure first)
    //   For each city reached at time arr_time, look at all flights arriving at that city
    //   with arrival time <= arr_time. The departure time of that flight is a candidate.

    // Build reverse adjacency: for each city b, list of (a, depart_time, arrive_time)
    vector<vector<tuple<int,int,int>>> rev_adj(N);
    for (int f = 0; f < M_FLIGHTS; f++) {
        rev_adj[sq_b[f]].emplace_back(sq_a[f], sq_s[f], sq_t[f]);
    }
    // Sort by arrival time for each destination
    for (int b = 0; b < N; b++) {
        sort(rev_adj[b].begin(), rev_adj[b].end(), [](auto& a, auto& b) {
            return get<2>(a) > get<2>(b); // sort by arrive_time descending
        });
    }

    for (int t_idx = 0; t_idx < NUM_TARGETS; t_idx++) {
        int T = target_times[t_idx];
        for (int j = 0; j < N; j++) {
            // best[i] = latest time you can depart from i to reach j by time T
            int best[N];
            fill(best, best + N, NEG_INF);
            best[j] = T;

            // Max-heap: (available_time_at_city, city)
            priority_queue<pair<int,int>> pq;
            pq.push({T, j});

            while (!pq.empty()) {
                auto [arr_time, city] = pq.top();
                pq.pop();

                if (arr_time < best[city]) continue;

                // Look at all flights arriving at 'city' with arrive_time <= arr_time
                for (auto& [from, dep, arr] : rev_adj[city]) {
                    if (arr > arr_time) continue;
                    if (arr < TIME_MIN) break; // sorted descending, so no more valid
                    // We can take this flight: depart from 'from' at time 'dep'
                    if (dep > best[from]) {
                        best[from] = dep;
                        pq.push({dep, from});
                    }
                }
            }

            for (int i = 0; i < N; i++) {
                s_sq[i][j][t_idx] = best[i];
            }
        }
    }
}

// Circle Airlines schedule
struct Flight {
    int from, to, depart, arrive; // 0-indexed cities, times in minutes
};

struct Airplane {
    vector<Flight> flights;
};

// Compute s_ci[i][j][t_idx] given Circle Airlines schedule
// Returns total score
long long evaluate(const vector<Airplane>& planes, bool compute_s_ci = false,
                   vector<vector<vector<int>>>* out_s_ci = nullptr) {
    // Build Circle adjacency
    vector<vector<tuple<int,int,int>>> ci_rev_adj(N);
    for (auto& plane : planes) {
        for (auto& f : plane.flights) {
            ci_rev_adj[f.to].emplace_back(f.from, f.depart, f.arrive);
        }
    }
    for (int b = 0; b < N; b++) {
        sort(ci_rev_adj[b].begin(), ci_rev_adj[b].end(), [](auto& a, auto& b) {
            return get<2>(a) > get<2>(b);
        });
    }

    long long v_ci = 0, v_sq = 0;

    for (int t_idx = 0; t_idx < NUM_TARGETS; t_idx++) {
        int T = target_times[t_idx];
        for (int j = 0; j < N; j++) {
            int best[N];
            fill(best, best + N, NEG_INF);
            best[j] = T;

            priority_queue<pair<int,int>> pq;
            pq.push({T, j});

            while (!pq.empty()) {
                auto [arr_time, city] = pq.top();
                pq.pop();
                if (arr_time < best[city]) continue;

                for (auto& [from, dep, arr] : ci_rev_adj[city]) {
                    if (arr > arr_time) continue;
                    if (dep > best[from]) {
                        best[from] = dep;
                        pq.push({dep, from});
                    }
                }
            }

            for (int i = 0; i < N; i++) {
                if (!valid_pair[i][j]) continue;
                int sci = best[i];
                int ssq = s_sq[i][j][t_idx];
                long long w = (long long)cw[i] * cw[j];
                if (sci > ssq) {
                    v_ci += w;
                } else {
                    v_sq += w;
                }
            }

            if (compute_s_ci && out_s_ci) {
                for (int i = 0; i < N; i++) {
                    (*out_s_ci)[i][j][t_idx] = best[i];
                }
            }
        }
    }

    return v_ci; // return v_ci; total = v_ci + v_sq, share = v_ci / total
}

// Quick incremental evaluation: only recompute affected destinations
// For efficiency during SA, we do full evaluation but optimize later if needed

bool is_valid_schedule(const Airplane& plane) {
    for (int j = 0; j < (int)plane.flights.size(); j++) {
        auto& f = plane.flights[j];
        if (f.from < 0 || f.from >= N || f.to < 0 || f.to >= N) return false;
        if (f.from == f.to) return false;
        if (f.depart < TIME_MIN || f.arrive > TIME_MAX) return false;
        if (f.depart % 5 != 0 || f.arrive % 5 != 0) return false;
        if (f.arrive - f.depart != flight_time[f.from][f.to]) return false;
        if (j > 0) {
            if (plane.flights[j-1].to != f.from) return false;
            if (plane.flights[j-1].arrive > f.depart) return false;
        }
    }
    return true;
}

// Build a route for one airplane: visit a sequence of cities with given start time
vector<Flight> build_route(const vector<int>& cities, int start_time) {
    vector<Flight> flights;
    int cur_time = start_time;
    for (int i = 0; i + 1 < (int)cities.size(); i++) {
        int from = cities[i], to = cities[i+1];
        if (from == to) continue;
        int ft = flight_time[from][to];
        // Round cur_time up to next 5-minute slot
        int dep = ((cur_time + 4) / 5) * 5;
        int arr = dep + ft;
        if (arr > TIME_MAX) break;
        if (dep < TIME_MIN) dep = TIME_MIN;
        arr = dep + ft;
        if (arr > TIME_MAX) break;
        flights.push_back({from, to, dep, arr});
        cur_time = arr;
    }
    return flights;
}

// Initial solution: hub-and-spoke from top cities
vector<Airplane> build_initial_solution() {
    vector<Airplane> planes(K);

    // Sort cities by population (already sorted in input, city 0 is largest)
    // Pick top cities as important destinations
    // Strategy: each plane does shuttle routes between city pairs
    // covering as many high-weight pairs as possible

    // Get top ~15 cities by population
    vector<int> top_cities;
    for (int i = 0; i < min(N, 20); i++) top_cities.push_back(i);

    // Hub city = city 0 (highest population)
    int hub = 1; // 0-indexed city 1 (second highest pop) - actually let's use 0
    // Try: each plane shuttles between hub and a spoke city

    // Important pairs by weight
    vector<tuple<long long, int, int>> pairs;
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            if (valid_pair[i][j]) {
                long long w = (long long)cw[i] * cw[j];
                pairs.push_back({w, i, j});
            }
        }
    }
    sort(pairs.rbegin(), pairs.rend());

    // Strategy: for each plane, create a route that visits many cities
    // covering high-weight pairs efficiently
    // Simple approach: each plane does a chain of flights visiting different cities
    // starting from different times to cover the time range

    // Better strategy: hub-and-spoke
    // Plane k: hub -> spoke_k -> hub -> spoke_k -> hub -> ...
    // This creates many connections through the hub

    // Select spoke cities: top cities excluding hub
    vector<int> spokes;
    for (int i = 0; i < N && (int)spokes.size() < K; i++) {
        if (i != 0) spokes.push_back(i); // 0-indexed, so city 0 = hub
    }

    // Each plane assigned to one spoke
    for (int k = 0; k < K; k++) {
        int spoke = spokes[k % spokes.size()];
        vector<int> route;

        // Start time staggered
        int base_start = TIME_MIN + (k * 30) % 180; // stagger by 30min, wrap at 3hr

        int cur_time = base_start;
        int cur_city = 0; // start from hub
        bool at_hub = true;

        route.push_back(cur_city);
        while (cur_time + flight_time[cur_city][at_hub ? spoke : 0] <= TIME_MAX) {
            int next = at_hub ? spoke : 0;
            route.push_back(next);
            cur_time += flight_time[cur_city][next];
            cur_city = next;
            at_hub = !at_hub;
        }

        planes[k].flights = build_route(route, base_start);
    }

    return planes;
}

// Build initial solution v2: greedily assign planes to cover high-weight pairs
vector<Airplane> build_initial_solution_v2() {
    vector<Airplane> planes(K);

    // Important pairs by weight
    vector<tuple<long long, int, int>> pairs;
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            if (valid_pair[i][j]) {
                long long w = 2LL * cw[i] * cw[j]; // both directions
                pairs.push_back({w, i, j});
            }
        }
    }
    sort(pairs.rbegin(), pairs.rend());

    // For each plane, create a tour visiting several top cities
    // Different starting cities and times for diversity

    // Create city visit sequences
    // Top 10 cities: 0,1,2,3,4,5,6,7,8,9
    // Each plane gets a circular tour through a subset

    // Strategy: divide day into time bands, assign planes to cover different bands
    // Each plane: chain of flights visiting top cities

    for (int k = 0; k < K; k++) {
        // Pick a starting city and a set of cities to visit
        int start_city;
        vector<int> visit_order;

        if (k < 15) {
            // Hub-spoke: shuttle between city 0 and a spoke
            int spoke = (k % 15) + 1; // cities 1-15
            start_city = 0;
            int base_start = TIME_MIN + ((k / 15) * 150 + (k % 15) * 10);
            if (base_start > TIME_MAX - 200) base_start = TIME_MIN + (k * 7) % 120;

            vector<int> route;
            int cur = start_city;
            int ct = base_start;
            route.push_back(cur);

            while (true) {
                int next = (cur == 0) ? spoke : 0;
                int ft = flight_time[cur][next];
                if (ct + ft > TIME_MAX) break;
                route.push_back(next);
                ct += ft;
                cur = next;
            }
            planes[k].flights = build_route(route, base_start);
        } else {
            // Chain tour through top cities
            int group = k - 15;
            int base_start = TIME_MIN + group * 60;
            if (base_start > TIME_MAX - 300) base_start = TIME_MIN;

            // Visit sequence: cycle through some cities
            vector<int> cities_to_visit;
            for (int i = 0; i < 8; i++) {
                cities_to_visit.push_back((group * 3 + i * 2) % 20);
            }

            vector<int> route;
            route.push_back(cities_to_visit[0]);
            for (int i = 1; i < (int)cities_to_visit.size(); i++) {
                if (cities_to_visit[i] != route.back()) {
                    route.push_back(cities_to_visit[i]);
                }
            }

            planes[k].flights = build_route(route, base_start);
        }
    }

    return planes;
}

// Improved initial solution: multi-hub approach
vector<Airplane> build_initial_solution_v3() {
    vector<Airplane> planes(K);

    // Hub-spoke with multiple hubs for better coverage
    // Hub 0 (city 0): planes 0-7 (8 planes)
    // Hub 1 (city 1): planes 8-14 (7 planes)
    // Hub 2 (city 2): planes 15-19 (5 planes)
    // Touring: planes 20-24 (5 planes)

    // For hub planes, shuttle to different spoke cities at staggered times
    auto make_hub_shuttle = [&](int hub, int spoke, int start_time) -> vector<Flight> {
        vector<int> route;
        int cur = hub;
        int ct = start_time;
        route.push_back(cur);

        while (true) {
            int next = (cur == hub) ? spoke : hub;
            int ft = flight_time[cur][next];
            int dep = ((ct + 4) / 5) * 5;
            if (dep + ft > TIME_MAX) break;
            route.push_back(next);
            ct = dep + ft;
            cur = next;
        }
        return build_route(route, start_time);
    };

    // Hub 0 spokes: top importance cities
    vector<int> hub0_spokes = {1, 2, 3, 4, 5, 6, 7, 8};
    for (int k = 0; k < 8; k++) {
        int spoke = hub0_spokes[k];
        int start = TIME_MIN + k * 20;
        planes[k].flights = make_hub_shuttle(0, spoke, start);
    }

    // Hub 1 spokes
    vector<int> hub1_spokes = {0, 2, 3, 4, 5, 6, 7};
    for (int k = 8; k < 15; k++) {
        int spoke = hub1_spokes[k - 8];
        int start = TIME_MIN + (k - 8) * 25;
        planes[k].flights = make_hub_shuttle(1, spoke, start);
    }

    // Hub 2 spokes
    vector<int> hub2_spokes = {0, 1, 3, 4, 5};
    for (int k = 15; k < 20; k++) {
        int spoke = hub2_spokes[k - 15];
        int start = TIME_MIN + (k - 15) * 30;
        planes[k].flights = make_hub_shuttle(2, spoke, start);
    }

    // Touring planes: visit sequences of cities
    for (int k = 20; k < K; k++) {
        int group = k - 20;
        vector<int> tour;
        // Create different tours for each plane
        int offset = group * 5;
        for (int i = 0; i < 10; i++) {
            tour.push_back((offset + i * 3) % N);
        }
        // Remove consecutive duplicates
        vector<int> route;
        route.push_back(tour[0]);
        for (int i = 1; i < (int)tour.size(); i++) {
            if (tour[i] != route.back()) route.push_back(tour[i]);
        }
        planes[k].flights = build_route(route, TIME_MIN + group * 40);
    }

    return planes;
}

// Simulated annealing
void simulated_annealing(vector<Airplane>& planes, double time_limit_sec) {
    auto start = chrono::steady_clock::now();

    long long cur_score = evaluate(planes);
    long long best_score = cur_score;
    vector<Airplane> best_planes = planes;

    int iter = 0;
    int accept_count = 0;

    auto elapsed = [&]() -> double {
        auto now = chrono::steady_clock::now();
        return chrono::duration<double>(now - start).count();
    };

    double T_start = 1e14;
    double T_end = 1e10;

    while (true) {
        double t = elapsed();
        if (t >= time_limit_sec) break;

        double progress = t / time_limit_sec;
        double T = T_start * pow(T_end / T_start, progress);

        iter++;

        // Choose operation
        int op = rng() % 100;
        int plane_idx = rng() % K;
        Airplane old_plane = planes[plane_idx];

        if (op < 40) {
            // Operation 1: Change a spoke city in a hub-spoke route
            auto& flights = planes[plane_idx].flights;
            if (flights.empty()) continue;

            // Pick a random flight and change destination
            int fi = rng() % flights.size();
            int new_city = rng() % N;
            if (new_city == flights[fi].from) continue;

            // Rebuild the rest of the route from this flight
            vector<int> route;
            for (int i = 0; i <= fi; i++) {
                if (i == 0) route.push_back(flights[i].from);
                if (i < fi) route.push_back(flights[i].to);
            }
            route.push_back(new_city);

            // Continue with alternating pattern or random cities
            int cur = new_city;
            int ct = route.size() > 1 ? flights[fi].depart : TIME_MIN;
            // Estimate arrival at new_city
            int ft_to_new = flight_time[flights[fi].from][new_city];
            int dep_new = flights[fi].depart;
            int arr_new = dep_new + ft_to_new;
            if (arr_new > TIME_MAX) {
                planes[plane_idx] = old_plane;
                continue;
            }

            // Add more flights after new_city
            ct = arr_new;
            // Try to go back to a hub (city 0 or 1 or 2)
            for (int tries = 0; tries < 10; tries++) {
                int next = rng() % min(N, 20);
                if (next == cur) continue;
                int ft = flight_time[cur][next];
                int dep = ((ct + 4) / 5) * 5;
                if (dep + ft > TIME_MAX) break;
                route.push_back(next);
                ct = dep + ft;
                cur = next;
            }

            int start_time = flights.empty() ? TIME_MIN : flights[0].depart;
            if (fi == 0) {
                start_time = flights[0].depart;
            }
            planes[plane_idx].flights = build_route(route, start_time);
        } else if (op < 60) {
            // Operation 2: Shift entire schedule by +-5 to +-15 minutes
            int shift = ((int)(rng() % 7) - 3) * 5; // -15 to +15
            if (shift == 0) continue;

            bool ok = true;
            for (auto& f : planes[plane_idx].flights) {
                f.depart += shift;
                f.arrive += shift;
                if (f.depart < TIME_MIN || f.arrive > TIME_MAX) {
                    ok = false;
                    break;
                }
            }
            if (!ok) {
                planes[plane_idx] = old_plane;
                continue;
            }
        } else if (op < 80) {
            // Operation 3: Completely rebuild one plane's route
            auto& flights = planes[plane_idx].flights;

            // Pick random start city and time
            int start_city = rng() % min(N, 25);
            int start_time = TIME_MIN + (rng() % 36) * 5; // random 5-min slot in first 3 hours

            vector<int> route;
            route.push_back(start_city);
            int cur = start_city;
            int ct = start_time;

            // Greedily add cities
            for (int tries = 0; tries < 15; tries++) {
                // Pick a random city from top 25 or all
                int next;
                if (rng() % 3 == 0) {
                    next = rng() % N; // any city
                } else {
                    next = rng() % min(N, 20); // top cities
                }
                if (next == cur) continue;
                int ft = flight_time[cur][next];
                int dep = ((ct + 4) / 5) * 5;
                if (dep + ft > TIME_MAX) continue;
                route.push_back(next);
                ct = dep + ft;
                cur = next;
            }

            planes[plane_idx].flights = build_route(route, start_time);
        } else {
            // Operation 4: Swap two planes' routes or swap a segment
            int other = rng() % K;
            if (other == plane_idx) continue;
            swap(planes[plane_idx], planes[other]);
            // This doesn't change score, skip evaluation
            continue;
        }

        // Evaluate
        long long new_score = evaluate(planes);
        long long delta = new_score - cur_score;

        if (delta > 0 || (T > 0 && exp((double)delta / T) > (double)(rng() % 1000000) / 1000000.0)) {
            cur_score = new_score;
            accept_count++;
            if (cur_score > best_score) {
                best_score = cur_score;
                best_planes = planes;
            }
        } else {
            planes[plane_idx] = old_plane;
        }
    }

    planes = best_planes;
    fprintf(stderr, "SA: iter=%d, accept=%d, best_score=%lld\n", iter, accept_count, best_score);
}

// Fast evaluation: only compute a partial score for a single plane change
// This caches Circle Airlines adjacency and only updates for the changed plane
struct FastEvaluator {
    vector<Airplane>* planes;
    // All circle flights combined
    vector<tuple<int,int,int>> ci_rev_adj[N]; // (from, depart, arrive)

    long long total_v_ci, total_v_sq;

    void init(vector<Airplane>* p) {
        planes = p;
        rebuild_all();
    }

    void rebuild_all() {
        for (int i = 0; i < N; i++) ci_rev_adj[i].clear();
        for (auto& plane : *planes) {
            for (auto& f : plane.flights) {
                ci_rev_adj[f.to].emplace_back(f.from, f.depart, f.arrive);
            }
        }
        for (int i = 0; i < N; i++) {
            sort(ci_rev_adj[i].begin(), ci_rev_adj[i].end(), [](auto& a, auto& b) {
                return get<2>(a) > get<2>(b);
            });
        }
    }

    long long compute_score() {
        long long v_ci = 0, v_sq = 0;

        for (int t_idx = 0; t_idx < NUM_TARGETS; t_idx++) {
            int T = target_times[t_idx];
            for (int j = 0; j < N; j++) {
                int best[N];
                fill(best, best + N, NEG_INF);
                best[j] = T;

                priority_queue<pair<int,int>> pq;
                pq.push({T, j});

                while (!pq.empty()) {
                    auto [arr_time, city] = pq.top();
                    pq.pop();
                    if (arr_time < best[city]) continue;

                    for (auto& [from, dep, arr] : ci_rev_adj[city]) {
                        if (arr > arr_time) continue;
                        if (dep > best[from]) {
                            best[from] = dep;
                            pq.push({dep, from});
                        }
                    }
                }

                for (int i = 0; i < N; i++) {
                    if (!valid_pair[i][j]) continue;
                    int sci = best[i];
                    int ssq = s_sq[i][j][t_idx];
                    long long w = (long long)cw[i] * cw[j];
                    if (sci > ssq) {
                        v_ci += w;
                    } else {
                        v_sq += w;
                    }
                }
            }
        }

        total_v_ci = v_ci;
        total_v_sq = v_sq;
        return v_ci;
    }
};

// Improved SA with fast evaluator
void simulated_annealing_v2(vector<Airplane>& planes, double time_limit_sec) {
    auto start = chrono::steady_clock::now();

    FastEvaluator eval;
    eval.init(&planes);
    long long cur_score = eval.compute_score();
    long long best_score = cur_score;
    vector<Airplane> best_planes = planes;

    int iter = 0;
    int accept_count = 0;

    auto elapsed = [&]() -> double {
        auto now = chrono::steady_clock::now();
        return chrono::duration<double>(now - start).count();
    };

    double T_start = 5e13;
    double T_end = 1e10;

    while (true) {
        double t = elapsed();
        if (t >= time_limit_sec) break;

        double progress = t / time_limit_sec;
        double T = T_start * pow(T_end / T_start, progress);

        iter++;

        int plane_idx = rng() % K;
        Airplane old_plane = planes[plane_idx];

        int op = rng() % 100;

        if (op < 35) {
            // Rebuild route: random chain through important cities
            int start_city;
            if (rng() % 2 == 0) {
                start_city = rng() % 3; // top 3 cities
            } else {
                start_city = rng() % min(N, 15);
            }
            int start_time = TIME_MIN + (rng() % 60) * 5;

            vector<int> route;
            route.push_back(start_city);
            int cur = start_city;
            int ct = start_time;

            for (int tries = 0; tries < 20; tries++) {
                int next;
                int r = rng() % 10;
                if (r < 4) next = rng() % 3;      // top 3
                else if (r < 7) next = rng() % 10; // top 10
                else if (r < 9) next = rng() % 20; // top 20
                else next = rng() % N;             // any

                if (next == cur) continue;
                int ft = flight_time[cur][next];
                int dep = ((ct + 4) / 5) * 5;
                if (dep + ft > TIME_MAX) continue;
                route.push_back(next);
                ct = dep + ft;
                cur = next;
            }

            planes[plane_idx].flights = build_route(route, start_time);
        } else if (op < 55) {
            // Shift time +-5 to +-20 minutes
            int shift = ((int)(rng() % 9) - 4) * 5;
            if (shift == 0) shift = 5;

            bool ok = true;
            for (auto& f : planes[plane_idx].flights) {
                f.depart += shift;
                f.arrive += shift;
                if (f.depart < TIME_MIN || f.arrive > TIME_MAX) { ok = false; break; }
            }
            if (!ok) {
                planes[plane_idx] = old_plane;
                continue;
            }
        } else if (op < 75) {
            // Modify one flight's destination
            auto& flights = planes[plane_idx].flights;
            if (flights.size() < 2) {
                // Rebuild instead
                int start_city = rng() % 10;
                int start_time = TIME_MIN + (rng() % 60) * 5;
                vector<int> route = {start_city};
                int cur = start_city;
                int ct = start_time;
                for (int tries = 0; tries < 15; tries++) {
                    int next = rng() % min(N, 20);
                    if (next == cur) continue;
                    int ft = flight_time[cur][next];
                    int dep = ((ct + 4) / 5) * 5;
                    if (dep + ft > TIME_MAX) continue;
                    route.push_back(next);
                    ct = dep + ft;
                    cur = next;
                }
                planes[plane_idx].flights = build_route(route, start_time);
            } else {
                // Pick a random split point and rebuild from there
                int split = 1 + rng() % ((int)flights.size() - 1);
                int cur = flights[split - 1].to;
                int ct = flights[split - 1].arrive;

                // Keep flights before split
                vector<Flight> new_flights(flights.begin(), flights.begin() + split);

                // Rebuild from split point
                for (int tries = 0; tries < 15; tries++) {
                    int next;
                    int r = rng() % 10;
                    if (r < 4) next = rng() % 3;
                    else if (r < 7) next = rng() % 10;
                    else next = rng() % N;

                    if (next == cur) continue;
                    int ft = flight_time[cur][next];
                    int dep = ((ct + 4) / 5) * 5;
                    if (dep + ft > TIME_MAX) break;
                    new_flights.push_back({cur, next, dep, dep + ft});
                    ct = dep + ft;
                    cur = next;
                }
                planes[plane_idx].flights = new_flights;
            }
        } else {
            // Hub-spoke shuttle rebuild
            int hub, spoke;
            if (rng() % 2 == 0) {
                hub = 0;
                spoke = 1 + rng() % (N - 1);
            } else {
                hub = rng() % 3;
                spoke = rng() % N;
                if (spoke == hub) continue;
            }

            int start_time = TIME_MIN + (rng() % 72) * 5; // 0 to 6 hours offset

            vector<int> route;
            int cur = hub;
            int ct = start_time;
            route.push_back(cur);

            while (true) {
                int next = (cur == hub) ? spoke : hub;
                int ft = flight_time[cur][next];
                int dep = ((ct + 4) / 5) * 5;
                if (dep + ft > TIME_MAX) break;
                route.push_back(next);
                ct = dep + ft;
                cur = next;
            }

            planes[plane_idx].flights = build_route(route, start_time);
        }

        // Validate
        if (!is_valid_schedule(planes[plane_idx])) {
            planes[plane_idx] = old_plane;
            continue;
        }

        // Evaluate
        eval.rebuild_all();
        long long new_score = eval.compute_score();
        long long delta = new_score - cur_score;

        if (delta > 0 || (T > 0 && exp((double)delta / T) > (double)(rng() % 1000000) / 1000000.0)) {
            cur_score = new_score;
            accept_count++;
            if (cur_score > best_score) {
                best_score = cur_score;
                best_planes = planes;
            }
        } else {
            planes[plane_idx] = old_plane;
        }
    }

    planes = best_planes;
    fprintf(stderr, "SA v2: iter=%d, accept=%d, best_v_ci=%lld\n", iter, accept_count, best_score);
}

int main() {
    auto global_start = chrono::steady_clock::now();

    int n, r;
    scanf("%d %d", &n, &r);

    for (int i = 0; i < N; i++) {
        scanf("%d %d %d", &cx[i], &cy[i], &cw[i]);
    }

    // Compute distance and flight time tables
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) {
                dist_table[i][j] = 0;
                flight_time[i][j] = 0;
                valid_pair[i][j] = false;
            } else {
                double dx = cx[i] - cx[j], dy = cy[i] - cy[j];
                dist_table[i][j] = sqrt(dx*dx + dy*dy);
                flight_time[i][j] = calc_flight_time(dist_table[i][j]);
                valid_pair[i][j] = (dist_table[i][j] >= 250.0);
            }
        }
    }

    // Read Square flights
    int m;
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        char s_time[6], t_time[6];
        scanf("%d %5s %d %5s", &sq_a[i], s_time, &sq_b[i], t_time);
        sq_a[i]--; sq_b[i]--; // 0-indexed
        sq_s[i] = parse_time(s_time);
        sq_t[i] = parse_time(t_time);
    }

    int k;
    scanf("%d", &k);

    // Target arrival times
    for (int i = 0; i < NUM_TARGETS; i++) {
        target_times[i] = 660 + i * 30; // 11:00, 11:30, ..., 21:00
    }

    // Compute Square Airlines Dijkstra
    compute_square_dijkstra();

    auto after_precomp = chrono::steady_clock::now();
    double precomp_time = chrono::duration<double>(after_precomp - global_start).count();
    fprintf(stderr, "Precomputation done in %.3fs\n", precomp_time);

    // Build initial solution
    vector<Airplane> planes = build_initial_solution_v3();

    long long init_score = evaluate(planes);
    fprintf(stderr, "Initial score (v_ci): %lld\n", init_score);

    // Run SA with remaining time
    double total_time_limit = 0.90; // leave margin for output
    double sa_time = total_time_limit - precomp_time;
    if (sa_time > 0.05) {
        simulated_annealing_v2(planes, sa_time);
    }

    // Compute final score
    long long final_vci = evaluate(planes);

    // Count total weight for share calculation
    long long total_weight = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (valid_pair[i][j]) {
                total_weight += (long long)cw[i] * cw[j];
            }
        }
    }
    // total_weight counted per target time
    total_weight *= NUM_TARGETS;

    fprintf(stderr, "Final v_ci: %lld, total_weight: %lld\n", final_vci, total_weight);
    if (total_weight > 0) {
        fprintf(stderr, "Share: %.6f, Score: %lld\n",
                (double)final_vci / total_weight,
                (long long)((double)final_vci / total_weight * 1000000));
    }

    // Output
    for (int p = 0; p < K; p++) {
        printf("%d\n", (int)planes[p].flights.size());
        for (auto& f : planes[p].flights) {
            printf("%d %s %d %s\n",
                   f.from + 1, format_time(f.depart).c_str(),
                   f.to + 1, format_time(f.arrive).c_str());
        }
    }

    auto total_elapsed = chrono::duration<double>(chrono::steady_clock::now() - global_start).count();
    fprintf(stderr, "Total time: %.3fs\n", total_elapsed);

    return 0;
}