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

const int N = 47;
const int MF = 400;
const int K = 25;
const int TMIN = 360;
const int TMAX = 1260;
const int NT = 21;
const int NINF = -1000000;

int cx[N], cy[N], cw[N];
int sqa_[MF], sqb_[MF], sqs_[MF], sqt_[MF];
int ft[N][N];
bool vp[N][N];
int tgt[NT];
int ssq[N][N][NT];

mt19937 rng(42);
int top_hubs[N]; // cities ranked by hub potential (computed in best_greedy_init)
int sa_hubs[3]; // top 3 hub cities by population


int parse_time(const char* s) {
    return (s[0]-'0')*600 + (s[1]-'0')*60 + (s[3]-'0')*10 + (s[4]-'0');
}

string fmt(int t) {
    char b[6];
    b[0]='0'+t/600; t%=600; b[1]='0'+t/60; t%=60;
    b[2]=':'; b[3]='0'+t/10; b[4]='0'+t%10; b[5]=0;
    return string(b);
}

int cft(double d) {
    return ((int)ceil((60.0*d/800.0+40.0)/5.0))*5;
}

void compute_sq() {
    struct E { int arr, dep, from; };
    vector<E> rev[N];
    for (int i = 0; i < MF; i++)
        rev[sqb_[i]].push_back({sqt_[i], sqs_[i], sqa_[i]});
    for (int i = 0; i < N; i++)
        sort(rev[i].begin(), rev[i].end(), [](auto& a, auto& b){ return a.arr > b.arr; });

    for (int ti = 0; ti < NT; ti++) {
        int T = tgt[ti];
        for (int j = 0; j < N; j++) {
            int best[N]; fill(best, best+N, NINF);
            best[j] = T;
            priority_queue<pair<int,int>> pq;
            pq.push({T, j});
            while (!pq.empty()) {
                auto [at, c] = pq.top(); pq.pop();
                if (at < best[c]) continue;
                for (auto& e : rev[c]) {
                    if (e.arr > at) continue;
                    if (e.dep > best[e.from]) {
                        best[e.from] = e.dep;
                        pq.push({e.dep, e.from});
                    }
                }
            }
            for (int i = 0; i < N; i++) ssq[i][j][ti] = best[i];
        }
    }
}

struct Flight { int from, to, dep, arr; };
struct Plane { vector<Flight> fs; };

vector<Flight> build(const vector<int>& cities, int start) {
    vector<Flight> fs;
    int ct = start;
    for (int i = 0; i+1 < (int)cities.size(); i++) {
        int a = cities[i], b = cities[i+1];
        if (a == b) continue;
        int d = ((ct+4)/5)*5;
        if (d < TMIN) d = TMIN;
        int ar = d + ft[a][b];
        if (ar > TMAX) break;
        fs.push_back({a, b, d, ar});
        ct = ar;
    }
    return fs;
}

bool valid(const Plane& p) {
    for (int j = 0; j < (int)p.fs.size(); j++) {
        auto& f = p.fs[j];
        if (f.from == f.to || f.dep < TMIN || f.arr > TMAX) return false;
        if (f.dep%5 || f.arr%5) return false;
        if (f.arr - f.dep != ft[f.from][f.to]) return false;
        if (j > 0 && (p.fs[j-1].to != f.from || p.fs[j-1].arr > f.dep)) return false;
    }
    return true;
}

// =========================================================
// BF-based evaluation
// =========================================================
struct CF { int from, to, dep, arr; };
CF sorted_flights[500];
int nf;
int plane_start[K+1]; // sorted_flights[plane_start[p]..plane_start[p+1]) belong to plane p

void collect_sorted(const vector<Plane>& planes) {
    nf = 0;
    for (auto& p : planes)
        for (auto& f : p.fs)
            sorted_flights[nf++] = {f.from, f.to, f.dep, f.arr};
    sort(sorted_flights, sorted_flights+nf, [](auto& a, auto& b){ return a.arr > b.arr; });
}

// Incremental update: remove old flights of plane pi, insert new ones
void update_sorted(int pi, const CF* removed, int nr, const CF* added, int na) {
    // Remove old flights: compact in-place
    int w = 0;
    for (int i = 0; i < nf; i++) {
        bool is_removed = false;
        for (int k = 0; k < nr; k++) {
            if (sorted_flights[i].from == removed[k].from &&
                sorted_flights[i].to == removed[k].to &&
                sorted_flights[i].dep == removed[k].dep &&
                sorted_flights[i].arr == removed[k].arr) {
                is_removed = true;
                // Mark as used to handle duplicates
                const_cast<CF&>(removed[k]).dep = -1;
                break;
            }
        }
        if (!is_removed) sorted_flights[w++] = sorted_flights[i];
    }
    nf = w;
    // Insert new flights maintaining arrival-desc sort order
    for (int k = 0; k < na; k++) {
        // Binary search for insertion point
        int lo = 0, hi = nf;
        while (lo < hi) {
            int mid = (lo+hi)/2;
            if (sorted_flights[mid].arr > added[k].arr) lo = mid+1;
            else hi = mid;
        }
        // Shift right
        for (int i = nf; i > lo; i--) sorted_flights[i] = sorted_flights[i-1];
        sorted_flights[lo] = added[k];
        nf++;
    }
}

int best_ci[NT][N][N];
long long spp[NT][N];

long long score_for(int j, int ti, const int* best) {
    long long s = 0;
    for (int i = 0; i < N; i++)
        if (vp[i][j] && best[i] > ssq[i][j][ti])
            s += (long long)cw[i]*cw[j];
    return s;
}

void bf_solve(int j, int ti, int* best_out) {
    fill(best_out, best_out+N, NINF);
    best_out[j] = tgt[ti];
    for (int round = 0; round < 8; round++) {
        bool changed = false;
        for (int fi = 0; fi < nf; fi++) {
            auto& f = sorted_flights[fi];
            if (f.arr <= best_out[f.to] && f.dep > best_out[f.from]) {
                best_out[f.from] = f.dep;
                changed = true;
            }
        }
        if (!changed) break;
    }
}

long long eval_full(const vector<Plane>& planes) {
    collect_sorted(planes);
    long long total = 0;
    for (int ti = 0; ti < NT; ti++) {
        for (int j = 0; j < N; j++) {
            bf_solve(j, ti, best_ci[ti][j]);
            spp[ti][j] = score_for(j, ti, best_ci[ti][j]);
            total += spp[ti][j];
        }
    }
    return total;
}

struct Change { int ti, j; int old_best[N]; long long old_spp; };
Change changes[NT*N];
int nchanges;

long long eval_incr(const vector<Plane>& planes, long long old_score) {
    collect_sorted(planes);
    long long total = old_score;
    nchanges = 0;
    int new_best[N];

    for (int ti = 0; ti < NT; ti++) {
        for (int j = 0; j < N; j++) {
            bf_solve(j, ti, new_best);
            if (memcmp(new_best, best_ci[ti][j], sizeof(int)*N) == 0) continue;
            Change& ch = changes[nchanges++];
            ch.ti = ti; ch.j = j;
            memcpy(ch.old_best, best_ci[ti][j], sizeof(int)*N);
            ch.old_spp = spp[ti][j];
            long long new_s = score_for(j, ti, new_best);
            total += new_s - spp[ti][j];
            spp[ti][j] = new_s;
            memcpy(best_ci[ti][j], new_best, sizeof(int)*N);
        }
    }
    return total;
}

// Partial eval for specific time slots only
long long eval_incr_partial(const vector<Plane>& planes, long long old_score,
                            const int* ti_list, int ti_cnt) {
    collect_sorted(planes);
    long long total = old_score;
    nchanges = 0;
    int new_best[N];

    for (int k = 0; k < ti_cnt; k++) {
        int ti = ti_list[k];
        for (int j = 0; j < N; j++) {
            bf_solve(j, ti, new_best);
            if (memcmp(new_best, best_ci[ti][j], sizeof(int)*N) == 0) continue;
            Change& ch = changes[nchanges++];
            ch.ti = ti; ch.j = j;
            memcpy(ch.old_best, best_ci[ti][j], sizeof(int)*N);
            ch.old_spp = spp[ti][j];
            long long new_s = score_for(j, ti, new_best);
            total += new_s - spp[ti][j];
            spp[ti][j] = new_s;
            memcpy(best_ci[ti][j], new_best, sizeof(int)*N);
        }
    }
    return total;
}

// Skip-based incremental eval: only re-run BF for (ti,j) pairs
// that might be affected by the changed flights
long long eval_incr_skip(const vector<Plane>& planes, long long old_score,
                         const int* ti_list, int ti_cnt,
                         const CF* removed, int nr,
                         const CF* added, int na) {
    collect_sorted(planes);
    long long total = old_score;
    nchanges = 0;
    int new_best[N];

    // Precompute min arrival time of any changed flight for time-window filter
    int min_arr = TMAX + 1;
    for (int k = 0; k < nr; k++) min_arr = min(min_arr, removed[k].arr);
    for (int k = 0; k < na; k++) min_arr = min(min_arr, added[k].arr);

    for (int k = 0; k < ti_cnt; k++) {
        int ti = ti_list[k];
        // Time-window filter: if all changed flights arrive after tgt[ti],
        // they cannot participate in any path for this ti
        if (min_arr > tgt[ti]) continue;

        for (int j = 0; j < N; j++) {
            // Per-flight impact check: can any removed/added flight affect (ti,j)?
            int* b = best_ci[ti][j];
            bool affected = false;

            // Check removed flights: was any potentially on the optimal path?
            for (int kk = 0; kk < nr && !affected; kk++) {
                auto& f = removed[kk];
                if (f.arr <= b[f.to] && f.dep >= b[f.from]) affected = true;
            }
            // Check added flights: could any improve the solution?
            for (int kk = 0; kk < na && !affected; kk++) {
                auto& f = added[kk];
                if (f.arr <= b[f.to] && f.dep > b[f.from]) affected = true;
            }
            if (!affected) continue;

            bf_solve(j, ti, new_best);
            if (memcmp(new_best, best_ci[ti][j], sizeof(int)*N) == 0) continue;
            Change& ch = changes[nchanges++];
            ch.ti = ti; ch.j = j;
            memcpy(ch.old_best, best_ci[ti][j], sizeof(int)*N);
            ch.old_spp = spp[ti][j];
            long long new_s = score_for(j, ti, new_best);
            total += new_s - spp[ti][j];
            spp[ti][j] = new_s;
            memcpy(best_ci[ti][j], new_best, sizeof(int)*N);
        }
    }
    return total;
}

void rollback() {
    for (int i = 0; i < nchanges; i++) {
        auto& ch = changes[i];
        memcpy(best_ci[ch.ti][ch.j], ch.old_best, sizeof(int)*N);
        spp[ch.ti][ch.j] = ch.old_spp;
    }
}

// =========================================================
// Greedy initial solution: backward construction
//
// Strategy: For each plane, build schedule from back to front.
// 1. Pick a "final destination" (high-population city)
// 2. Set deadline = TMAX (21:00)
// 3. Repeatedly prepend flights:
//    - For current position (city c, must depart by time t),
//      pick the source city a that maximizes score contribution
//      of the flight a->c arriving at or before t
//    - Update c = a, t = dep time of that flight
//    - Stop when we reach TMIN
// =========================================================

// Precomputed spoke rankings per hub
struct SpokeVal { int city; long long val; };
vector<SpokeVal> spoke_rank[N]; // spoke_rank[hub] = sorted list of (spoke, value)

void precompute_spoke_ranks() {
    for (int hub = 0; hub < N; hub++) {
        spoke_rank[hub].clear();
        for (int s = 0; s < N; s++) {
            if (s == hub) continue;
            long long val = 0;
            if (vp[hub][s]) {
                int fwd_time = ft[hub][s];
                int rev_time = ft[s][hub];
                for (int ti = 0; ti < NT; ti++) {
                    for (int arr = tgt[ti]; arr >= TMIN + fwd_time; arr -= 30) {
                        int dep = arr - fwd_time;
                        if (dep >= TMIN && dep > ssq[hub][s][ti]) {
                            val += (long long)cw[hub] * cw[s];
                            break;
                        }
                    }
                    for (int arr = tgt[ti]; arr >= TMIN + rev_time; arr -= 30) {
                        int dep = arr - rev_time;
                        if (dep >= TMIN && dep > ssq[s][hub][ti]) {
                            val += (long long)cw[s] * cw[hub];
                            break;
                        }
                    }
                }
            }
            // Always include for short-distance cities (even if !vp)
            // They're useful as transfer points
            val += (long long)cw[hub] * cw[s] / 100;
            spoke_rank[hub].push_back({s, val});
        }
        sort(spoke_rank[hub].begin(), spoke_rank[hub].end(),
             [](auto& a, auto& b){ return a.val > b.val; });
    }
}

// Backward greedy: build hub<->spoke shuttle from back to front
// hub_assign[K]: hub city for each plane
// stagger: time stagger per plane (in 5-min units)
void greedy_backward(vector<Plane>& planes, const int* hub_assign, int stagger) {
    for (int p = 0; p < K; p++) {
        int hub = hub_assign[p];
        auto& sr = spoke_rank[hub];

        // Pick spoke: distribute among planes with same hub
        int hub_idx = 0;
        for (int q = 0; q < p; q++) if (hub_assign[q] == hub) hub_idx++;
        int spoke = sr[hub_idx % min((int)sr.size(), 15)].city;

        // Build backward
        vector<Flight> fs;
        int cur_city = hub;
        int cur_deadline = TMAX - (p % stagger) * 5;
        if (cur_deadline < TMIN + 60) cur_deadline = TMAX;

        for (int step = 0; step < 20; step++) {
            int next_city = (cur_city == hub) ? spoke : hub;
            int flight_time = ft[next_city][cur_city];
            int arr = (cur_deadline / 5) * 5;
            if (arr > TMAX) arr = TMAX;
            int dep = arr - flight_time;
            if (dep < TMIN) break;
            dep = (dep / 5) * 5;
            arr = dep + flight_time;
            if (arr > cur_deadline || arr > TMAX) break;
            fs.push_back({next_city, cur_city, dep, arr});
            cur_city = next_city;
            cur_deadline = dep;
        }
        reverse(fs.begin(), fs.end());
        planes[p].fs = fs;
    }
}

// Generate multiple hub assignment patterns and pick the best
void best_greedy_init(vector<Plane>& planes) {
    precompute_spoke_ranks();

    // Rank cities by hub potential (sum of spoke values)
    vector<pair<long long,int>> hub_potential(N);
    for (int h = 0; h < N; h++) {
        long long total = 0;
        for (auto& sv : spoke_rank[h]) total += sv.val;
        hub_potential[h] = {total, h};
    }
    sort(hub_potential.rbegin(), hub_potential.rend());
    for (int i = 0; i < N; i++) top_hubs[i] = hub_potential[i].second;
    // Distribution patterns: {hub_rank, plane_count}[]
    // Use hub ranks (0=best, 1=2nd best, etc.)
    struct HubPattern {
        vector<pair<int,int>> hub_ranks; // (hub_rank, count)
        int stagger;
    };

    vector<HubPattern> patterns = {
        {{{0,15},{1,5},{2,5}}, 5},
        {{{0,15},{1,5},{2,5}}, 3},
        {{{0,17},{1,4},{2,4}}, 4},
        {{{0,14},{1,6},{2,5}}, 5},
        {{{0,10},{1,8},{2,7}}, 5},
        {{{0,9},{1,8},{2,8}}, 5},
        {{{0,25}}, 5},
        {{{0,18},{1,7}}, 5},
    };

    long long best_score = -1;
    vector<Plane> best_result(K);

    for (auto& pat : patterns) {
        int ha[K];
        int idx = 0;
        for (auto& [hr, cnt] : pat.hub_ranks) {
            int city = top_hubs[hr];
            for (int i = 0; i < cnt && idx < K; i++) ha[idx++] = city;
        }
        while (idx < K) ha[idx++] = top_hubs[0];

        vector<Plane> trial(K);
        greedy_backward(trial, ha, pat.stagger);

        long long score = eval_full(trial);
        if (score > best_score) {
            best_score = score;
            best_result = trial;
        }
    }


    planes = best_result;
}

// =========================================================
// Phase-based SA evaluation
// =========================================================
int phase_ti[3][NT];
int phase_nt[3];
double phase_scale[3];

void init_phases() {
    // Phase 0: every 3rd slot (7 slots)
    phase_nt[0] = 0;
    for (int i = 0; i < NT; i += 3) phase_ti[0][phase_nt[0]++] = i;
    phase_scale[0] = (double)NT / phase_nt[0];

    // Phase 1: every 2nd slot (11 slots)
    phase_nt[1] = 0;
    for (int i = 0; i < NT; i += 2) phase_ti[1][phase_nt[1]++] = i;
    phase_scale[1] = (double)NT / phase_nt[1];

    // Phase 2: all slots (21 slots)
    phase_nt[2] = NT;
    for (int i = 0; i < NT; i++) phase_ti[2][i] = i;
    phase_scale[2] = 1.0;
}

int main() {
    auto t0 = chrono::steady_clock::now();
    auto el = [&]() { return chrono::duration<double>(chrono::steady_clock::now()-t0).count(); };

    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]);

    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        if (i == j) { ft[i][j] = 0; vp[i][j] = false; continue; }
        double dx = cx[i]-cx[j], dy = cy[i]-cy[j];
        double d = sqrt(dx*dx+dy*dy);
        ft[i][j] = cft(d);
        vp[i][j] = d >= 250.0;
    }

    int m; scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        char s1[6], s2[6];
        scanf("%d%5s%d%5s", &sqa_[i], s1, &sqb_[i], s2);
        sqa_[i]--; sqb_[i]--;
        sqs_[i] = parse_time(s1);
        sqt_[i] = parse_time(s2);
    }
    int k; scanf("%d", &k);
    for (int i = 0; i < NT; i++) tgt[i] = 660 + i*30;

    compute_sq();

    long long tw = 0;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
        if (vp[i][j]) tw += (long long)cw[i]*cw[j];
    tw *= NT;

    // Setup SA hubs: top 3 by population
    {
        vector<pair<int,int>> by_w(N);
        for (int i = 0; i < N; i++) by_w[i] = {-cw[i], i};
        sort(by_w.begin(), by_w.end());
        for (int i = 0; i < 3; i++) sa_hubs[i] = by_w[i].second;
    }

    init_phases();
    fprintf(stderr, "Precomp: %.3fs\n", el());

    // =========================================================
    // Initial solution: try both greedy and hub-spoke, pick better
    // =========================================================
    vector<Plane> planes(K);

    auto shuttle = [](int hub, int spoke, int start) -> vector<Flight> {
        vector<int> route;
        int cur = hub, ct = start;
        route.push_back(cur);
        while (true) {
            int next = (cur==hub)?spoke:hub;
            int d = ((ct+4)/5)*5;
            if (d < TMIN) d = TMIN;
            if (d+ft[cur][next] > TMAX) break;
            route.push_back(next);
            ct = d+ft[cur][next];
            cur = next;
        }
        return build(route, start);
    };

    // Option A: original hub-spoke
    vector<Plane> planes_hs(K);
    {
        int asgn[][2] = {
            {0,1},{0,2},{0,3},{0,4},{0,5},{0,6},{0,7},{0,8},
            {1,0},{1,2},{1,3},{1,4},{1,5},{1,6},
            {2,0},{2,1},{2,3},{2,4},{2,5},
            {0,9},{0,10},{0,11},{0,12},{0,13},{0,14}
        };
        for (int i = 0; i < K; i++)
            planes_hs[i].fs = shuttle(asgn[i][0], asgn[i][1], TMIN + i*12);
    }
    long long score_hs = eval_full(planes_hs);
    fprintf(stderr, "Hub-spoke init: %lld share=%.4f (%.3fs)\n", score_hs, (double)score_hs/tw, el());

    // Option B: best of multiple greedy backward patterns
    vector<Plane> planes_gr(K);
    best_greedy_init(planes_gr);
    long long score_gr = eval_full(planes_gr);
    fprintf(stderr, "Best greedy init: %lld share=%.4f (%.3fs)\n", score_gr, (double)score_gr/tw, el());

    // Pick the better one
    if (score_gr > score_hs) {
        planes = planes_gr;
        fprintf(stderr, "Using greedy init\n");
    } else {
        planes = planes_hs;
        fprintf(stderr, "Using hub-spoke init\n");
    }

    long long cur = eval_full(planes);
    long long best = cur;
    vector<Plane> best_p = planes;
    fprintf(stderr, "Init: %lld share=%.4f (%.3fs)\n", cur, (double)cur/tw, el());

    // =========================================================
    // SA with phased precision
    // =========================================================
    const double phase_boundary[2] = {0.35, 0.70};
    const double sa_lim = 0.90;

    int cur_phase = 0;
    // Compute partial score for current phase from cache
    long long cur_partial = 0;
    for (int k2 = 0; k2 < phase_nt[cur_phase]; k2++) {
        int ti = phase_ti[cur_phase][k2];
        for (int j = 0; j < N; j++) cur_partial += spp[ti][j];
    }

    double Ts_base = 3e13, Te_base = 1e9;
    int it = 0, ac = 0;
    int phase_its[3] = {0, 0, 0};

    while (el() < sa_lim) {
        double t_now = el();
        double prog = t_now / sa_lim;
        double sc = phase_scale[cur_phase];
        double Ts_eff = Ts_base / sc, Te_eff = Te_base / sc;
        double T = Ts_eff * pow(Te_eff/Ts_eff, prog);

        // Phase transition
        int new_phase = (prog < phase_boundary[0]) ? 0 :
                        (prog < phase_boundary[1]) ? 1 : 2;
        if (new_phase != cur_phase) {
            cur_phase = new_phase;
            eval_full(planes);
            cur_partial = 0;
            for (int k2 = 0; k2 < phase_nt[cur_phase]; k2++) {
                int ti = phase_ti[cur_phase][k2];
                for (int j = 0; j < N; j++) cur_partial += spp[ti][j];
            }
            long long full_now = 0;
            for (int ti = 0; ti < NT; ti++)
                for (int j = 0; j < N; j++) full_now += spp[ti][j];
            if (full_now > best) { best = full_now; best_p = planes; }
        }

        it++;
        phase_its[cur_phase]++;

        int pi = rng() % K;
        Plane old = planes[pi];
        int op = rng() % 100;

        if (op < 40) {
            int hub, spoke;
            int r2 = rng()%10;
            hub = sa_hubs[(r2<5)?0:(r2<8)?1:2];
            spoke = rng()%N;
            if (spoke == hub) spoke = (hub+1+rng()%(N-1))%N;
            int start = TMIN + (rng()%72)*5;
            planes[pi].fs = shuttle(hub, spoke, start);
        } else if (op < 60) {
            int shift = ((int)(rng()%9)-4)*5;
            if (!shift) shift = 5;
            bool ok = true;
            for (auto& f : planes[pi].fs) {
                f.dep += shift; f.arr += shift;
                if (f.dep < TMIN || f.arr > TMAX) { ok = false; break; }
            }
            if (!ok) { planes[pi] = old; continue; }
        } else if (op < 80) {
            int sc2; int r2=rng()%10;
            sc2 = (r2<4)?rng()%3:(r2<7)?rng()%10:rng()%N;
            int start = TMIN + (rng()%72)*5;
            vector<int> route = {sc2};
            int c = sc2, ct = start;
            for (int t = 0; t < 15; t++) {
                int nx; int r3=rng()%10;
                nx = (r3<3)?rng()%3:(r3<6)?rng()%10:(r3<8)?rng()%20:rng()%N;
                if (nx == c) continue;
                int d = ((ct+4)/5)*5;
                if (d < TMIN) d = TMIN;
                if (d+ft[c][nx] > TMAX) continue;
                route.push_back(nx);
                ct = d+ft[c][nx];
                c = nx;
            }
            planes[pi].fs = build(route, start);
        } else {
            auto& fs = planes[pi].fs;
            if (fs.size() < 2) { planes[pi] = old; continue; }
            int split = 1+rng()%((int)fs.size()-1);
            int c = fs[split-1].to, ct = fs[split-1].arr;
            vector<Flight> nfs(fs.begin(), fs.begin()+split);
            for (int t = 0; t < 10; t++) {
                int nx; int r3=rng()%10;
                nx = (r3<3)?rng()%3:(r3<6)?rng()%10:rng()%N;
                if (nx == c) continue;
                int d = ((ct+4)/5)*5;
                if (d+ft[c][nx] > TMAX) break;
                nfs.push_back({c, nx, d, d+ft[c][nx]});
                ct = d+ft[c][nx]; c = nx;
            }
            planes[pi].fs = nfs;
        }

        if (!valid(planes[pi])) { planes[pi] = old; continue; }

        // Extract removed (old) and added (new) flights for skip-based eval
        CF removed_f[20]; int nr = 0;
        CF added_f[20]; int na = 0;
        for (auto& f : old.fs) removed_f[nr++] = {f.from, f.to, f.dep, f.arr};
        for (auto& f : planes[pi].fs) added_f[na++] = {f.from, f.to, f.dep, f.arr};

        long long ns = eval_incr_skip(planes, cur_partial,
                                       phase_ti[cur_phase], phase_nt[cur_phase],
                                       removed_f, nr, added_f, na);
        long long delta = ns - cur_partial;
        if (delta > 0 || exp((double)delta/T) > (double)(rng()%1000000)/1e6) {
            cur_partial = ns; ac++;
        } else {
            planes[pi] = old;
            rollback();
        }
    }

    // Final full evaluation
    {
        long long final_score = eval_full(planes);
        if (final_score > best) { best = final_score; best_p = planes; }
    }

    planes = best_p;
    fprintf(stderr, "SA: it=%d ac=%d best=%lld share=%.4f\n", it, ac, best, (double)best/tw);
    fprintf(stderr, "Phase iters: [%d, %d, %d]\n", phase_its[0], phase_its[1], phase_its[2]);

    long long verify = eval_full(planes);
    fprintf(stderr, "Verify: %lld (diff=%lld)\n", verify, verify - best);

    for (int p = 0; p < K; p++) {
        printf("%d\n", (int)planes[p].fs.size());
        for (auto& f : planes[p].fs) {
            string sd = fmt(f.dep), sa2 = fmt(f.arr);
            printf("%d %s %d %s\n", f.from+1, sd.c_str(), f.to+1, sa2.c_str());
        }
    }
    fprintf(stderr, "Score: %lld\nTotal: %.3fs\n", (long long)((double)best/tw*1e6), el());
    return 0;
}