#include <bits/stdc++.h>

#define QINGYU_LOCAL
//11
#ifdef QINGYU_LOCAL
#define debug(x) \
        cerr << "Func " << __FUNCTION__ << ", " << "L" << __LINE__ << ": " << #x << " = " << x << '\n'
#else
#define debug(x) 0
#endif

using namespace std;


namespace builtin_constraints {
    constexpr int MAX_N = 8 + 1;        // number of network domains
    constexpr int MAX_R = 32 + 1;        // number of racks in each network domain
    constexpr int MAX_S = 16 + 1;        // number of physical machines in each rack
    constexpr int MAX_K = 4 + 1;        // number of NUMA nodes per PM
    constexpr int MAX_F = 20 + 1;        // number of VM types
    constexpr int MAX_CPU = 200;             // maximum value of CPU capacity
    constexpr int MAX_MEMORY = 500;             // maximum value of MEMORY CAPACITY
    constexpr int MAX_VM = 235'000 + 50;     // maximum number of created VMs
    constexpr int MAX_REQ = 13'500 + 50;     // maximum number of requests

    constexpr int NO_CONSTRAINT = 0;            // given constraint doesn't exist
    constexpr int SOFT_CONSTRAINT = 1;            // given constraint is soft
    constexpr int HARD_CONSTRAINT = 2;            // given constraint is hard
    constexpr int QINGYU_SEED = 20041115;     // fixed random seed
    int N, R, S, K, F;

    bool in_range(int x, int l, int r) {
        return l <= x && x < r;
    }

    bool is_valid_network_id(int x) {
        return in_range(x, 0, N);
    }

    bool is_valid_rack_id(int x) {
        return in_range(x, 0, R);
    }

    bool is_valid_pm_id(int x) {
        return in_range(x, 0, S);
    }

    bool is_valid_node_id(int x) {
        return in_range(x, 0, K);
    }

    bool is_valid_vm_id(int x) {
        return in_range(x, 0, F);
    }
};

using namespace builtin_constraints;

mt19937 rng(QINGYU_SEED);

function<int64_t(int, int)> global_get_value = [](int, int) -> int64_t {
    throw "not assigned yet";
};

class node_t {
public:
    int cpu, memory;
    int64_t val;
//    function<int64_t()> get_value;
    node_t() : cpu(0), memory(0) {

    }

    void update_value() {
        val = global_get_value(cpu, memory);
    }
    node_t(int cpu, int memory) : cpu(cpu), memory(memory) {
//        update_value();
    }
    int64_t get_value() const {
        return cpu + memory;
    }
};

node_t operator+(const node_t &lhs, const node_t &rhs) {
    return node_t(lhs.cpu + rhs.cpu, lhs.memory + rhs.memory);
}

node_t &operator+=(node_t &lhs, const node_t &rhs) {
    return lhs = (lhs + rhs);
}

node_t operator-(const node_t &lhs, const node_t &rhs) {
    return node_t(lhs.cpu - rhs.cpu, lhs.memory - rhs.memory);
}

node_t &operator-=(node_t &lhs, const node_t &rhs) {
    return lhs = (lhs - rhs);
}

node_t operator*(const node_t &lhs, const int k) {
    return node_t(lhs.cpu * k, lhs.memory * k);
}

ostream &operator<<(ostream &f, const node_t &rhs) {
    f << "(" << rhs.cpu << "c, " << rhs.memory << "m)";
    return f;
}

auto operator<=>(const node_t &lhs, const node_t &rhs) {
    return lhs.val <=> rhs.val;
    //    return lhs.get_value() <=> rhs.get_value();
}

bool can_fit(const node_t &container, const node_t &target) {
    return container.cpu >= target.cpu && container.memory >= target.memory;
}

class VM_t {
public:
    int n, cpu, memory;

    VM_t() : n(0), cpu(0), memory(0) {}

    VM_t(int n, int c, int m) : n(n), cpu(c), memory(m) {}

    operator node_t() const {
        return node_t(cpu, memory);
    }
};

ostream &operator<<(ostream &f, const VM_t &rhs) {
    f << "(" << rhs.n << "n, " << rhs.cpu << "c, " << rhs.memory << "m)";
    return f;
}

class PG_t {
public:
    /// number of partitions for hard rack anti-affinity with partitions
    int k;
    /// maximum number of VMs for soft PM anti-affinity
    int a;
    /// network affinity requirement
    int network_affinity;
    /// rack affinity requirement
    int rack_affinity;

    PG_t() : k(0), a(0), network_affinity(0), rack_affinity(0) {}

    PG_t(int k, int a, int n, int r) : k(k), a(a), network_affinity(n), rack_affinity(r) {}
};

ostream &operator<<(ostream &f, const PG_t &p) {
    f << "(k = " << p.k << ", a = " << p.a << ", n = " << p.network_affinity << ", r = " << p.rack_affinity << ")";
    return f;
}

class position_t {
public:
    int id;
    int pg_id;              /// placement group id
    int vm_id;              /// virtual machine id
    int partition_id;       /// partition id
    int network_id;         /// network id
    int rack_id;            /// rack id
    int pm_id;              /// physical machine id
    int node_0, node_1;     /// NUMA's id
    position_t() : id(0), pg_id(0), vm_id(0), partition_id(0), network_id(0), rack_id(0), pm_id(0), node_0(-1), node_1(-1) {}

    position_t(int id, int pg_id, int vm_id) : id(id), pg_id(pg_id), vm_id(vm_id), partition_id(partition_id), network_id(0),
                                               rack_id(0), pm_id(0), node_0(-1), node_1(-1) {
        assert(is_valid_vm_id(vm_id));
    }

    void set_position(int network_id, int rack_id, int pm_id, int node_0 = -1, int node_1 = -1) {
        assert(is_valid_network_id(network_id));
        assert(is_valid_rack_id(rack_id));
        assert(is_valid_pm_id(pm_id));
        assert(node_0 == -1 || is_valid_node_id(node_0));
        assert(node_1 == -1 || is_valid_node_id(node_1));
        this->network_id = network_id;
        this->rack_id = rack_id;
        this->pm_id = pm_id;
        this->node_0 = node_0;
        this->node_1 = node_1;
    }
};

namespace interaction_protocol {
    bool called;

    void reset() {
        called = false;
    }

    void finish() {
        assert(called);
    }

    void failed_to_place() {
        cerr << "Failed to place, will exit soon!\n";
        cout << "-1" << '\n';
        cout.flush();
        exit(0);
    }

    void print_plan(int nv, int rv, int sv, vector<int> nodes) {
        assert(nodes.size() <= 2);
        assert(is_valid_network_id(nv));
        assert(is_valid_rack_id(rv));
        assert(is_valid_pm_id(sv));
        for (int z: nodes)
            assert(is_valid_node_id(z));
        assert(!called);
        cout << nv + 1 << ' ' << rv + 1 << ' ' << sv + 1;
        for (int x: nodes) cout << ' ' << x + 1;
        cout << '\n';
        cout.flush();
    }

    void print_plan(vector<vector<int>> ret) {
        for (auto &vec: ret) {
            assert(in_range(vec.size(), 4, 4 + 2));
            int nv = vec[0];
            int rv = vec[1];
            int sv = vec[2];
            vector<int> remain = {};
            for (int i = 3; i < vec.size(); ++i)
                remain.push_back(vec[i]);
            print_plan(nv, rv, sv, remain);
        }
        called = true;
    }
}

namespace human_intelligence {
//    int lambda(int x) { return 1u << x; }
    int lambda(int x) {
        // return 1 * x;
        return pow(1.5, x);
    }
    // TODO: wait for some minds
}

class sum2d_t {
protected:
    bool inited;
    int n, m;
    vector<vector<int64_t>> src;
public:
    sum2d_t() : inited(false), n(0), m(0) {}

    sum2d_t(int n, int m) : n(n), m(m), src(vector<vector<int64_t>>(n, vector<int64_t>(m))), inited(false) {}

    void add(int x, int y, int val) {
        assert(in_range(x, 0, n));
        assert(in_range(y, 0, m));
        assert(!inited);
        src[x][y] += val;
    }

    void calculate() {
        assert(!inited);
        inited = true;
        auto gogo = [&](int i, int j) -> int64_t {
            if (i < 0 || j < 0 || i >= n || j >= m)
                return 0;
            return src[i][j];
        };
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                src[i][j] += gogo(i - 1, j) + gogo(i, j - 1) - gogo(i - 1, j - 1);
            }
    }

    int64_t query(int i, int j) {
        assert(inited);
        assert(in_range(i, 0, n));
        assert(in_range(j, 0, m));
        return src[i][j];
    }
};

class or2d_t {
protected:
    bool inited;
    int n, m;
    vector<vector<uint32_t>> src;
public:
    or2d_t() : inited(false), n(0), m(0) {}

    or2d_t(int n, int m) : n(n), m(m), src(vector<vector<uint32_t>>(n, vector<uint32_t>(m))), inited(false) {}

    void set(int x, int y, int k) {
        assert(in_range(x, 0, n));
        assert(in_range(y, 0, m));
        assert(in_range(k, 0, 32));
        assert(!inited);
        src[x][y] |= 1u << k;
    }

    void calculate() {
        assert(!inited);
        inited = true;
        auto gogo = [&](int i, int j) -> uint32_t {
            if (i < 0 || j < 0 || i >= n || j >= m)
                return 0;
            return src[i][j];
        };
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                src[i][j] |= gogo(i - 1, j) | gogo(i, j - 1);
            }
    }

    uint32_t query(int i, int j) {
        assert(inited);
        assert(in_range(i, 0, n));
        assert(in_range(j, 0, m));
        return src[i][j];
    }
};

namespace main_solver {
    vector<VM_t> VM;
    vector<PG_t> PG;
    vector<node_t> NUMA;
    vector<vector<vector<vector<node_t>>>> resources;
    vector<vector<vector<node_t>>> pm_resources;
    vector<vector<node_t>> rack_resources;
    vector<node_t> network_resources;
    vector<pair<int, int>> candidates;
    vector<vector<int>> rack_weights;
    sum2d_t vm_weights;
    position_t pos[MAX_VM];
    /// order: network-id, rack-id, partition-id, PG-id
    uint16_t PG_count_in_partition[MAX_N][MAX_R][MAX_K][MAX_REQ];
    /// order: network-id, rack-id, PM-id, PG-id
    uint16_t PG_count_in_PM[MAX_N][MAX_R][MAX_S][MAX_REQ];
    /// order: network-id, rack-id, PM-id
    uint16_t PM_count[MAX_N][MAX_R][MAX_S];
    /// order: network-id, rack-id
    uint16_t rack_count[MAX_N][MAX_R];
    /// order: PG-id
    uint64_t PG_count[MAX_REQ];
    /// the bitmasks of network [0], rack [1] and placement group [2]
    uint16_t partitions_bitmask[MAX_N][MAX_R][MAX_REQ];
    /// if the given placement group has been assigned to a specific network
    int PG_network_id[MAX_REQ];
    /// if the given placement group has been assigned to a specific rack
    int PG_rack_id[MAX_REQ];
    set<int> vm_id_in_PG[MAX_REQ];

    void set_unsync() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
    }

    void read_all() {
        cin >> N >> R >> S >> K;
        NUMA = vector<node_t>(K);
        for (int i = 0; i < K; ++i) {
            cin >> NUMA[i].cpu >> NUMA[i].memory;
        }
        cin >> F;
        VM = vector<VM_t>(F);
        for (int i = 0; i < F; ++i) {
            cin >> VM[i].n >> VM[i].cpu >> VM[i].memory;
        }

    }

    void set_groups_info() {
        resources = vector(N, vector(R, vector(S, vector(K, node_t()))));
        pm_resources = vector(N, vector(R, vector(S, node_t())));
        rack_resources = vector(N, vector(R, node_t()));
        network_resources = vector(N, node_t());
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < R; ++j)
                candidates.emplace_back(i, j);
        shuffle(candidates.begin(), candidates.end(), rng);
    }


    void update_values(int l, int r) {
        for (int network_id = l; network_id < r; ++network_id) {
            int64_t network_val = 0;
            for (int rack_id = 0; rack_id < R; ++rack_id) {
                int64_t rack_val = 0;
                for (int pm_id = 0; pm_id < S; ++pm_id) {
                    int64_t pm_val = 0;
                    for (int node_id = 0; node_id < K; ++node_id) {
                        resources[network_id][rack_id][pm_id][node_id].update_value();
                        int64_t val = resources[network_id][rack_id][pm_id][node_id].val;
                        pm_val += val;
                        rack_val += val;
                        network_val += val;
                    }
                    pm_resources[network_id][rack_id][pm_id].val = pm_val;
                }
                rack_resources[network_id][rack_id].val = rack_val;
            }
            network_resources[network_id].val = network_val;
        }
    }
    void update_values() {
        update_values(0, N - 1);
    }

    void set_VMs_weights() {
        vm_weights = sum2d_t(MAX_CPU + 1, MAX_MEMORY + 1);
        for (int k = 0; k < F; ++k) {
            auto &vm = VM[k];
            // if (vm.n != 2) {
            //     continue;
            // }
            int cpu = vm.cpu, memory = vm.memory;
            for (int i = 1; i * cpu <= MAX_CPU && i * memory <= MAX_MEMORY; ++i) {
                vm_weights.add(i * cpu, i * memory, human_intelligence::lambda(i));
            }
        }
        vm_weights.calculate();
        global_get_value = [&](int cpu, int memory) -> int64_t {
            return cpu + memory;
        };
        for (int network_id = 0; network_id < N; ++network_id) {
            for (int rack_id = 0; rack_id < R; ++rack_id) {
                for (int pm_id = 0; pm_id < S; ++pm_id) {
                    for (int numa_id = 0; numa_id < K; ++numa_id) {
                        auto machine = node_t(NUMA[numa_id].cpu, NUMA[numa_id].memory);
                        machine.update_value();
                        resources[network_id][rack_id][pm_id][numa_id] = machine;
                        pm_resources[network_id][rack_id][pm_id] += machine;
                        rack_resources[network_id][rack_id] += machine;
                        network_resources[network_id] += machine;
                    }
                }
            }
        }
        update_values();
    }

    void set_racks_weights() {
        rack_weights = vector(N, vector<int>(R));
        for (int network_id = 0; network_id < N; ++network_id)
            for (int rack_id = 0; rack_id < R; ++rack_id) {
                rack_weights[network_id][rack_id] = network_id * R + rack_id;
            }
    }

    void init() {
        set_groups_info();
        set_VMs_weights();
        set_racks_weights();
    }

    bool can_occupy(int constraint, uint32_t bitmask) {
        if (constraint == 0)
            return true;
        if ((bitmask & ~(1u << constraint)) == 0)
            return true;
        return false;
    }

    void create_placement_group(int j, int k, int a, int n, int r) {
        assert(PG.size() == j);
        PG.emplace_back(k, a, n, r);
    }

    void update_infomap(VM_t &object, int network_id, int rack_id, int pm_id, int node_0 = -1, int node_1 = -1) {
        if (object.n == 1) {
            assert(node_1 == -1);
        }
        if (object.n == 2) {
            assert(node_1 != -1);
        }
        if (node_0 != -1) {
            resources[network_id][rack_id][pm_id][node_0] -= object;
        }
        if (node_1 != -1) {
            resources[network_id][rack_id][pm_id][node_1] -= object;
        }
        auto weighted_object = object * object.n;
        pm_resources[network_id][rack_id][pm_id] -= weighted_object;
        rack_resources[network_id][rack_id] -= weighted_object;
        network_resources[network_id] -= weighted_object;
        update_values(network_id, network_id + 1);
    }

    void update_resources_pool(position_t &cur, int network_id, int rack_id, int pm_id) {
        ++PG_count[cur.pg_id];
        ++PG_count_in_partition[network_id][rack_id][cur.partition_id][cur.pg_id];
        ++PG_count_in_PM[network_id][rack_id][pm_id][cur.pg_id];
        ++PM_count[network_id][rack_id][pm_id];
        ++rack_count[network_id][rack_id];
        partitions_bitmask[network_id][rack_id][cur.pg_id] |= 1u << cur.partition_id;
        auto pg = PG[cur.pg_id];
        if (pg.network_affinity && PG_count[cur.pg_id] == 1) {
            PG_network_id[cur.pg_id] = network_id;
        }
        if (pg.rack_affinity && PG_count[cur.pg_id] == 1) {
            PG_rack_id[cur.pg_id] = rack_id;
        }
        vm_id_in_PG[cur.pg_id].insert(cur.id);
    }

    bool check_PG_rack(int id) {
        int network_id = PG_network_id[id], rack_id = PG_rack_id[id];
        for(auto i : vm_id_in_PG[id]) {
            if(pos[i].network_id != network_id) return false;
            if(pos[i].rack_id != rack_id) return false;
        }
        return true;
    }
    bool check_PG_network(int id) {
        int network_id = PG_network_id[id];
        for(auto i : vm_id_in_PG[id]) {
            if(pos[i].network_id != network_id) return false;
        }
        return true;
    }
    bool insert(int network_id, int rack_id, int id, vector<vector<int>> &result, bool check_soft_PM_anti_affinity) {
        auto &cur = pos[id];
        // TODO: add some greedy policy here
        vector<int> vs(S);
        iota(vs.begin(), vs.end(), 0);
        int pg_id = pos[id].pg_id;
        auto vm = VM[cur.vm_id];
        auto compare = [&](int x, int y) -> bool {
            int left_cnt = PG_count_in_PM[network_id][rack_id][x][pg_id];
            int right_cnt = PG_count_in_PM[network_id][rack_id][y][pg_id];
            int cond = PG[pg_id].a;
            if(cond != 1) {
                if (left_cnt < cond && right_cnt >= cond)
                    return true;
                if (left_cnt >= cond && right_cnt < cond)
                    return false;
            }
            if (VM[cur.vm_id].n == 1) {
                if (K == 2) {
                    auto &L = resources[network_id][rack_id][x];
                    auto &R = resources[network_id][rack_id][y];
                    auto L0 = L[0], L1 = L[1];
                    auto R0 = R[0], R1 = R[1];
                    if (L0 < L1) swap(L0, L1);
                    if (R0 < R1) swap(R0, R1);
                    bool left_ok = can_fit(L0 * 3 - L1 * 2, vm);
                    bool right_ok = can_fit(R0 * 3 - R1 * 2, vm);
                    if (left_ok != right_ok)
                        return left_ok > right_ok;
                } else {
                    auto &L = resources[network_id][rack_id][x];
                    auto &R = resources[network_id][rack_id][y];
                    auto L0 = L[0], L1 = L[1], L2 = L[2], L3 = L[3];
                    auto R0 = R[0], R1 = R[1], R2 = R[2], R3 = R[3];
                    if (L0 < L1) swap(L0, L1);
                    if (L2 < L3) swap(L2, L3);
                    if (R0 < R1) swap(R0, R1);
                    if (R2 < R3) swap(R2, R3);
                    bool left_ok = can_fit(L0 * 3 - L1 * 2, vm) || can_fit(L2 * 3 - L3 * 2, vm);
                    bool right_ok = can_fit(R0 * 3 - R1 * 2, vm) || can_fit(R2 * 3 - R3 * 2, vm);
                    if (left_ok != right_ok)
                        return left_ok > right_ok;
                }
            }
            else {
                if(K == 2) {
                    // auto &L = resources[network_id][rack_id][x];
                    // auto &R = resources[network_id][rack_id][y];
                    // auto L0 = L[0], L1 = L[1];
                    // auto R0 = R[0], R1 = R[1];
                    // if (L0 < L1) swap(L0, L1);
                    // if (R0 < R1) swap(R0, R1);
                    // bool left_ok = can_fit(L0 - L1, vm);
                    // bool right_ok = can_fit(R0 - R1, vm);
                    // if (left_ok != right_ok)
                    //     return left_ok < right_ok;
                }
                else {
                    // auto &L = resources[network_id][rack_id][x];
                    // auto &R = resources[network_id][rack_id][y];
                    // auto L0 = L[0], L1 = L[1], L2 = L[2], L3 = L[3];
                    // auto R0 = R[0], R1 = R[1], R2 = R[2], R3 = R[3];
                    // if (L0 < L1) swap(L0, L1);
                    // if (L2 < L3) swap(L2, L3);
                    // if (R0 < R1) swap(R0, R1);
                    // if (R2 < R3) swap(R2, R3);
                    // bool left_ok = can_fit(L0 - L1, vm) || can_fit(L2 - L3, vm);
                    // bool right_ok = can_fit(R0 - R1, vm) || can_fit(R2 - R3, vm);
                    // if (left_ok != right_ok)
                    //     return left_ok < right_ok;
                }
            }
            return pm_resources[network_id][rack_id][x] < pm_resources[network_id][rack_id][y];
        };
        stable_sort(vs.begin(), vs.end(), compare);
        // if (PG[pg_id].a == 1) {
        //     stable_sort(vs.begin(), vs.end(), [&](int x, int y) -> bool {
        //         int lhs = PG_count_in_PM[network_id][rack_id][x][pg_id];
        //         int rhs = PG_count_in_PM[network_id][rack_id][y][pg_id];
        //         lhs = min(lhs, PG[pg_id].a);
        //         rhs = min(rhs, PG[pg_id].a);
        //         return lhs < rhs;
        //     });
        // }
        int n_vm_cores = VM[cur.vm_id].n;
        int network_affinity = PG[cur.pg_id].network_affinity;
        int rack_affinity = PG[cur.pg_id].rack_affinity;
        if (PG_count[cur.pg_id] != 0) {
            assert(PG_count[cur.pg_id] >= 0);
            if (network_affinity == HARD_CONSTRAINT && network_id != PG_network_id[cur.pg_id]) {
                return false;
            }
            if (rack_affinity == HARD_CONSTRAINT && rack_id != PG_rack_id[cur.pg_id]) {
                return false;
            }
            if (!can_occupy(cur.partition_id, partitions_bitmask[network_id][rack_id][cur.pg_id])) {
                return false;
            }
        }
        int pos = 0;
        auto prediction = [&](const node_t &z) {
            return vm_weights.query(z.cpu, z.memory);
        };
        function<bool(const int &, const int &)> compare_via_resources;
        if (K == 2) {
            compare_via_resources = [&](int x, int y) -> bool {
                auto &v = resources[network_id][rack_id][pos];
                return v[x] > v[y];
            };
        } else {
            compare_via_resources = [&](int x, int y) -> bool {
                auto &v = resources[network_id][rack_id][pos];
                int a0 = x, a1 = x ^ 1;
                int b0 = y, b1 = y ^ 1;
                auto L0 = v[a0], L1 = v[a1], R0 = v[b0], R1 = v[b1];
                int64_t VL0 = prediction(L0), VL1 = prediction(L1), VL2 = prediction(L0 - vm);
                int64_t VR0 = prediction(R0), VR1 = prediction(R1), VR2 = prediction(R0 - vm);
                int64_t lf = min(VL0, VL1) - min(VL1, VL2);
                int64_t rf = min(VR0, VR1) - min(VR1, VR2);

                if (lf != rf)
                    return lf < rf;

                long double pL = min(1.0 * v[x].cpu / vm.cpu, 1.0 * v[x].memory / vm.memory);
                long double pR = min(1.0 * v[y].cpu / vm.cpu, 1.0 * v[y].memory / vm.memory);
                return pL > pR;
            };
        }
        for (int pm_id: vs) {
            if (check_soft_PM_anti_affinity && PG[pg_id].a && PG_count_in_PM[network_id][rack_id][pm_id][pg_id] >= PG[pg_id].a) {
                continue;
            }
            pos = pm_id;
            vector<int> OK(K), candidates;
            int matched = 0;
            for (int node_id = 0; node_id < K; ++node_id) {
                if (can_fit(resources[network_id][rack_id][pm_id][node_id], VM[cur.vm_id])) {
                    ++matched;
                    candidates.push_back(node_id);
                    OK[node_id] = 1;
                }
            }
            if (matched < VM[cur.vm_id].n)
                continue;
            shuffle(candidates.begin(), candidates.end(), rng);
            stable_sort(candidates.begin(), candidates.end(), compare_via_resources);
            auto &object = VM[cur.vm_id];
            int node_0 = (candidates.size() >= 1 ? candidates.at(0) : -1);
            int node_1 = (candidates.size() >= 2 ? candidates.at(1) : -1);
            if (n_vm_cores == 1) {
                update_infomap(object, network_id, rack_id, pm_id, node_0);
                cur.set_position(network_id, rack_id, pm_id, node_0);
                result.push_back({network_id, rack_id, pm_id, node_0});
                update_resources_pool(cur, network_id, rack_id, pm_id);
            } else {
                if(K == 4) {
                    if(OK[0] && OK[1] && (node_0 <= 1 || node_1 <= 1)) node_0 = 0, node_1 = 1;
                    if(OK[2] && OK[3] && (node_0 > 1 || node_1 > 1)) node_0 = 2, node_1 = 3;
                }
                update_infomap(object, network_id, rack_id, pm_id, node_0, node_1);
                cur.set_position(network_id, rack_id, pm_id, node_0, node_1);
                result.push_back({network_id, rack_id, pm_id, node_0, node_1});
                update_resources_pool(cur, network_id, rack_id, pm_id);
            }
            return true;
        }
        return false;
    }

    void delete_virtual_machine(int id) {
        auto &cur = pos[id];
        int vm_id = cur.vm_id;
        int network_id = cur.network_id;
        int rack_id = cur.rack_id;
        int pm_id = cur.pm_id;
        int pg_id = cur.pg_id;
        int node_0 = cur.node_0;
        int node_1 = cur.node_1;
        int partition_id = cur.partition_id;
        --PG_count_in_partition[network_id][rack_id][partition_id][pg_id];
        --PG_count_in_PM[network_id][rack_id][pm_id][pg_id];
        --PG_count[pg_id];
        --PM_count[network_id][rack_id][pm_id];
        --rack_count[network_id][rack_id];

        const auto &vm = VM[vm_id];
        auto object = VM[vm_id] * VM[vm_id].n;
        network_resources[network_id] += object;
        rack_resources[network_id][rack_id] += object;
        pm_resources[network_id][rack_id][pm_id] += object;
        resources[network_id][rack_id][pm_id][node_0] += vm;
        if (vm.n > 1) {
            assert(node_1 != -1);
            resources[network_id][rack_id][pm_id][node_1] += vm;
        }
        if (!PG_count_in_partition[network_id][rack_id][partition_id][pg_id]) {
            assert(partitions_bitmask[network_id][rack_id][pg_id] >> partition_id & 1);
            partitions_bitmask[network_id][rack_id][pg_id] ^= 1 << partition_id;
        }
        assert(vm_id_in_PG[pg_id].count(id) != 0);
        vm_id_in_PG[pg_id].erase(id);
        update_values(network_id, network_id + 1);
    }

    void delete_virtual_machine(vector<int> id) {
        for (int x: id) {
            delete_virtual_machine(x);
        }
    }

    bool check_pg_soft_constraints(int pg_id) {
        auto &pg = PG[pg_id];
        int network_id = -1;
        int rack_id = -1;
        for (int id : vm_id_in_PG[pg_id]) {
            auto &cur = pos[id];
            if (PG_count_in_PM[cur.network_id][cur.rack_id][cur.pm_id][cur.pg_id] > pg.a)
                return false;
            if (pg.network_affinity >= SOFT_CONSTRAINT) {
                if (network_id == -1) {
                    network_id = cur.network_id;
                }
                else if (network_id != cur.network_id) {
                    return false;
                }
            }
            if (pg.rack_affinity >= SOFT_CONSTRAINT) {
                if (rack_id == -1) {
                    rack_id = cur.rack_id;
                }
                else if (rack_id != cur.rack_id) {
                    return false;
                }
            }
        }
        return true;
    }

    bool is_network_possible_to_fit(int network_id, int l, int f, int j, int p, bool check_soft_PM_anti_affinity) {
        auto current = resources[network_id];
        VM_t single = VM[f];
        vector<vector<int>> cnt(R, vector(S, 0));
        int a = PG.at(j).a;
        if (a != 1) {
            // if the soft constraints is 1 (the most strict)
            // then distribute the VMs into different physical machines...
            a = 0;
        }
        auto try_place = [&]() -> bool {
            for (int rack_id = 0; rack_id < R; ++rack_id) {
                for (int pm_id = 0; pm_id < S; ++pm_id) {
                    if (check_soft_PM_anti_affinity && a > 0 &&
                        cnt[rack_id][pm_id] + PG_count_in_PM[network_id][rack_id][pm_id][j] >= a) {
                        continue;
                    }
                    if (single.n == 1) {
                        for (int node_id = 0; node_id < K; ++node_id) {
                            if (can_fit(current[rack_id][pm_id][node_id], single)) {
                                current[rack_id][pm_id][node_id] -= single;
                                ++cnt[rack_id][pm_id];
                                return true;
                            }
                        }
                    } else {
                        vector<int> candidates;
                        for (int node_id = 0; node_id < K; ++node_id) {
                            if (can_fit(current[rack_id][pm_id][node_id], single)) {
                                candidates.push_back(node_id);
                            }
                        }
                        if (candidates.size() >= 2) {
                            int node_0 = candidates.at(0);
                            int node_1 = candidates.at(1);
                            current[rack_id][pm_id][node_0] -= single;
                            current[rack_id][pm_id][node_1] -= single;
                            ++cnt[rack_id][pm_id];
                            return true;
                        }
                    }
                }
            }
            return false;
        };
        for (int count = 0; count < l; ++count) {
            if (!try_place()) {
                return false;
            }
        }
        return true;
    }

    bool is_rack_possible_to_fit(int network_id, int rack_id, int l, int f, int j, int p,
                                 bool check_soft_PM_anti_affinity) {
        auto current = resources[network_id][rack_id];
        VM_t single = VM[f];
        vector<int> cnt(S, 0);
        int a = PG.at(j).a;
        if (a != 1) {
            // if the soft constraints is 1 (the most strict)
            // then distribute the VMs into different physical machines...
            a = 0;
        }
        auto try_place = [&]() -> bool {
            for (int pm_id = 0; pm_id < S; ++pm_id) {
                if (check_soft_PM_anti_affinity && a > 0 &&
                    cnt[pm_id] + PG_count_in_PM[network_id][rack_id][pm_id][j] + single.n > a) {
                    continue;
                }
                if (single.n == 1) {
                    for (int node_id = 0; node_id < K; ++node_id) {
                        if (can_fit(current[pm_id][node_id], single)) {
                            current[pm_id][node_id] -= single;
                            ++cnt[pm_id];
                            return true;
                        }
                    }
                } else {
                    vector<int> candidates;
                    for (int node_id = 0; node_id < K; ++node_id) {
                        if (can_fit(current[pm_id][node_id], single)) {
                            candidates.push_back(node_id);
                        }
                    }
                    if (candidates.size() >= 2) {
                        int node_0 = candidates.at(0);
                        int node_1 = candidates.at(1);
                        current[pm_id][node_0] -= single;
                        current[pm_id][node_1] -= single;
                        ++cnt[pm_id];
                        return true;
                    }
                }
            }

            return false;
        };
        for (int count = 0; count < l; ++count) {
            if (!try_place()) {
                return false;
            }
        }
        return true;

    }

    void create_virtual_machine_with_hard_rack_constraints(int l, int f, int j, int p, vector<int> &id) {
        vector<vector<int>> plan;
        shuffle(candidates.begin(), candidates.end(), rng);
        vector<vector<int>> ok(N, vector<int>(R)), soft_ok(N, vector<int>(R));
        for (int network_id = 0; network_id < N; ++network_id) {
            for (int rack_id = 0; rack_id < R; ++rack_id) {
                ok[network_id][rack_id] = is_rack_possible_to_fit(network_id, rack_id, l, f, j, p, false);
                if (ok[network_id][rack_id]) {
                    soft_ok[network_id][rack_id] = is_rack_possible_to_fit(network_id, rack_id, l, f, j, p, true);
                } else {
                    soft_ok[network_id][rack_id] = false;
                }
            }
        }
        bool is_soft_ok = true;//check_pg_soft_constraints(j);
        stable_sort(candidates.begin(), candidates.end(), [&](const auto &x, const auto &y) -> bool {
            const auto &[xn, xr] = x;
            const auto &[yn, yr] = y;
            if (ok[xn][xr] != ok[yn][yr])
                return ok[xn][xr] > ok[yn][yr];
            if (is_soft_ok) {
                if (soft_ok[xn][xr] != soft_ok[yn][yr])
                    return soft_ok[xn][xr] > soft_ok[yn][yr];
            }
            return rack_resources[xn][xr] < rack_resources[yn][yr];
        });
        for (auto [x, y]: candidates) {
            bool ok = true;
            vector<int> bin;
            for (int z: id) {
                if (!insert(x, y, z, plan, true)) {
                    if (!insert(x, y, z, plan, false)) {
                        ok = false;
                        delete_virtual_machine(bin);
                        plan.clear();
                        break;
                    }
                }
                bin.push_back(z);
            }
            if (ok) {
                interaction_protocol::print_plan(plan);
                return;
            }
        }
        if (!interaction_protocol::called) {
            interaction_protocol::failed_to_place();
        }
    }

    void create_virtual_machine_with_hard_network_constraints(int l, int f, int j, int p, vector<int> &id) {
        VM_t single_machine = VM.at(f);
        auto total_cost = single_machine * l;
        vector<int> ok(N), soft_ok(N);
        for (int i = 0; i < N; ++i) {
            ok[i] = is_network_possible_to_fit(i, l, f, j, p, false);
            if (ok[i]) {
                soft_ok[i] = is_network_possible_to_fit(i, l, f, j, p, true);
            } else {
                soft_ok[i] = false;
            }
        }
        bool is_soft_ok = true;//check_pg_soft_constraints(j);
        stable_sort(candidates.begin(), candidates.end(), [&](const auto &x, const auto &y) -> bool {
            const auto &[xn, xr] = x;
            const auto &[yn, yr] = y;
            int cnt_reserved = 1;
            int x_reserved = (xn >= N - cnt_reserved);
            int y_reserved = (yn >= N - cnt_reserved);
            if (x_reserved != y_reserved)
                return x_reserved > y_reserved;
            if (ok[xn] != ok[yn])
                return ok[xn] > ok[yn];
            if (is_soft_ok) {
                if (soft_ok[xn] != soft_ok[yn])
                    return soft_ok[xn] > soft_ok[yn];
            }
			// if(xn != yn) {
			// 	return network_resources[xn] < network_resources[yn];
			// }
			// if(PG[j].rack_affinity) {
	        //     return rack_resources[xn][xr] > rack_resources[yn][yr];				
			// }
            return rack_resources[xn][xr] < rack_resources[yn][yr];
        });
        vector<vector<int>> plan;
        vector<pair<int, int>> local_candidates;
        for (auto [network_id, rack_id]: candidates) {
            if (ok[network_id]) {
                local_candidates.emplace_back(network_id, rack_id);
            }
        }
        for (int z: id) {
            bool ok = false;
            for (auto [x, y]: local_candidates) {
                if (insert(x, y, z, plan, true)) {
                    ok = true;
                    break;
                }
            }
            if(!ok) {
                for (auto [x, y]: local_candidates) {
                    if (insert(x, y, z, plan, false)) {
                        ok = true;
                        break;
                    }
                }
            }
            if (!ok) interaction_protocol::failed_to_place();
        }
        interaction_protocol::print_plan(plan);
    }

    void create_virtual_machine_ordinary_cases(int l, int f, int j, int p, vector<int> &id) {
        vector<vector<int>> plan;
        for (int z: id) {
            bool ok = false;

            auto cur = pos[z];
            int pid = cur.partition_id;
            auto compare = [&](const auto &x, const auto &y) -> bool {
                const auto &[xn, xr] = x;
                const auto &[yn, yr] = y;
                int a = PG_count_in_partition[xn][xr][pid][j];
                int b = PG_count_in_partition[yn][yr][pid][j];
                a = (a != 0);
                b = (b != 0);
                return a > b;
            };

            if (PG_count[j] == 0) {
                auto compare = [&](const auto &x, const auto &y) -> bool {
                    const auto &[xn, xr] = x;
                    const auto &[yn, yr] = y;
                    int cnt_reserved = 1;
                    int x_reserved = (xn >= N - cnt_reserved);
                    int y_reserved = (yn >= N - cnt_reserved);
                    if (x_reserved != y_reserved)
                        return x_reserved < y_reserved;

                    if (PG[j].rack_affinity == SOFT_CONSTRAINT) {
                        return rack_resources[xn][xr] > rack_resources[yn][yr];
                    }
                    if (PG[j].network_affinity == SOFT_CONSTRAINT) {
                        if (xn != yn) {
                            return network_resources[xn] > network_resources[yn];
                        }
                    }
                    return rack_resources[xn][xr] < rack_resources[yn][yr];
                };
                stable_sort(candidates.begin(), candidates.end(), compare);
            } else if (PG[j].rack_affinity == SOFT_CONSTRAINT && check_PG_rack(j)) {
                stable_sort(candidates.begin(), candidates.end(), [&](const auto &x, const auto &y) -> bool {
                    const auto &[xn, xr] = x;
                    const auto &[yn, yr] = y;
                    bool L = (xn == PG_network_id[j] && xr == PG_rack_id[j]);
                    bool R = (yn == PG_network_id[j] && yr == PG_rack_id[j]);
                    if (L != R)
                        return L > R;
                    if (L && R) {
                        return rack_resources[xn][xr] < rack_resources[yn][yr];
                    }
                    return rack_resources[xn][xr] < rack_resources[yn][yr];
                });
            } else if (PG[j].network_affinity == SOFT_CONSTRAINT && check_PG_network(j)) {
                stable_sort(candidates.begin(), candidates.end(), [&](const auto &x, const auto &y) -> bool {
                    const auto &[xn, xr] = x;
                    const auto &[yn, yr] = y;
                    bool L = (xn == PG_network_id[j]);
                    bool R = (yn == PG_network_id[j]);
                    if (L != R)
                        return L > R;
                    if (L && R) {
                        return rack_resources[xn][xr] < rack_resources[yn][yr];
                    }
                    if (xn != yn) {
                        return network_resources[xn] < network_resources[yn];
                    }
                    return rack_resources[xn][xr] < rack_resources[yn][yr];
                });
            } else {
                stable_sort(candidates.begin(), candidates.end(), [&](const auto &x, const auto &y) -> bool {
                    const auto &[xn, xr] = x;
                    const auto &[yn, yr] = y;
                    return rack_resources[xn][xr] < rack_resources[yn][yr];
                });
            }
            if (cur.partition_id != 0 && PG_count[j] > 0) {
                stable_sort(candidates.begin(), candidates.end(), compare);
            }
            for (auto [x, y]: candidates) {
                if (insert(x, y, z, plan, true)) {
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                for (auto [x, y]: candidates) {
                    if (insert(x, y, z, plan, false)) {
                        ok = true;
                        break;
                    }
                }
            }
            if (!ok) interaction_protocol::failed_to_place();
        }
        interaction_protocol::print_plan(plan);

    }

    void create_virtual_machine(int l, int f, int j, int p, vector<int> &id) {
//        cerr << "creating virtual machine: " << l << ' ' << f << ' ' << j << ' ' << p << ' ' << '\n';
        auto &pg = PG[j];
        auto &cur_vm = VM[f];
        int curID = 0;
        assert(is_valid_vm_id(f));
        for (int x : id) {
            ++curID;
            int pg_id = j;
            int vm_id = f;
            int partition_id = 0;
            if (p > 0) partition_id = p;
            else if (p == -1) partition_id = curID;
            pos[x] = position_t(x, pg_id, vm_id);
            pos[x].partition_id = partition_id;
        }
        if (pg.rack_affinity == HARD_CONSTRAINT) {
            create_virtual_machine_with_hard_rack_constraints(l, f, j, p, id);
        } else if (pg.network_affinity == HARD_CONSTRAINT) {
            create_virtual_machine_with_hard_network_constraints(l, f, j, p, id);
        } else {
            create_virtual_machine_ordinary_cases(l, f, j, p, id);
        }
    }

    void go() {
        int cnt = 0;
	    while (true) {
            int type;
            cin >> type;
            if (type == 1) {
                int j, k, a, n, r;
                cin >> j >> k >> a >> n >> r;
				cnt += a == 1;
                --j;
                create_placement_group(j, k, a, n, r);
            } else if (type == 2) {
                int l, f, j, p;
                cin >> l >> f >> j >> p;
                --j;
                --f;
                vector<int> id(l);
                for (int i = 0; i < l; ++i) {
                    cin >> id[i];
                }
                interaction_protocol::reset();
                create_virtual_machine(l, f, j, p, id);
                interaction_protocol::finish();
            } else if (type == 3) {
                int l;
                cin >> l;
                vector<int> id(l);
                for (int i = 0; i < l; ++i) {
                    cin >> id[i];
                }
                delete_virtual_machine(id);
            } else {
                break;
            }
			assert(cnt < 2);
        }
    }
}

void start(int seed) {
    rng = mt19937(seed);
    main_solver::set_unsync();
    main_solver::read_all();
    main_solver::init();
    main_solver::go();
}

int main() {
start(678727356);
}
//revision: E4AZnLNu-371