#include <array>
#include <cmath>
#include <queue>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <algorithm>
using namespace std;

using ll = long long;

mt19937_64 mt(1);

const int N = 47;
const int R = 1000;
const int M = 400;
const int K = 25;

int convert_time_int(string s) {
	assert(s.size() == 5);
	assert('0' <= s[0] && s[0] <= '9');
	assert('0' <= s[1] && s[1] <= '9');
	assert(s[2] == ':');
	assert('0' <= s[3] && s[3] <= '9');
	assert('0' <= s[4] && s[4] <= '9');
	int h = int(s[0] - '0') * 10 + int(s[1] - '0');
	int m = int(s[3] - '0') * 10 + int(s[4] - '0');
	assert(make_pair(h, m) >= make_pair(6, 0));
	assert(make_pair(h, m) <= make_pair(21, 0));
	assert(m % 5 == 0);
	return (h - 6) * 12 + (m / 5);
}

string convert_int_time(int x) {
	assert(0 <= x && x <= 180);
	int h = x / 12 + 6;
	int m = (x % 12) * 5;
	string res;
	res += char(h / 10 + '0');
	res += char(h % 10 + '0');
	res += ':';
	res += char(m / 10 + '0');
	res += char(m % 10 + '0');
	return res;
}

int sqr(int x) {
	return x * x;
}

class city {
public:
	int x, y, w;
	explicit city() : x(0), y(0), w(0) {}
	explicit city(int x_, int y_, int w_) : x(x_), y(y_), w(w_) {}
};

class route {
public:
	int a, s, b, t;
	explicit route() : a(-1), s(-1), b(-1), t(-1) {}
	explicit route(int a_, int s_, int b_, int t_) : a(a_), s(s_), b(b_), t(t_) {}
};

int get_norm(const city& c1, const city& c2) {
	return sqr(c2.x - c1.x) + sqr(c2.y - c1.y);
}

int req_time(const city& c1, const city& c2) {
	int norm = get_norm(c1, c2);
	int res = ceil((60 * sqrt(norm) / 800 + 40) / 5);
	return res;
}

vector<vector<vector<int>>> calc_times(const vector<route>& routes) {
	vector<vector<int>> base_g(N);
	for (int i = 0; i < int(routes.size()); i++) {
		base_g[routes[i].b].push_back(i);
	}
	vector<vector<vector<int>>> base_time(21, vector<vector<int>>(N));
	for (int i = 0; i <= 20; i++) {
		int start = i * 6 + 60;
		for (int j = 0; j < N; j++) {
			vector<int> d(N, -1);
			d[j] = start;
			priority_queue<pair<int, int>> que;
			que.emplace(start, j);
			while (!que.empty()) {
				auto [t, u] = que.top();
				que.pop();
				if (d[u] == t) {
					vector<int> best_s(N, -1);
					for (int k : base_g[u]) {
						const route& r = routes[k];
						if (r.t <= t) {
							best_s[r.a] = max(best_s[r.a], r.s);
						}
					}
					for (int k = 0; k < N; k++) {
						if (d[k] < best_s[k]) {
							d[k] = best_s[k];
							que.emplace(d[k], k);
						}
					}
				}
			}
			base_time[i][j] = d;
		}
	}
	return base_time;
}

vector<route> flatten(const vector<vector<route>>& ans) {
	vector<route> res;
	for (const vector<route>& v : ans) {
		for (const route& r : v) {
			res.push_back(r);
		}
	}
	return res;
}

pair<ll, ll> get_base_score(const vector<city>& cities, const vector<vector<vector<int>>>& sq_time, const vector<vector<vector<int>>>& ci_time) {
	ll sq_val = 0;
	ll ci_val = 0;
	for (int i = 0; i < 21; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				int norm = get_norm(cities[j], cities[k]);
				if (norm * 16 >= R * R) {
					if (ci_time[i][j][k] > sq_time[i][j][k]) {
						ci_val += (ll)(cities[j].w) * cities[k].w;
					} else {
						sq_val += (ll)(cities[j].w) * cities[k].w;
					}
				}
			}
		}
	}
	return make_pair(sq_val, ci_val);
}

class bit192 {
private:
	array<uint64_t, 3> bit;
public:
	int get(int idx) const {
		return (bit[idx >> 6] >> (idx & 63)) & 1;
	}
	void set(int idx) {
		bit[idx >> 6] |= uint64_t(1) << (idx & 63);
	}
	void unset(int idx) {
		bit[idx >> 6] &= ~(uint64_t(1) << (idx & 63));
	}
	int query_one(int idx) const {
		// find the last 1 in positions 0, ..., idx (inclusive!)
		if (idx >= 128) {
			uint64_t q = bit[2] & ((uint64_t(2) << (idx - 128)) - 1);
			if (q) {
				return 128 + (63 - __builtin_clzll(q));
			}
		}
		if (idx >= 64) {
			uint64_t q = bit[1] & ((uint64_t(2) << min(idx - 64, 63)) - 1);
			if (q) {
				return 64 + (63 - __builtin_clzll(q));
			}
		}
		if (idx >= 0) {
			uint64_t q = bit[0] & ((uint64_t(2) << min(idx, 63)) - 1);
			if (q) {
				return 63 - __builtin_clzll(q);
			}
		}
		return -1;
	}
};

vector<vector<route>> solve(const vector<city>& cities, const vector<route>& routes) {
	// step #1. calculate distances
	vector<vector<int>> cost(N, vector<int>(N));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (i != j) {
				cost[i][j] = req_time(cities[i], cities[j]);
			}
		}
	}
	vector<vector<bool>> far(N, vector<bool>(N));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			far[i][j] = (get_norm(cities[i], cities[j]) * 16 >= R * R);
		}
	}
	vector<vector<vector<int>>> sq_time = calc_times(routes);

	// step #2. find optimal hub
	pair<ll, int> hub_opt = make_pair(7LL << 58, -1);
	for (int i = 0; i < N; i++) {
		ll total = 0;
		for (int j = 0; j < N; j++) {
			for (int k = j + 1; k < N; k++) {
				if (far[j][k]) {
					int d = cost[j][i] + cost[k][i];
					total += (ll)(d) * cities[j].w * cities[k].w;
				}
			}
		}
		hub_opt = min(hub_opt, make_pair(total, i));
	}
	int hub = hub_opt.second;
	cerr << "hub = " << hub << endl;
	vector<int> c(N);
	for (int i = 0; i < N; i++) {
		c[i] = cost[hub][i];
	}

	// step #3. data structure for intervals
	vector<bit192> state(N);
	vector<vector<vector<int>>> ci_time(21, vector<vector<int>>(N, vector<int>(N, -1)));
	ll score = 0;
	auto update = [&](int t, int x, int y) -> void {
		// update ci_time[t][x][y]
		int s0 = t * 6 + 60, res = -1;
		if (x != hub && y != hub) {
			int s1 = state[x].query_one(s0);
			int s2 = state[y].query_one(s1 - c[x] - c[y]);
			res = s2;
		}
		if (x != hub && y == hub) {
			int s1 = state[x].query_one(s0);
			res = (s1 != -1 ? s1 - c[x] : -1);
		}
		if (x == hub && y != hub) {
			int s2 = state[y].query_one(s0 - c[y]);
			res = s2;
		}
		ll delta = (ll)(cities[x].w) * cities[y].w;
		if (ci_time[t][x][y] > sq_time[t][x][y]) {
			score -= delta;
		}
		ci_time[t][x][y] = res;
		if (ci_time[t][x][y] > sq_time[t][x][y]) {
			score += delta;
		}
	};
	auto add = [&](int x, int y) -> void {
		// (hub at time y-c[x]) --> (city x at time y) --> (hub at time y+c[x])
		int start = (max(y - 60, 0) + 5) / 6;
		state[x].set(y);
		for (int i = start; i < 21; i++) {
			for (int j = 0; j < N; j++) {
				if (far[x][j]) {
					update(i, x, j);
					update(i, j, x);
				}
			}
		}
	};
	auto remove = [&](int x, int y) -> void {
		// (hub at time y-c[x]) --> (city x at time y) --> (hub at time y+c[x])
		state[x].unset(y);
		for (int i = 0; i < 21; i++) {
			for (int j = 0; j < N; j++) {
				if (far[x][j]) {
					update(i, x, j);
					update(i, j, x);
				}
			}
		}
	};

	// step #4. hill climbing
	const double TIME_LIMIT = 0.85;
	const clock_t start_time = clock();
	double elapsed = 0.0;
	vector<pair<int, int>> place;
	vector<int> span(180);
	ll loops = 0;
	while (true) {
		loops++;
		if ((loops & 7) == 0) {
			elapsed = ((clock() - start_time) / CLOCKS_PER_SEC) / TIME_LIMIT;
			if (elapsed >= 1.0) {
				break;
			}
		}
		vector<pair<int, int>> old_place = place;
		vector<int> old_span = span;
		ll old_score = score;
		int x, y;
		do {
			x = mt() % N;
			y = mt() % 181;
		} while (x == hub || state[x].get(y));
		int l = max(y - c[x], 0);
		int r = min(y + c[x], 180);
		vector<int> c1_buf(r - l);
		vector<int> c2_buf(place.size());
		vector<pair<int, int>> erased;
		while (true) {
			int h = *max_element(span.begin() + l, span.begin() + r);
			if (h < K) {
				break;
			}
			int c1 = 0;
			for (int i = l; i < r; i++) {
				if (span[i] == K) {
					c1_buf[c1++] = i;
				}
			}
			int pos1 = c1_buf[mt() % c1];
			int c2 = 0;
			for (int i = 0; i < int(place.size()); i++) {
				auto [sx, sy] = place[i];
				if (sy - c[sx] <= pos1 && pos1 < sy + c[sx]) {
					c2_buf[c2++] = i;
				}
			}
			int pos2 = c2_buf[mt() % c2];
			auto [tx, ty] = place[pos2];
			for (int i = max(ty - c[tx], 0); i < min(ty + c[tx], 180); i++) {
				span[i]--;
			}
			erased.push_back(place[pos2]);
			place.erase(place.begin() + pos2);
			remove(tx, ty);
		}
		place.emplace_back(x, y);
		for (int i = l; i < r; i++) {
			span[i]++;
		}
		add(x, y);
		if (old_score <= score || (double(mt()) / double(uint64_t(-1)) < exp((score - old_score) / (2.0e+12 * (1.0 - elapsed))))) {
			if (old_score < score) {
				cerr << "#" << loops << ": " << score << endl;
			}
		} else {
			remove(x, y);
			for (auto [sx, sy] : erased) {
				add(sx, sy);
			}
			place = old_place;
			span = old_span;
		}
	}

	// step #4. greedy algorithm
	vector<route> ans;
	for (auto [x, y] : place) {
		ans.push_back(route(hub, y - c[x], x, y));
		ans.push_back(route(x, y, hub, y + c[x]));
	}
	const int MAX_TIME = 38;
	const int Z = ans.size() / 2;
	vector<bool> occupied(K);
	vector<int> seat(Z, -1);
	vector<vector<int>> g_start(181 + MAX_TIME * 2), g_end(181 + MAX_TIME * 2);
	vector<vector<route>> final_ans(K);
	for (int i = 0; i < Z; i++) {
		g_start[ans[i * 2 + 0].s + MAX_TIME].push_back(i);
		g_end[ans[i * 2 + 1].t + MAX_TIME].push_back(i);
	}
	for (int i = 0; i <= 180 + MAX_TIME * 2; i++) {
		for (int j : g_end[i]) {
			occupied[seat[j]] = false;
		}
		for (int j : g_start[i]) {
			int x = -1;
			for (int k = 0; k < K; k++) {
				if (!occupied[k]) {
					x = k;
					break;
				}
			}
			assert(x != -1);
			occupied[x] = true;
			seat[j] = x;
			if (ans[j * 2 + 0].s >= 0) {
				final_ans[x].push_back(ans[j * 2 + 0]);
			}
			if (ans[j * 2 + 1].t <= 180) {
				final_ans[x].push_back(ans[j * 2 + 1]);
			}
		}
	}

	return final_ans;
}

void output_score(const vector<city>& cities, const vector<route>& routes, const vector<vector<route>>& ans) {
	// step #1. check if the answer is valid
	if (ans.size() != K) {
		cerr << "wrong answer [1]" << endl;
		return;
	}
	for (int i = 0; i < K; i++) {
		int rs = ans[i].size();
		for (int j = 0; j < rs; j++) {
			route r = ans[i][j];
			if (!(0 <= r.a && r.a < N && 0 <= r.b && r.b < N && 0 <= r.s && r.s <= 180 && 0 <= r.t && r.t <= 180)) {
				cerr << "wrong answer [2]" << endl;
				return;
			}
			if (r.t - r.s != req_time(cities[r.a], cities[r.b])) {
				cerr << "wrong answer [3]" << endl;
				return;
			}
			if (j >= 1) {
				route pr = ans[i][j - 1];
				if (!(pr.b == r.a && pr.t <= r.s)) {
					cerr << "wrong answer [4]" << endl;
					return;
				}
			}
		}
	}

	// step #2. compute score
	vector<vector<vector<int>>> sq_time = calc_times(routes);
	vector<vector<vector<int>>> ci_time = calc_times(flatten(ans));
	auto [sq_val, ci_val] = get_base_score(cities, sq_time, ci_time);
	double share = double(ci_val) / (sq_val + ci_val);
	cerr << "sq_val = " << sq_val << endl;
	cerr << "ci_val = " << ci_val << endl;
	cerr << "score = " << int(share * 1000000) << endl;
}

int main() {
	int TMP_N, TMP_R, TMP_M, TMP_K;
	cin >> TMP_N >> TMP_R;
	vector<city> cities(N);
	for (int i = 0; i < N; i++) {
		cin >> cities[i].x >> cities[i].y >> cities[i].w;
	}
	cin >> TMP_M;
	vector<route> routes(M);
	for (int i = 0; i < M; i++) {
		int a, b; string cs, ct;
		cin >> a >> cs >> b >> ct;
		routes[i].a = a - 1;
		routes[i].s = convert_time_int(cs);
		routes[i].b = b - 1;
		routes[i].t = convert_time_int(ct);
	}
	vector<vector<route>> ans = solve(cities, routes);
	for (int i = 0; i < K; i++) {
		cout << ans[i].size() << endl;
		for (const route& r : ans[i]) {
			cout << r.a + 1 << ' ' << convert_int_time(r.s) << ' ' << r.b + 1 << ' ' << convert_int_time(r.t) << endl;
		}
	}
	output_score(cities, routes, ans);
	return 0;
}