#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define endl '\n' #define ALL(v) (v).begin(), (v).end() #define RALL(v) (v).rbegin(), (v).rend() #define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end()) typedef long long ll; typedef long double ld; typedef pair P; typedef complex comp; typedef vector< vector > matrix; struct pairhash { public: template size_t operator()(const pair &x) const { size_t seed = hash()(x.first); return hash()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2); } }; const int INF = 1e9 + 9; //const ll INF = 1e18 + 9; const ll MOD = 1e9 + 7; //const ll MOD = 998244353; const double EPS = 1e-8; const double PI = acos(-1); unsigned long xor128(void) { static unsigned long x=123456789,y=362436069,z=521288629,w=88675123; unsigned long t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); } // [0, k) int rand(int k) { return xor128() % k; } // [a, b) int rand(int a, int b) { return a + xor128() % (b - a); } int n, t; int a[3010], b[3010], c[3010], d[3010]; const int MAX_Y = 14; const int MAX_X = 14; double route_weight[15][15][2]; double weight_each[3010][15][15][2]; bool built[15][15][2]; struct road { double count; int x, y, t; }; bool operator< (const road& r1, const road& r2) { return r1.count < r2.count; } vector high_way; bool prev_build = false; void build(const road& r) { high_way.push_back(r); built[r.x][r.y][r.t] = true; prev_build = true; cout << "1 " << r.x+1 << " " << r.y+1 << " " << r.x+2-r.t << " " << r.y+r.t+1 << endl; cout.flush(); } void get_coop() { prev_build = false; cout << "2" << endl; cout.flush(); } void get_money() { prev_build = false; cout << "3" << endl; cout.flush(); } bool in_area(const int idx, const road& r) { const int minY = min(a[idx], c[idx]); const int maxY = max(a[idx], c[idx]); const int minX = min(b[idx], d[idx]); const int maxX = max(b[idx], d[idx]); return minY <= r.x && r.x <= maxY && minY <= r.x+1-r.t && r.x+1-r.t <= maxY && minX <= r.y && r.y <= maxX && minX <= r.y+r.t && r.y+r.t <= maxX; } void add_weight(const int idx) { const int minY = min(a[idx], c[idx]); const int maxY = max(a[idx], c[idx]); const int minX = min(b[idx], d[idx]); const int maxX = max(b[idx], d[idx]); for (int y = minY; y <= maxY; y++) { for (int x = minX; x <= maxX; x++) { route_weight[y][x][0] += weight_each[idx][y][x][0]; route_weight[y][x][1] += weight_each[idx][y][x][1]; } } } void subtract_weight(const int idx) { const int minY = min(a[idx], c[idx]); const int maxY = max(a[idx], c[idx]); const int minX = min(b[idx], d[idx]); const int maxX = max(b[idx], d[idx]); for (int y = minY; y <= maxY; y++) { for (int x = minX; x <= maxX; x++) { route_weight[y][x][0] -= weight_each[idx][y][x][0]; route_weight[y][x][1] -= weight_each[idx][y][x][1]; } } } void add_weight_each(const int idx, const int minY, const int maxY, const int minX, const int maxX, const double weight) { for (int y = minY; y <= maxY; y++) { for (int x = minX; x <= maxX; x++) { if (y < maxY) weight_each[idx][y][x][0] += weight; if (x < maxX) weight_each[idx][y][x][1] += weight; } } } void calc_weight_each(const int idx) { memset(weight_each[idx], 0, sizeof(weight_each[idx])); int cnt = 0; vector h; for (const auto& r : high_way) { if (in_area(idx, r)) { cnt++; h.push_back(r); } } const double weight = cnt == 0 ? 1.0 : 1.0 / cnt; const int minY = min(a[idx], c[idx]); const int maxY = max(a[idx], c[idx]); const int minX = min(b[idx], d[idx]); const int maxX = max(b[idx], d[idx]); if (cnt == 0) { add_weight_each(idx, minY, maxY, minX, maxX, weight); } else if ((a[idx] - c[idx]) * (b[idx] - d[idx]) > 0){ for (const auto& r : h) { add_weight_each(idx, minY, r.x, minX, r.y, weight); add_weight_each(idx, r.x+1-r.t, maxY, r.y+r.t, maxX, weight); } } else { for (const auto& r : h) { add_weight_each(idx, r.x+1-r.t, maxY, minX, r.y, weight); add_weight_each(idx, minY, r.x, r.y+r.t, maxX, weight); } } } void init() { for (int i = 0; i < n; i++) { calc_weight_each(i); add_weight(i); } } road get_candidate() { if (prev_build) { const auto& r = high_way.back(); for (int i = 0; i < n; i++) { if (in_area(i, r)) { subtract_weight(i); calc_weight_each(i); add_weight(i); } } } double max_weight = 0; road ret; for (int y = 0; y < MAX_Y; y++) { for (int x = 0; x < MAX_X; x++) { if (y < MAX_Y-1 && !built[y][x][0] && route_weight[y][x][0] > max_weight) { ret = road{route_weight[y][x][0], y, x, 0}; max_weight = route_weight[y][x][0]; } if (x < MAX_X-1 && !built[y][x][1] && route_weight[y][x][1] > max_weight) { ret = road{route_weight[y][x][1], y, x, 1}; max_weight = route_weight[y][x][1]; } } } return ret; } void solve() { init(); int u, v; for (int iter = 0; iter < t; iter++) { cin >> u >> v; const int cost = 1e7 / sqrt(v); const auto& r = get_candidate(); const int gain = r.count * (t-iter) * 60 * pow(0.99, iter); //cerr << "??? " << u << " " << v << " " << cost << " " << gain << endl; if (u < cost || gain < cost) { get_coop(); } else { build(r); } } } void input() { cin >> n >> t; for (int i = 0; i < n; i++) { cin >> a[i] >> b[i] >> c[i] >> d[i]; a[i]--; b[i]--; c[i]--; d[i]--; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15); input(); solve(); }