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

const int T_START = 360;
const int T_END   = 1260;
const int T_STEP  = 5;
const int NUM_TARGETS = 21;
const int NEG_INF = -999999;
const int MAX_FL = 500;

int N, R, M, K;
double px[50], py[50];
int pw[50];

struct Flight { int a, b, s, t; };

Flight sq_arr[401];
double dist_tab[50][50];
int ftime_tab[50][50];
int vsrc[50][50], vsrc_cnt[50];
int target_t[NUM_TARGETS];
int sq_lat[50][NUM_TARGETS][50];

int plane_start[26];
int rd[26][200]; // route data
int rl[26];      // route length

mt19937 rng;
long long cum_w[50], total_w;

int sample_city() {
    long long r = rng() % total_w;
    int lo = 1, hi = N;
    while (lo < hi) { int m = (lo+hi)/2; if (cum_w[m] <= r) lo=m+1; else hi=m; }
    return lo;
}

int sample_buf(const int* buf, int n) {
    if (n == 1) return buf[0];
    long long s = 0;
    for (int i = 0; i < n; i++) s += pw[buf[i]];
    long long r = rng() % s, acc = 0;
    for (int i = 0; i < n; i++) { acc += pw[buf[i]]; if (acc > r) return buf[i]; }
    return buf[n-1];
}

int parse_time(const char* s) { int h,m; sscanf(s,"%d:%d",&h,&m); return h*60+m; }

void precompute() {
    for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) {
        double dx=px[i]-px[j], dy=py[i]-py[j];
        dist_tab[i][j]=sqrt(dx*dx+dy*dy);
    }
    for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) {
        if (i==j){ftime_tab[i][j]=0;continue;}
        double raw=60.0*dist_tab[i][j]/800.0+40.0;
        ftime_tab[i][j]=(int)ceil(raw/5.0)*5;
    }
    for (int j=1;j<=N;j++) {
        vsrc_cnt[j]=0;
        for (int i=1;i<=N;i++)
            if (i!=j && dist_tab[i][j]>=0.25*R)
                vsrc[j][vsrc_cnt[j]++]=i;
    }
    for (int k=0;k<NUM_TARGETS;k++) target_t[k]=660+30*k;
    cum_w[0]=0;
    for (int i=1;i<=N;i++) cum_w[i]=cum_w[i-1]+pw[i];
    total_w=cum_w[N];
}

Flight sq_sorted[401]; int sq_scnt;
void precompute_sq() {
    sq_scnt=M; memcpy(sq_sorted,sq_arr,sizeof(Flight)*M);
    sort(sq_sorted,sq_sorted+sq_scnt,[](const Flight&a,const Flight&b){return a.t>b.t;});
    int lat[50];
    for (int j=1;j<=N;j++) for (int k=0;k<NUM_TARGETS;k++) {
        for (int c=1;c<=N;c++) lat[c]=NEG_INF;
        lat[j]=target_t[k];
        for (int fi=0;fi<sq_scnt;fi++){
            const auto&f=sq_sorted[fi];
            if (lat[f.b]!=NEG_INF && f.t<=lat[f.b] && f.s>lat[f.a]) lat[f.a]=f.s;
        }
        memcpy(sq_lat[j][k],lat,sizeof(int)*(N+1));
    }
}

// Per-plane cached flights
Flight pfl[26][50]; int pfl_cnt[26];
void gen_plane(int p) {
    pfl_cnt[p]=0;
    if (rl[p]<2) return;
    int cur=plane_start[p];
    for (int i=0;i+1<rl[p];i++){
        int a=rd[p][i],b=rd[p][i+1],arr=cur+ftime_tab[a][b];
        if (arr>T_END) break;
        pfl[p][pfl_cnt[p]++]={a,b,cur,arr};
        cur=arr;
    }
}

Flight ci_buf[MAX_FL]; int ci_cnt;
void rebuild_ci() {
    ci_cnt=0;
    for (int p=1;p<=K;p++)
        for (int i=0;i<pfl_cnt[p];i++)
            ci_buf[ci_cnt++]=pfl[p][i];
    sort(ci_buf,ci_buf+ci_cnt,[](const Flight&a,const Flight&b){return a.t>b.t;});
}

long long eval_score() {
    long long v=0; int lat[50];
    for (int j=1;j<=N;j++){
        int wj=pw[j], vc=vsrc_cnt[j];
        if (!vc) continue;
        for (int k=0;k<NUM_TARGETS;k++){
            for (int c=1;c<=N;c++) lat[c]=NEG_INF;
            lat[j]=target_t[k];
            for (int fi=0;fi<ci_cnt;fi++){
                int fb=ci_buf[fi].b;
                if (lat[fb]!=NEG_INF && ci_buf[fi].t<=lat[fb]){
                    int fa=ci_buf[fi].a;
                    if (ci_buf[fi].s>lat[fa]) lat[fa]=ci_buf[fi].s;
                }
            }
            const int*sq=sq_lat[j][k], *vs=vsrc[j];
            for (int vi=0;vi<vc;vi++){
                int i=vs[vi];
                if (sq[i]<lat[i]) v+=(long long)pw[i]*wj;
            }
        }
    }
    return v;
}

void fill_route(int p) {
    int cur=plane_start[p];
    for (int i=0;i+1<rl[p];i++){
        int ft=ftime_tab[rd[p][i]][rd[p][i+1]];
        if (cur+ft>T_END){rl[p]=i+1;return;}
        cur+=ft;
    }
    int cands[50],ccnt;
    while (true) {
        int last=rd[p][rl[p]-1]; ccnt=0;
        for (int c=1;c<=N;c++){
            if (c==last) continue;
            if (cur+ftime_tab[last][c]<=T_END) cands[ccnt++]=c;
        }
        if (!ccnt) break;
        int nx=sample_buf(cands,ccnt);
        rd[p][rl[p]++]=nx;
        cur+=ftime_tab[last][nx];
    }
}

int main(){
    rng.seed(chrono::steady_clock::now().time_since_epoch().count());
    scanf("%d%d",&N,&R);
    for (int i=1;i<=N;i++) scanf("%lf%lf%d",&px[i],&py[i],&pw[i]);
    scanf("%d",&M);
    for (int i=0;i<M;i++){
        char ss[10],tt[10];
        scanf("%d%s%d%s",&sq_arr[i].a,ss,&sq_arr[i].b,tt);
        sq_arr[i].s=parse_time(ss); sq_arr[i].t=parse_time(tt);
    }
    scanf("%d",&K);
    precompute(); precompute_sq();

    // ---- Multiple random starts, pick best ----
    long long init_best = -1;
    int init_rd[26][200], init_rl[26], init_ps[26];
    for (int trial=0; trial<5; trial++){
        for (int p=1;p<=K;p++){
            plane_start[p]=T_START;
            rd[p][0]=sample_city(); rl[p]=1;
            fill_route(p);
            gen_plane(p);
        }
        rebuild_ci();
        long long sc=eval_score();
        if (sc>init_best){
            init_best=sc;
            for (int p=1;p<=K;p++){
                memcpy(init_rd[p],rd[p],sizeof(int)*rl[p]);
                init_rl[p]=rl[p]; init_ps[p]=plane_start[p];
            }
        }
    }
    for (int p=1;p<=K;p++){
        memcpy(rd[p],init_rd[p],sizeof(int)*init_rl[p]);
        rl[p]=init_rl[p]; plane_start[p]=init_ps[p];
        gen_plane(p);
    }
    rebuild_ci();

    // ---- SA ----
    long long cur_score=init_best, best_score=init_best;
    int best_rd[26][200], best_rl[26], best_ps[26];
    for (int p=1;p<=K;p++){
        memcpy(best_rd[p],rd[p],sizeof(int)*rl[p]);
        best_rl[p]=rl[p]; best_ps[p]=plane_start[p];
    }

    auto t0=chrono::steady_clock::now();
    const double time_limit=0.97;
    int iter=0;
    double cur_temp=1e13;

    int old_rd_buf[200];
    int old_rl_v, old_ps_v, old_pfl_cnt_v;
    Flight old_pfl_buf[50];
    // Save ci_buf for fast rollback (avoid re-sorting)
    Flight saved_ci[MAX_FL]; int saved_ci_cnt;

    while(true){
        if ((iter&63)==0){
            double el=chrono::duration<double>(chrono::steady_clock::now()-t0).count();
            if (el>=time_limit) break;
            double prog=el/time_limit;
            cur_temp=1e13*pow(1e-4,prog);
        }
        iter++;

        int p=rng()%K+1;
        // Save state
        old_rl_v=rl[p]; old_ps_v=plane_start[p]; old_pfl_cnt_v=pfl_cnt[p];
        memcpy(old_rd_buf,rd[p],sizeof(int)*old_rl_v);
        memcpy(old_pfl_buf,pfl[p],sizeof(Flight)*old_pfl_cnt_v);
        saved_ci_cnt=ci_cnt;
        memcpy(saved_ci,ci_buf,sizeof(Flight)*ci_cnt);

        // Mutation (0-2: change city 37.5%, 3: insert 12.5%, 4: remove 12.5%,
        //           5: swap 12.5%, 6: start time 12.5%, 7: reinit 12.5%)
        int mut=rng()%8;
        if (mut<=2 && rl[p]>=2){
            int pos=rng()%rl[p];
            rd[p][pos]=sample_city();
        } else if (mut==3 && rl[p]<190){
            int pos=rng()%(rl[p]+1), nc=sample_city();
            for (int i=rl[p];i>pos;i--) rd[p][i]=rd[p][i-1];
            rd[p][pos]=nc; rl[p]++;
        } else if (mut==4 && rl[p]>=2){
            int pos=rng()%rl[p];
            for (int i=pos;i+1<rl[p];i++) rd[p][i]=rd[p][i+1];
            rl[p]--;
        } else if (mut==5 && rl[p]>=3){
            int a=rng()%rl[p], b=rng()%rl[p];
            swap(rd[p][a],rd[p][b]);
        } else if (mut==6){
            int delta=((int)(rng()%13)-6)*T_STEP;
            plane_start[p]=max(T_START,min(T_END,plane_start[p]+delta));
        } else {
            rd[p][0]=sample_city(); rl[p]=1;
            fill_route(p);
        }

        // Validate
        bool ok=true;
        for (int i=0;i<rl[p]&&ok;i++) if (rd[p][i]<1||rd[p][i]>N) ok=false;
        for (int i=0;i+1<rl[p]&&ok;i++) if (rd[p][i]==rd[p][i+1]) ok=false;
        if (!ok||rl[p]==0){
            memcpy(rd[p],old_rd_buf,sizeof(int)*old_rl_v);
            rl[p]=old_rl_v; plane_start[p]=old_ps_v;
            continue;
        }

        gen_plane(p);
        rebuild_ci();
        long long ns=eval_score();

        long long d=ns-cur_score;
        bool accept=(d>=0);
        if (!accept && cur_temp>0){
            accept=((rng()%1000000)<(int)(exp((double)d/cur_temp)*1000000));
        }

        if (accept){
            cur_score=ns;
            if (ns>best_score){
                best_score=ns;
                for (int q=1;q<=K;q++){
                    memcpy(best_rd[q],rd[q],sizeof(int)*rl[q]);
                    best_rl[q]=rl[q]; best_ps[q]=plane_start[q];
                }
            }
        } else {
            // Fast rollback: restore saved state without rebuild_ci
            memcpy(rd[p],old_rd_buf,sizeof(int)*old_rl_v);
            rl[p]=old_rl_v; plane_start[p]=old_ps_v;
            pfl_cnt[p]=old_pfl_cnt_v;
            memcpy(pfl[p],old_pfl_buf,sizeof(Flight)*old_pfl_cnt_v);
            ci_cnt=saved_ci_cnt;
            memcpy(ci_buf,saved_ci,sizeof(Flight)*saved_ci_cnt);
        }
    }

    // Restore best
    for (int p=1;p<=K;p++){
        memcpy(rd[p],best_rd[p],sizeof(int)*best_rl[p]);
        rl[p]=best_rl[p]; plane_start[p]=best_ps[p];
        gen_plane(p);
    }
    fprintf(stderr,"SA: %d iters, best=%lld\n",iter,best_score);

    // Output
    for (int p=1;p<=K;p++){
        printf("%d\n",pfl_cnt[p]);
        for (int i=0;i<pfl_cnt[p];i++)
            printf("%d %02d:%02d %d %02d:%02d\n",
                pfl[p][i].a,pfl[p][i].s/60,pfl[p][i].s%60,
                pfl[p][i].b,pfl[p][i].t/60,pfl[p][i].t%60);
    }
    return 0;
}