#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 cached_plane_id = -1;
int base_lat_cache[50][NUM_TARGETS][50];
bool is_valid_src[50][50];
int lat_cur[50][NUM_TARGETS][50];

int plane_start[26];
int rd[26][200];
int rl[26];

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 i=1;i<=N;i++) for(int j=1;j<=N;j++)
        is_valid_src[i][j]=(i!=j && dist_tab[i][j]>=0.25*R);
    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));
    }
}

Flight pfl[26][50]; int pfl_cnt[26];

void compute_base_lat(int exclude_p) {
    static Flight buf[1000];
    int cnt=0;
    for(int q=1;q<=K;q++){
        if(q==exclude_p) continue;
        for(int i=0;i<pfl_cnt[q];i++) buf[cnt++]=pfl[q][i];
    }
    sort(buf,buf+cnt,[](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<cnt;fi++){
            const auto&f=buf[fi];
            if(lat[f.b]!=NEG_INF && f.t<=lat[f.b] && f.s>lat[f.a]) lat[f.a]=f.s;
        }
        memcpy(base_lat_cache[j][k],lat,sizeof(int)*(N+1));
    }
    cached_plane_id=exclude_p;
}

long long eval_score_diff(int p) {
    int p_cnt=pfl_cnt[p];
    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++){
            memcpy(lat,base_lat_cache[j][k],sizeof(int)*(N+1));
            for(int fi=p_cnt-1;fi>=0;fi--){
                const auto&f=pfl[p][fi];
                if(lat[f.b]!=NEG_INF && f.t<=lat[f.b] && f.s>lat[f.a]) lat[f.a]=f.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 init_lat_cur(int p) {
    for(int j=1;j<=N;j++) for(int k=0;k<NUM_TARGETS;k++){
        memcpy(lat_cur[j][k],base_lat_cache[j][k],sizeof(int)*(N+1));
        for(int fi=pfl_cnt[p]-1;fi>=0;fi--){
            const auto&f=pfl[p][fi];
            if(lat_cur[j][k][f.b]!=NEG_INF && f.t<=lat_cur[j][k][f.b] && f.s>lat_cur[j][k][f.a])
                lat_cur[j][k][f.a]=f.s;
        }
    }
}

long long eval_flight_delta(int p, int a, int b, int s, int t) {
    long long delta=0;
    for(int j=1;j<=N;j++){
        if(!vsrc_cnt[j]) continue;
        for(int k=0;k<NUM_TARGETS;k++){
            if(lat_cur[j][k][b]==NEG_INF || t>lat_cur[j][k][b]) continue;
            if(s<=lat_cur[j][k][a]) continue;
            if(is_valid_src[a][j] && sq_lat[j][k][a]<s &&
               (lat_cur[j][k][a]==NEG_INF || sq_lat[j][k][a]>=lat_cur[j][k][a]))
                delta+=(long long)pw[a]*pw[j];
            int clat=s;
            for(int fi=pfl_cnt[p]-1;fi>=0;fi--){
                if(pfl[p][fi].t>clat) break;
                int fa=pfl[p][fi].a, fs=pfl[p][fi].s;
                int old_fa=lat_cur[j][k][fa];
                if(fs<=old_fa) break;
                if(is_valid_src[fa][j] && sq_lat[j][k][fa]<fs &&
                   (old_fa==NEG_INF || sq_lat[j][k][fa]>=old_fa))
                    delta+=(long long)pw[fa]*pw[j];
                clat=fs;
            }
        }
    }
    return delta;
}

void commit_flight_lat_cur(int p, int a, int b, int s, int t) {
    pfl[p][pfl_cnt[p]++]={a,b,s,t};
    for(int j=1;j<=N;j++) for(int k=0;k<NUM_TARGETS;k++){
        if(lat_cur[j][k][b]==NEG_INF || t>lat_cur[j][k][b]) continue;
        if(s<=lat_cur[j][k][a]) continue;
        lat_cur[j][k][a]=s;
        int clat=s;
        for(int fi=pfl_cnt[p]-2;fi>=0;fi--){
            if(pfl[p][fi].t>clat) break;
            int fa=pfl[p][fi].a;
            if(pfl[p][fi].s<=lat_cur[j][k][fa]) break;
            lat_cur[j][k][fa]=pfl[p][fi].s;
            clat=pfl[p][fi].s;
        }
    }
}

void greedy_extend(int p) {
    int cur_time, last_city;
    if(pfl_cnt[p]>0){
        cur_time=pfl[p][pfl_cnt[p]-1].t;
        last_city=pfl[p][pfl_cnt[p]-1].b;
    } else {
        cur_time=plane_start[p]; last_city=-1;
        for(int i=0;i<rl[p];i++){
            if(rd[p][i]>0){last_city=rd[p][i];break;}
            else cur_time+=T_STEP;
        }
    }
    if(last_city<1) return;
    while(true){
        int best_c=-1; long long best_d=-1;
        for(int c=1;c<=N;c++){
            if(c==last_city) continue;
            int arr=cur_time+ftime_tab[last_city][c];
            if(arr>T_END) continue;
            long long d=eval_flight_delta(p,last_city,c,cur_time,arr);
            if(d>best_d||(d==best_d&&(rng()&1))){best_d=d;best_c=c;}
        }
        if(best_c==-1) break;
        int arr=cur_time+ftime_tab[last_city][best_c];
        commit_flight_lat_cur(p,last_city,best_c,cur_time,arr);
        rd[p][rl[p]++]=best_c;
        cur_time=arr; last_city=best_c;
    }
}

// rd[p][i]==0 means "wait 5 min at current city"
// rd[p][i]>=1 means city id
void gen_plane(int p) {
    pfl_cnt[p]=0;
    if(rl[p]<1) return;
    int cur=plane_start[p];
    int last_city=-1; // last real city
    for(int i=0;i<rl[p];i++){
        if(rd[p][i]==0){
            // wait 5 minutes
            cur+=T_STEP;
            if(cur>T_END) break;
        } else {
            if(last_city==-1){
                last_city=rd[p][i]; // starting city
            } else {
                int a=last_city, b=rd[p][i];
                int arr=cur+ftime_tab[a][b];
                if(arr>T_END) break;
                pfl[p][pfl_cnt[p]++]={a,b,cur,arr};
                cur=arr;
                last_city=b;
            }
        }
    }
}

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) {
    // Replay existing route to find cur time and last city
    int cur=plane_start[p];
    int last_city=-1;
    for(int i=0;i<rl[p];i++){
        if(rd[p][i]==0){
            cur+=T_STEP;
            if(cur>T_END){rl[p]=i;return;}
        } else {
            if(last_city>=1){
                int ft=ftime_tab[last_city][rd[p][i]];
                if(cur+ft>T_END){rl[p]=i;return;}
                cur+=ft;
            }
            last_city=rd[p][i];
        }
    }
    if(last_city<1) return;
    // Greedily extend
    int cands[50],ccnt;
    while(true){
        ccnt=0;
        for(int c=1;c<=N;c++){
            if(c==last_city) continue;
            if(cur+ftime_tab[last_city][c]<=T_END) cands[ccnt++]=c;
        }
        if(!ccnt) break;
        int nx=sample_buf(cands,ccnt);
        rd[p][rl[p]++]=nx;
        cur+=ftime_tab[last_city][nx];
        last_city=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);
    auto t0=chrono::steady_clock::now();

    precompute(); precompute_sq();

    // ---- Initial solution: greedy construction ----
    for(int p=1;p<=K;p++){plane_start[p]=T_START;pfl_cnt[p]=0;rl[p]=0;}
    // Sort cities by weight descending for starting city trials
    int city_order[50]; int n_cities=N;
    for(int i=0;i<N;i++) city_order[i]=i+1;
    sort(city_order,city_order+N,[](int a,int b){return pw[a]>pw[b];});
    int num_trials=min(N,5);
    for(int p=1;p<=K;p++){
        compute_base_lat(p);
        int sv_rd[200],sv_rl; Flight sv_pfl[50]; int sv_pc;
        long long best_sc=-1;
        for(int tr=0;tr<num_trials;tr++){
            int c=city_order[tr];
            rd[p][0]=c; rl[p]=1; pfl_cnt[p]=0;
            init_lat_cur(p); greedy_extend(p);
            gen_plane(p); // ensure consistency
            long long sc=eval_score_diff(p);
            if(sc>best_sc){
                best_sc=sc;
                memcpy(sv_rd,rd[p],sizeof(int)*rl[p]); sv_rl=rl[p];
                memcpy(sv_pfl,pfl[p],sizeof(Flight)*pfl_cnt[p]); sv_pc=pfl_cnt[p];
            }
        }
        memcpy(rd[p],sv_rd,sizeof(int)*sv_rl); rl[p]=sv_rl;
        memcpy(pfl[p],sv_pfl,sizeof(Flight)*sv_pc); pfl_cnt[p]=sv_pc;
    }
    long long init_best=0;
    {   // compute exact initial score
        rebuild_ci(); init_best=eval_score();
    }

    // ---- SA (differential evaluation) ----
    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];
    }

    const double time_limit=0.95;
    int iter=0;
    double cur_temp=1e13;
    bool sa_timeout=false;

    int old_rd_buf[200];
    Flight old_pfl_buf[50];
    int old_rl_v, old_ps_v, old_pfl_cnt_v;

    int greedy_cd=0;
    while(!sa_timeout){
        int p=rng()%K+1;
        if(p!=cached_plane_id){
            compute_base_lat(p);
            cur_score=eval_score_diff(p);
        }

        // Periodic greedy rebuild
        greedy_cd--;
        if(greedy_cd<=0){
            greedy_cd=8;
            double el2=chrono::duration<double>(chrono::steady_clock::now()-t0).count();
            if(el2<time_limit-0.02){
                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);
                int brk=1+rng()%max(1,rl[p]-1);
                rl[p]=brk; gen_plane(p);
                init_lat_cur(p); greedy_extend(p);
                gen_plane(p);
                long long ns=eval_score_diff(p);
                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 {
                    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);
                }
            }
        }

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

            // Save
            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);

            // Mutations
            int rlen=rl[p];
            int mut=rng()%20;
            if(mut<7 && rlen>=1){
                int pos=rng()%rlen;
                rd[p][pos]=sample_city();
            } else if(mut<9 && rlen<190){
                int pos=rng()%(rlen+1);
                for(int i=rlen;i>pos;i--) rd[p][i]=rd[p][i-1];
                rd[p][pos]=sample_city(); rl[p]++;
            } else if(mut<11 && rlen>=2){
                int pos=1+rng()%(rlen-1);
                for(int i=pos;i+1<rlen;i++) rd[p][i]=rd[p][i+1];
                rl[p]--;
            } else if(mut<13 && rlen>=3){
                int a=rng()%rlen, b=rng()%rlen;
                swap(rd[p][a],rd[p][b]);
            } else if(mut<15 && rlen<190 && rlen>=2){
                int pos=1+rng()%(rlen-1);
                for(int i=rlen;i>pos;i--) rd[p][i]=rd[p][i-1];
                rd[p][pos]=0; rl[p]++;
            } else if(mut<16){
                for(int i=rlen-1;i>=1;i--){
                    if(rd[p][i]==0){
                        for(int j=i;j+1<rlen;j++) rd[p][j]=rd[p][j+1];
                        rl[p]--; break;
                    }
                }
            } else if(mut<18){
                int delta=((int)(rng()%25)-12)*T_STEP;
                plane_start[p]=max(T_START,min(T_END-60,plane_start[p]+delta));
            } else {
                rd[p][0]=sample_city(); rl[p]=1;
                fill_route(p);
            }

            // Validate
            bool ok=(rl[p]>=1 && rd[p][0]>=1 && rd[p][0]<=N);
            if(ok){
                int prev_city=-1;
                for(int i=0;i<rl[p]&&ok;i++){
                    int v=rd[p][i];
                    if(v<0||v>N) ok=false;
                    else if(v>0){
                        if(v==prev_city) ok=false;
                        prev_city=v;
                    }
                }
            }
            if(!ok){
                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);
            long long ns=eval_score_diff(p);

            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 {
                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);
            }
        }
    }

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

    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;
}