#include #define endl '\n' using namespace std; #define int long long int const int MAXN = 50000 + 5; struct Tower { int x, y, count; Tower() {}; Tower(int _x, int _y, int _count) { x = _x; y = _y; count = _count; } }; bool cmp(Tower a, Tower b) { // return a.x < b.x; return a.x + a.y < b.x + b.y; } int currx, curry; bool cmp2(Tower a, Tower b) { return (currx-a.x)*(currx-a.x) + (curry-a.y)*(curry-a.y) < (currx-b.x)*(currx-b.x) + (curry-b.y)*(curry-b.y); } int n, m; vector towers1; vector towers2; vector commands; void addCommand(int a, int b, int c, int d, int e) { commands.push_back(to_string(a) + " " + to_string(b) + " " + to_string(c) + " " + to_string(d) + " " + to_string(e)); } signed main () { freopen("war.in", "r", stdin); freopen("war.out", "w", stdout); cin >> n >> m; towers1.resize(n); towers2.resize(m); int sum1 = 0, sum2 = 0; for (int i = 0; i < n; i++) { int x, y, u; cin >> x >> y >> u; sum1 += u; towers1[i] = Tower(x, y, u); } int maxv = 0; for (int i = 0; i < m; i++) { int x, y, u; cin >> x >> y >> u; sum2 += u; maxv = max(maxv, u); towers2[i] = Tower(x, y, u); } sort(towers1.begin(), towers1.end(), cmp); sort(towers2.begin(), towers2.end(), cmp); int k = sqrt(maxv); int mm = 100; int ind = 0; for (int i = 0; i < m; i++) { while (ind < towers1.size()-1 && towers1[ind].count < 1) ind++; currx = towers2[i].x; curry = towers2[i].y; // sort(towers1.begin() + ind, towers1.begin() + min(ind + mm, (int)towers1.size()), cmp2); int new_ind = ind; int sum = 0; int posx = towers2[i].x+1; int posy = towers2[i].y+1; for (int j = ind; j < towers1.size(); j++) { if (towers1[j].count < 1) continue; addCommand(towers1[j].x, towers1[j].y, posx, posy, towers1[j].count); sum += towers1[j].count; towers1[j].count = 0; towers1[j].x = posx; towers1[j].y = posy; if (sum >= towers2[i].count) { if (sum1 >= sum2) { ind = j; break; } int rem = ceil(sqrt((long double)(sum*sum - towers2[i].count*towers2[i].count))); if (sum1 - sum + rem >= sum2 - towers2[i].count) { ind = j; break; } if (sum >= k*towers2[i].count) { ind = j; break; } } } int rem = ceil(sqrt((long double)(sum*sum - towers2[i].count*towers2[i].count))); addCommand(posx, posy, towers2[i].x, towers2[i].y, sum); sum1 = sum1 - sum + rem; sum2 = sum2 - towers2[i].count; towers1[ind].x = towers2[i].x; towers1[ind].y = towers2[i].y; towers1[ind].count = rem; } // int ind = 1; // for (int i = 1; i <= m; i++) // { // while (towers1[ind].count < 1 && ind <= n) ind++; // // int posx = towers2[i].x+1; // int posy = towers2[i].y+1; // // // long long sum = 0; // // currx = posx; // curry = posy; //// sort(towers1.begin() + ind, towers1.begin() + 1 + min(n, 100LL), cmp3); // // while (true) // { // if (ind > n) break; // if (sum >= towers2[i].count) // { // if (sum1 >= sum2) break; // // int rem = ceil(sqrt((long double)(sum*sum - towers2[i].count*towers2[i].count))); // if (sum1 - sum + rem >= sum2 - towers2[i].count) break; // // if (sum >= k * towers2[i].count) break; // } // // if (towers1[ind].count < 1) // { // ind++; // continue; // } // addCommand(towers1[ind].x, towers1[ind].y, posx, posy, towers1[ind].count); // // sum += towers1[ind].count; // towers1[ind].count = 0; // towers1[ind].x = posx; // towers1[ind].y = posy; // ind++; // } // ind--; // // // // // // sum1 = sum1 - sum + rem; // sum2 = sum2 - towers2[i].count; // // towers1[ind].x = towers2[i].x; // towers1[ind].y = towers2[i].y; // towers1[ind].count = rem; //// towers1[ind].count = 0; // } // // cout << commands.size() << endl; for (string command : commands) { cout << command << endl; // cerr << command << endl; } return 0; }