Untitled

#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

using ll = long long;

struct rect {
    ll x1, y1, x2, y2;

    void dbg() {
        debug(x1, y1, x2, y2);
    }
};

ll area(rect r) {
    return max(0LL, (r.x2 - r.x1 + 1)) * max(0LL, (r.y2 - r.y1 + 1));
}

rect inter(rect a, rect b) {
    ll x1 = max(a.x1, b.x1);
    ll x2 = min(a.x2, b.x2);
    ll y1 = max(a.y1, b.y1);
    ll y2 = min(a.y2, b.y2);
    return {x1, y1, x2, y2};
}

void test_case() {
    ll w, h, s, q;
    cin >> w >> h >> s >> q;
    vector<int> x(s), y(s);
    for (int i = 0; i < s; i++) {
        cin >> x[i] >> y[i];
    }
    int t;
    cin >> t;
    vector<ll> b(t), n(t), m(t);
    for (int i = 0; i < t; i++) {
        cin >> b[i] >> n[i] >> m[i];
        b[i]--;
    }
    auto coords = [&](int bi, ll mi) -> rect {
        ll x1 = max(1LL, x[bi] - mi);
        ll y1 = max(1LL, y[bi] - mi);
        ll x2 = min(w, x[bi] + mi);
        ll y2 = min(h, y[bi] + mi);
        return {x1, y1, x2, y2};
    };
    auto check = [&](int k, int z) -> bool {
        vector<vector<ll>> mob(4);
        for (int i = 0; i < k + (z == 0 ? 0 : 1); i++) {
            mob[b[i]].push_back(m[i]);
        }
        for (int i = 0; i < s; i++) {
            sort(mob[i].begin(), mob[i].end());
            mob[i].erase(unique(mob[i].begin(), mob[i].end()), mob[i].end());
        }
        vector<vector<ll>> a(s, vector<ll> (k + 1));
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < (int)mob[b[i]].size(); j++) {
                if (m[i] >= mob[b[i]][j]) {
                    a[b[i]][j] += n[i];
                }
            }
        }
        if (z != 0) {
            for (int j = 0; j < (int)mob[b[k]].size(); j++) {
                if (m[k] >= mob[b[k]][j]) {
                    a[b[k]][j] += z;
                }
            }
        }
        int bi[4];
        for (bi[0] = -1; bi[0] < (int)mob[0].size(); bi[0]++) {
            for (bi[1] = -1; bi[1] < (int)mob[1].size(); bi[1]++) {
                for (bi[2] = -1; bi[2] < (int)mob[2].size(); bi[2]++) {
                    for (bi[3] = -1; bi[3] < (int)mob[3].size(); bi[3]++) {
                        ll NA = 0;
                        for (int i = 1; i < (1 << s); i++) {
                            int cnt = __builtin_popcount(i);
                            rect res = {1, 1, w, h};
                            bool f = true;
                            for (int j = 0; j < s; j++) {
                                if ((i >> j) & 1) {
                                    if (bi[j] == -1) {
                                        f = false;
                                        break;
                                    }
                                    res = inter(res, coords(j, mob[j][bi[j]]));
                                }
                            }
                            if (f) {
                                NA += area(res) * (cnt % 2 ? 1 : -1);
                            }
                        }
                        ll A = (bi[0] != -1 ? a[0][bi[0]] : 0) + (bi[1] != -1 ? a[1][bi[1]] : 0) + (bi[2] != -1 ? a[2][bi[2]] : 0) + (bi[3] != -1 ? a[3][bi[3]] : 0);
                        if (A > NA * q) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    };
    int Lk = 0, Rk = t + 1;
    while (true) {
        int Mk = (Lk + Rk) / 2;
        int Lz = -1, Rz;
        if (Mk == t) {
            Rz = 1;
        } else {
            Rz = n[Mk] + 1;
            if (check(Mk, n[Mk])) {
                Lk = Mk;
                continue;
            }
            if (!check(Mk, 0)) {
                Rk = Mk;
                continue;
            }
        }
        while (Lz + 1 != Rz) {
            int Mz = (Lz + Rz) / 2;
            if (check(Mk, Mz)) {
                Lz = Mz;
            } else {
                Rz = Mz;
            }
        }
        if (Mk != t && Lz == n[Mk]) {
            Lk = Mk;
        } else if (Lz == -1) {
            Rk = Mk;
        } else {
            cout << Mk << ' ' << Lz;
            return;
        }
    }
    cout << "0 0";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef LOCAL
    freopen("mining.in", "r", stdin);
    freopen("mining.out", "w", stdout);
    #endif
    int tests = 1;
    // cin >> tests;
    while (tests--) {
        test_case();
    }
    return 0;
}