Language: C++

// Created by Nikolay Budin

#ifdef LOCAL
#  define _GLIBCXX_DEBUG
#else
#  define cerr __get_ce
#endif
#include <bits/stdc++.h>
#define ff first
#define ss second
#define szof(x) ((int)x.size())

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
int const INF = (int)1e9 + 1e3;
ll const INFL = (ll)1e18 + 1e6;
#ifdef LOCAL
	mt19937 tw(9450189);
#else
	mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
uniform_int_distribution<ll> ll_distr;
ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }

struct big_integer {
private:
    std::vector<uint32_t> number;
    void normalize();
    void negate();
    
public:
    big_integer();
    big_integer(int num);
    big_integer(ll num);
    big_integer(uint32_t num);
    big_integer(std::vector<uint32_t> const& _number);
    explicit big_integer(std::string const& s);

    ~big_integer();
    
    big_integer(big_integer const& other);

    void print() const;

    bool get_sign() const;

    size_t size() const;
    
    uint32_t operator[](size_t pos) const;

    big_integer& operator=(big_integer const& other);

    big_integer& operator+=(big_integer const& rhs);
    big_integer& operator-=(big_integer const& rhs);
    big_integer& operator*=(big_integer const& rhs);
    big_integer& operator/=(big_integer const& rhs);
    big_integer& operator%=(big_integer const& rhs);

    big_integer& operator&=(big_integer const& rhs);
    big_integer& operator|=(big_integer const& rhs);
    big_integer& operator^=(big_integer const& rhs);

    big_integer& operator<<=(int rhs);
    big_integer& operator>>=(int rhs);

    big_integer operator+() const;
    big_integer operator-() const;
    big_integer operator~() const;

    big_integer& operator++();
    big_integer operator++(int);
    big_integer& operator--();
    big_integer operator--(int);

    friend bool operator==(big_integer const& a, big_integer const& b);
    friend bool operator!=(big_integer const& a, big_integer const& b);
    friend bool operator<(big_integer const& a, big_integer const& b);
    friend bool operator>(big_integer const& a, big_integer const& b);
    friend bool operator<=(big_integer const& a, big_integer const& b);
    friend bool operator>=(big_integer const& a, big_integer const& b);

    friend std::string to_string(big_integer const& a);
};

bool operator==(big_integer const& num1, big_integer const& num2);
bool operator!=(big_integer const& a, big_integer const& b);
bool operator<(big_integer const& num1, big_integer const& num2);
bool operator>(big_integer const& num1, big_integer const& num2);
bool operator<=(big_integer const& num1, big_integer const& num2);
bool operator>=(big_integer const& num1, big_integer const& num2);

big_integer operator+(big_integer num1, big_integer const& num2);
big_integer operator-(big_integer num1, big_integer const& num2);
big_integer operator*(big_integer a, big_integer const& b);
big_integer operator/(big_integer a, big_integer const& b);
big_integer operator%(big_integer a, big_integer const& b);

big_integer operator&(big_integer num1, big_integer const& num2);
big_integer operator|(big_integer num1, big_integer const& num2);
big_integer operator^(big_integer num1, big_integer const& num2);

big_integer operator<<(big_integer a, int b);
big_integer operator>>(big_integer a, int b);

std::string to_string(big_integer const& a);
std::ostream& operator<<(std::ostream& s, big_integer const& a);

const big_integer TEN(10), ZERO(0);
const uint64_t MASK = (((uint64_t) 1 << 32) - 1);

void big_integer::normalize() {
    //assert(number.back() == 0 || number.back() == MASK);
    while (number.size() > 1 && number[number.size() - 2] == number.back()) {
        number.pop_back();
    }
}

void big_integer::negate() {
    for (auto& num: number) {
        num = ~num;
    }
    operator+=(big_integer(1));
}

big_integer::big_integer() {
    number = {0};
}

big_integer::big_integer(int num) {
    number = {(uint32_t) num};
    if (num > 0) {
        number.push_back(0);
    }
    if (num < 0) {
        number.push_back((uint32_t) -1);
    }
    normalize();
}

big_integer::big_integer(uint32_t num) {
    number = {num, 0};
}

big_integer::big_integer(ll num) {
    number = {(uint32_t) num, (uint32_t) (num >> 32)};
    if (num > 0) {
        number.push_back(0);
    }
    if (num < 0) {
        number.push_back((uint32_t) -1);
    }
    normalize();
}

big_integer::big_integer(std::vector<uint32_t> const& _number) {
    number = _number;
    while (number.size() > 1 && number[number.size() - 2] == number.back()) {
        number.pop_back();
    }
}

big_integer::big_integer(std::string const& s) {
    number = {0};
    big_integer tp(1);
    bool sign = 0;
    if (s[0] == '-') {
        sign = 1;
    }
    
    for (size_t i = s.size() - 1; ~i; --i) {
        if ('0' <= s[i] && s[i] <= '9') {
            operator+=(tp * big_integer(s[i] - '0'));
            tp *= TEN;
        }
    }

    if (sign) {
        negate();
    }
}

big_integer::~big_integer() {
}

big_integer::big_integer(big_integer const& other) {
    number = other.number;
}

void big_integer::print() const {
    for (auto num: number) {
        std::cerr << num << " ";
    }
    std::cerr << std::endl;
}

bool big_integer::get_sign() const {
    return number.back();
}

size_t big_integer::size() const {
    return number.size();
}

uint32_t big_integer::operator[](size_t pos) const {
    //assert(number.size());
    return number[std::min(pos, number.size() - 1)];
}

big_integer& big_integer::operator=(big_integer const& other) {
    number = other.number;
    return *this;
}

big_integer& big_integer::operator+=(big_integer const& rhs) {
    std::vector<uint32_t> v;
    size_t c = 0;
    uint64_t now = 0;
    while (c <= size() || c <= rhs.size()) {
        now += operator[](c);
        now += rhs[c];
        v.push_back(now & MASK);
        now >>= 32;
        ++c;
    }
    number = v;
    normalize();
    return *this;
}

big_integer& big_integer::operator-=(big_integer const& rhs) {
    std::vector<uint32_t> v;
    size_t c = 0;
    uint64_t now = 0;
    while (c <= size() || c <= rhs.size()) {
        now += rhs[c];
        v.push_back(operator[](c) - now);
        if (operator[](c) >= now) {
            now = 0;
        } else {
            now = 1;
        }
        ++c;
    }
    number = v;
    normalize();
    return *this;
}

big_integer& big_integer::operator*=(big_integer const& rhs) {
    bool sign = get_sign() ^ rhs.get_sign();
    big_integer a = *this;
    if (a.get_sign() == 1) {
        a.negate();
    }
    big_integer b = rhs;
    if (b.get_sign() == 1) {
        b.negate();
    }

    std::vector<std::pair<uint64_t, uint64_t>> v(a.size() + b.size() - 1);
    for (size_t i = 0; i < a.size(); ++i) {
        for (size_t j = 0; j < b.size(); ++j) {
            uint64_t tmp = (uint64_t) a[i] * b[j];
            v[i + j].first += tmp & (((uint64_t) 1 << 32 ) - 1);
            if (i + j + 1 < v.size()) {
                v[i + j + 1].second += tmp >> 32;
            }
        }
    }
    number = std::vector<uint32_t>();
    uint64_t now = 0;
    for (size_t i = 0; i < v.size(); ++i) {
        now += v[i].first;
        now += v[i].second;
        number.push_back(now & MASK);
        now >>= 32;
    }
    normalize();
    if (sign) {
        negate();
    }
    return *this;
}

big_integer& big_integer::operator/=(big_integer const& rhs) {
    bool sign = get_sign() ^ rhs.get_sign();
    if (get_sign() == 1) {
        negate();
    }
    big_integer b = rhs;
    if (b.get_sign() == 1) {
        b.negate();
    }
    
    if (*this < b) {
        number = {0};
        return *this;
    }

    std::vector<uint32_t> v(size() - b.size() + 2);
    for (size_t i = size() - b.size(); ~i; --i) {
        uint64_t l = 0, r = (uint64_t) 1 << 32;
        while (r - l > 1) {
            uint32_t mid = l + (r - l) / 2;
            
            uint64_t now = 0;
            bool flag = true;
            for (size_t j = 0; j < b.size(); ++j) {
                now += (uint64_t) b[j] * mid;
                if ((now & MASK) != number[i + j]) {
                    flag = (number[i + j] > (now & MASK));
                }
                now >>= 32;
            }

            if (flag) {
                l = mid;
            } else {
                r = mid;
            }
        }
        
        uint64_t now = 0, nowd = 0;
        for (size_t j = 0; j < b.size(); ++j) {
            now += (uint64_t) b[j] * l;
            nowd += now & MASK;
            now >>= 32;
            if (nowd <= number[i + j]) {
                number[i + j] -= nowd;
                nowd = 0;
            } else {
                number[i + j] -= nowd;
                nowd = 1;
            }
        }
        v[i] = l;
    }

    number = v;
    normalize();
    if (sign) {
        negate();
    }
    return *this;
}

big_integer& big_integer::operator%=(big_integer const& rhs) {
    bool sign = get_sign();
    if (get_sign() == 1) {
        negate();
    }
    big_integer b = rhs;
    if (b.get_sign() == 1) {
        b.negate();
    }
    
    if (*this < b) {
        return *this;
    }

    for (size_t i = size() - b.size(); ~i; --i) {
        uint64_t l = 0, r = (uint64_t) 1 << 32;
        while (r - l > 1) {
            uint32_t mid = l + (r - l) / 2;
            
            uint64_t now = 0;
            bool flag = true;
            for (size_t j = 0; j < b.size(); ++j) {
                now += (uint64_t) b[j] * mid;
                //prod[j] = now & MASK;
                if ((now & MASK) != number[i + j]) {
                    flag = (number[i + j] > (now & MASK));
                }
                now >>= 32;
            }

            if (flag) {
                l = mid;
            } else {
                r = mid;
            }
        }
        
        uint64_t now = 0, nowd = 0;
        for (size_t j = 0; j < b.size(); ++j) {
            now += (uint64_t) b[j] * l;
            nowd += now & MASK;
            now >>= 32;
            if (nowd <= number[i + j]) {
                number[i + j] -= nowd;
                nowd = 0;
            } else {
                number[i + j] -= nowd;
                nowd = 1;
            }
        }
    }

    normalize();
    if (sign) {
        negate();
    }
    return *this;
}

big_integer& big_integer::operator&=(big_integer const& rhs) {
    std::vector<uint32_t> v;
    size_t c = 0;
    while (c <= size() || c <= rhs.size()) {
        v.push_back(operator[](c) & rhs[c]);
        ++c;
    }
    number = v;
    normalize();
    return *this;
}

big_integer& big_integer::operator|=(big_integer const& rhs) {
    std::vector<uint32_t> v;
    size_t c = 0;
    while (c <= size() || c <= rhs.size()) {
        v.push_back(operator[](c) | rhs[c]);
        ++c;
    }
    number = v;
    normalize();
    return *this;
}

big_integer& big_integer::operator^=(big_integer const& rhs) {
    std::vector<uint32_t> v;
    size_t c = 0;
    while (c <= size() || c <= rhs.size()) {
        v.push_back(operator[](c) ^ rhs[c]);
        ++c;
    }
    number = v;
    normalize();
    return *this;
}

big_integer& big_integer::operator<<=(int rhs) {
    int d = rhs % 32;
    int tot = rhs / 32;
    std::vector<uint32_t> v;
    for (int i = 0; i < tot; ++i) {
        v.push_back(0);
    }
    size_t c = 0;
    uint32_t prev = 0;
    while (c <= size()) {
        uint32_t tmp = (operator[](c) << d) | prev;
        v.push_back(tmp);
        prev = operator[](c) >> (32 - d);
        ++c;
    }
    number = v;
    normalize();
    return *this;
}

big_integer& big_integer::operator>>=(int rhs) {
    int d = rhs % 32;
    int tot = rhs / 32;
    std::vector<uint32_t> v;
    size_t c = tot;
    do {
        uint32_t tmp = (operator[](c) >> d) | (operator[](c + 1) << (32 - d));
        v.push_back(tmp);
        ++c;
    } while (c <= size() + 1);
    number = v;
    normalize();
    return *this;
}

big_integer big_integer::operator+() const {
    big_integer ret = *this;
    return ret;
}

big_integer big_integer::operator-() const {
    big_integer ret = *this;
    ret.negate();
    return ret;
}

big_integer big_integer::operator~() const {
    std::vector<uint32_t> v;
    for (size_t i = 0; i < size(); ++i) {
        v.push_back(~number[i]);
    }
    return big_integer(v);
}

big_integer& big_integer::operator++() {
    operator+=(big_integer(1));
    return *this;
}

big_integer big_integer::operator++(int) {
    big_integer ret = *this;
    operator+=(big_integer(1));
    return ret;
}

big_integer& big_integer::operator--() {
    operator-=(big_integer(1));
    return *this;
}

big_integer big_integer::operator--(int) {
    big_integer ret = *this;
    operator-=(big_integer(1));
    return ret;
}



bool operator==(big_integer const& a, big_integer const& b) {
    return a.number == b.number;
}

bool operator!=(big_integer const& a, big_integer const& b) {
    return a.number != b.number;
}

bool operator<(big_integer const& a, big_integer const& b) {
    if (a.get_sign() != b.get_sign()) {
        return a.get_sign() > b.get_sign();
    }
    
    if (a.number.size() != b.number.size()) {
        return a.number.size() < b.number.size();
    }

    for (size_t i = a.number.size() - 1; ~i; --i) {
        if (a.number[i] != b.number[i]) {
            return a.number[i] < b.number[i];
        }
    }
    return false;
}

bool operator>(big_integer const& a, big_integer const& b) {
    return !(a == b || a < b);
}

bool operator<=(big_integer const& a, big_integer const& b) {
    return a == b || a < b;
}

bool operator>=(big_integer const& a, big_integer const& b) {
    return a == b || a > b;
}

big_integer operator+(big_integer a, big_integer const& b) {
    return a += b;
}

big_integer operator-(big_integer a, big_integer const& b) {
    return a -= b;
}

big_integer operator*(big_integer a, big_integer const& b) {
    return a *= b;
}

big_integer operator/(big_integer a, big_integer const& b) {
    return a /= b;
}

big_integer operator%(big_integer a, big_integer const& b) {
    return a %= b;
}

big_integer operator&(big_integer a, big_integer const& b) {
    return a &= b;
}

big_integer operator|(big_integer a, big_integer const& b) {
    return a |= b;
}

big_integer operator^(big_integer a, big_integer const& b) {
    return a ^= b;
}

big_integer operator<<(big_integer a, int b) {
    return a <<= b;
}
big_integer operator>>(big_integer a, int b) {
    return a >>= b;
}

std::string to_string(big_integer const& a) {
    big_integer tmp = a;
    std::string ret = "";
    bool sign = 0;
    if (tmp < ZERO) {
        tmp = -tmp;
        sign = 1;
    }
    while (tmp > ZERO) {
        big_integer dig = tmp % TEN;
        ret += '0' + dig[0];
        tmp /= TEN;
    }
    if (ret.size() == 0) {
        ret = "0";
    }
    if (sign) {
        ret += '-';
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

std::ostream& operator<<(std::ostream& s, big_integer const& a) {
    s << to_string(a);
    return s;
}

struct number {
	big_integer p, q;

	number() : p(0), q(1) {}

	number(ll num) : p(big_integer(num)), q(1) {}

	number(big_integer _p, big_integer _q) : p(_p), q(_q) {
		if (q < 0) {
			q *= -1;
			p *= -1;
		}
	}

	number operator+(number const& other) const {
		return number(p * other.q + q * other.p, q * other.q);
	}
	number operator-(number const& other) const {
		return number(p * other.q - q * other.p, q * other.q);
	}

	number operator*(number const& other) const {
		return number(p * other.p, q * other.q);
	}

	number operator/(number const& other) const {
		return number(p * other.q, q * other.p);
	}

	number& operator/=(number const& other) {
		auto tmp = *this / other;
		p = tmp.p;
		q = tmp.q;
		return *this;
	}

	number& operator-=(number const& other) {
		auto tmp = *this - other;
		p = tmp.p;
		q = tmp.q;
		return *this;
	}

	number operator-() const {
		return number(-p, q);
	}

	bool operator==(number const& other) const {
		return p * other.q == q * other.p;
	}

	bool operator<(number const& other) const {
		return p * other.q < q * other.p;
	}

	bool operator>(number const& other) const {
		return p * other.q > q * other.p;
	}
};

bool eq(number a, number b) {
	return a == b;
}

bool ls(number a, number b) {
	return a < b;
}

vector<number> simplex(vector<vector<number> > a) {
    int n = a.size() - 1;
    int m = a[0].size() - 1;
    vector<int> left(n + 1), up(m + 1);
    iota(up.begin(), up.end(), 0);
    iota(left.begin(), left.end(), m);
    auto pivot = [&](int x, int y) {
        swap(left[x], up[y]);
        number k = a[x][y];
        a[x][y] = 1;
        vector<int> vct;
        for (int j = 0; j <= m; j++) {
            a[x][j] /= k;
            if (!eq(a[x][j], 0)) vct.push_back(j);
        }
        for (int i = 0; i <= n; i++) {
            if (eq(a[i][y], 0) || i == x) continue;
            k = a[i][y];
            a[i][y] = 0;
            for (int j : vct) a[i][j] -= k * a[x][j];
        }
    };
    while (1) {
        int x = -1;
        for (int i = 1; i <= n; i++) if (ls(a[i][0], 0) && (x == -1 || a[i][0] < a[x][0])) x = i;
        if (x == -1) break;
        int y = -1;
        for (int j = 1; j <= m; j++) if (ls(a[x][j], 0) && (y == -1 || a[x][j] < a[x][y])) y = j;
        if (y == -1) assert(0); // infeasible
        pivot(x, y);
    }
    while (1) {
        int y = -1;
        for (int j = 1; j <= m; j++) if (ls(0, a[0][j]) && (y == -1 || a[0][j] > a[0][y])) y = j;
        if (y == -1) break;
        int x = -1;
        for (int i = 1; i <= n; i++) if (ls(0, a[i][y]) && (x == -1 || a[i][0] / a[i][y] < a[x][0] / a[x][y])) x = i;
        if (x == -1) assert(0); // unbounded
        pivot(x, y);
    }
    vector<number> ans(m + 1);
    for (int i = 1; i <= n; i++) if (left[i] <= m) ans[left[i]] = a[i][0];
    ans[0] = -a[0][0];
    return ans;
}
// j=1..m: x[j]>=0
// i=1..n: sum(j=1..m) A[i][j]*x[j] <= A[i][0]
// max sum(j=1..m) A[0][j]*x[j]
// res[0] is answer
// res[1..m] is certificate

void solve() {
	int n;
	cin >> n;
	vector<vector<number>> matr;
	vector<pii> coords;
	matr.push_back(vector<number>(n + 1));
	for (int i = 0; i < n; ++i) {
		int x, y;
		ll w;
		cin >> x >> y >> w;
		matr[0][i + 1] = w;
		coords.push_back({x, y});
		matr.push_back(vector<number>(n + 1));
		matr.back()[0] = 1;
		matr.back()[i + 1] = 1;
	}

	int m;
	cin >> m;
	for (int i = 0; i < m; ++i) {
		char t;
		int a, b;
		cin >> t >> a >> b;
		matr.push_back(vector<number>(n + 1));
		matr.back()[0] = b;
		if (t == 'L') {
			for (int j = 0; j < n; ++j) {
				if (coords[j].ff <= a) {
					matr.back()[j + 1] = 1;
				}
			}
		} else if (t == 'R') {
			for (int j = 0; j < n; ++j) {
				if (coords[j].ff >= a) {
					matr.back()[j + 1] = 1;
				}
			}
		} else if (t == 'D') {
			for (int j = 0; j < n; ++j) {
				if (coords[j].ss <= a) {
					matr.back()[j + 1] = 1;
				}
			}
		} else if (t == 'U') {
			for (int j = 0; j < n; ++j) {
				if (coords[j].ss >= a) {
					matr.back()[j + 1] = 1;
				}
			}
		}
	}

	auto res = simplex(matr);
	cout << res[0].p << "\n";
}


int main() {
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed;
#endif
	cout << setprecision(15) << fixed;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int test_count = 1;
	// cin >> test_count;
	for (int test = 1; test <= test_count; ++test) {
		solve();
	}
	
#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}


Compiler output:
/usr/bin/ld: /tmp/cco8RU5d.o: warning: relocation against `_ZSt8__get_ce' in read-only section `.text'
/usr/bin/ld: /tmp/cco8RU5d.o: in function `big_integer::print() const':
a.cc:(.text+0x7d1): undefined reference to `std::__get_ce'
/usr/bin/ld: a.cc:(.text+0x822): undefined reference to `std::__get_ce'
/usr/bin/ld: warning: creating DT_TEXTREL in a PIE
collect2: error: ld returned 1 exit status