結果
| 問題 |
No.3207 Digital Font
|
| コンテスト | |
| ユーザー |
 Rubikun
|
| 提出日時 | 2025-07-18 23:25:39 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 737 ms / 3,000 ms |
| コード長 | 39,277 bytes |
| コンパイル時間 | 4,776 ms |
| コンパイル使用メモリ | 261,700 KB |
| 実行使用メモリ | 22,740 KB |
| 最終ジャッジ日時 | 2025-07-18 23:26:02 |
| 合計ジャッジ時間 | 22,398 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 38 |
ソースコード
// https://judge.yosupo.jp/submission/188674
#include <bits/stdc++.h>
using namespace std;
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>
#include <array>
#include <cstdint>
#include <cstring>
#include <string>
#include <limits>
#include <utility>
#include <unistd.h>
namespace suisen {
namespace internal::fast_io {
template <typename T> struct is_container {
template <typename T2> static auto test(T2 t) -> decltype(++t.begin() != t.end(), *t.begin(), std::true_type{});
static std::false_type test(...);
public:
static constexpr bool value = decltype(test(std::declval<T>()))::value;
};
template <typename T> constexpr bool is_container_v = is_container<T>::value;
template <typename T> using is_integral = std::disjunction<std::is_integral<T>, std::is_same<T, __int128_t>, std::is_same<T, __uint128_t>>;
template <typename T> constexpr bool is_integral_v = is_integral<T>::value;
template <typename T> using is_signed = std::disjunction<std::is_signed<T>, std::is_same<T, __int128_t>>;
template <typename T> constexpr bool is_signed_v = is_signed<T>::value;
template <typename T> using is_unsigned = std::disjunction<std::is_unsigned<T>, std::is_same<T, __uint128_t>>;
template <typename T> constexpr bool is_unsigned_v = is_unsigned<T>::value;
template <typename T> struct make_unsigned : std::make_unsigned<T> {};
template <> struct make_unsigned<__int128_t> { using type = __uint128_t; };
template <> struct make_unsigned<__uint128_t> { using type = __uint128_t; };
template <typename T> using make_unsigned_t = typename make_unsigned<T>::type;
template <typename T> struct bit_num {
static constexpr int value = std::numeric_limits<make_unsigned_t<T>>::digits;
};
template <> struct bit_num<__int128_t> { static constexpr int value = 128; };
template <> struct bit_num<__uint128_t> { static constexpr int value = 128; };
template <typename T> constexpr int bit_num_v = bit_num<T>::value;
template <int fd>
struct FastIn {
template <typename T>
FastIn& operator>>(T& v) { return _read(v), * this; }
private:
struct {
FastIn<fd> &self;
template <typename T> operator T() const { T x; self >> x; return x; }
} const self { *this };
public:
const auto& read() { return self; }
template <typename ...Args>
void read(Args &...args) { ((*this >> args), ...); }
private:
static constexpr int IBUF_SIZE = 1 << 20;
char ibuf[IBUF_SIZE];
char* ibuf_ptr = ibuf, * ibuf_ptr_r = ibuf;
void _load() {
if (ibuf_ptr == ibuf + IBUF_SIZE) ibuf_ptr = ibuf;
ibuf_ptr_r = ibuf_ptr + ::read(fd, ibuf_ptr, IBUF_SIZE - (ibuf_ptr - ibuf));
}
char _nextchar() {
if (ibuf_ptr == ibuf_ptr_r) _load();
return *ibuf_ptr++;
}
void _read(char& c) { do c = _nextchar(); while (not std::isgraph(c)); }
template <typename T, std::enable_if_t<is_integral_v<T>, std::nullptr_t> = nullptr>
void _read(T& x) {
char c;
_read(c);
if (c == '-') {
using U = make_unsigned_t<T>;
U ux;
_read(ux), x = -ux;
return;
}
if (not std::isdigit(c)) throw - 1;
x = 0;
do x = x * 10 + (std::exchange(c, _nextchar()) - '0'); while (std::isdigit(c));
}
template <typename T, std::enable_if_t<is_container_v<T>, std::nullptr_t> = nullptr>
void _read(T& x) { for (auto& e : x) _read(e); }
void _read(std::string& x) {
x.clear();
char c;
_read(c);
do x += std::exchange(c, _nextchar()); while (std::isgraph(c));
}
};
struct PrecalcInts {
static constexpr int LOG_B = 4;
static constexpr int B = 10000;
char str[B][LOG_B];
constexpr PrecalcInts() : str() {
for (int i = 0; i < B; ++i) {
for (int j = LOG_B, v = i; j--; v /= 10) str[i][j] = '0' + (v % 10);
}
}
} constexpr pre;
template <int fd>
struct FastOut {
~FastOut() { flush(); }
template <typename T>
FastOut& operator<<(const T& v) { return _write(v), * this; }
template <typename Head, typename ...Tails>
void print(Head&& head, Tails &&...tails) {
*this << head, ((*this << ' ' << tails), ...);
}
template <typename ...Args>
void println(Args &&...args) {
if constexpr (sizeof...(Args)) print(std::forward<Args>(args)...);
*this << '\n';
}
void flush() {
ssize_t wt = ::write(fd, obuf, obuf_ptr - obuf);
if (wt != obuf_ptr - obuf) throw - 1;
obuf_ptr = obuf;
}
private:
static constexpr int OBUF_SIZE = 1 << 20;
char obuf[OBUF_SIZE];
char* obuf_ptr = obuf;
void _write(char c) {
if (obuf_ptr == obuf + OBUF_SIZE) flush();
*obuf_ptr++ = c;
}
template <typename T, std::enable_if_t<is_integral_v<T>, std::nullptr_t> = nullptr>
void _write(T x) {
make_unsigned_t<T> ux = x;
if constexpr (is_signed_v<T>) {
if (x < 0) return _write('-'), _write(-ux);
}
if (obuf_ptr + 50 > obuf + OBUF_SIZE) flush();
int digits = _digits(ux);
char* nxt_obuf_ptr = obuf_ptr + digits;
for (; digits >= pre.LOG_B; digits -= pre.LOG_B) {
::memcpy(obuf_ptr + digits - pre.LOG_B, pre.str[ux % pre.B], pre.LOG_B);
ux /= pre.B;
}
::memcpy(obuf_ptr, pre.str[ux] + pre.LOG_B - digits, digits);
obuf_ptr = nxt_obuf_ptr;
}
template <typename T, std::enable_if_t<is_container_v<T>, std::nullptr_t> = nullptr>
void _write(const T& x) {
bool insert_delim = false;
for (auto it = x.begin(); it != x.end(); ++it) {
if (std::exchange(insert_delim, true)) _write(' ');
_write(*it);
}
}
void _write(const std::string& x) {
for (char c : x) _write(c);
}
static constexpr std::array<int, 128> DIGITS_POW2 = []{
std::array<int, 128> table{};
for (int i = 0; i < 128; ++i) {
for (__uint128_t v = __uint128_t(1) << i; v; v /= 10) ++table[i];
}
return table;
}();
static constexpr std::array<__uint128_t, 39> POW10 = []{
std::array<__uint128_t, 39> table{};
table[0] = 1;
for (int i = 1; i < 39; ++i) table[i] = table[i - 1] * 10;
return table;
}();
template <typename U, std::enable_if_t<bit_num_v<U> == 128, std::nullptr_t> = nullptr>
static constexpr int _digits(U x) {
if (x == 0) return 1;
const int res = DIGITS_POW2[(x >> 64) ? 127 - __builtin_clzll(x >> 64) : 63 - __builtin_clzll(x)];
return res + ((res != int(POW10.size())) and (x >= POW10[res]));
}
template <typename U, std::enable_if_t<bit_num_v<U> == 64, std::nullptr_t> = nullptr>
static constexpr int _digits(U x) {
if (x == 0) return 1;
const int res = DIGITS_POW2[63 - __builtin_clzll(x)];
return res + (x >= POW10[res]);
}
template <typename U, std::enable_if_t<bit_num_v<U> == 32, std::nullptr_t> = nullptr>
static constexpr int _digits(U x) {
if (x == 0) return 1;
const int res = DIGITS_POW2[31 - __builtin_clz(x)];
return res + (x >= uint64_t(POW10[res]));
}
};
}
using internal::fast_io::FastIn;
using internal::fast_io::FastOut;
FastIn<STDIN_FILENO> fast_in;
FastOut<STDOUT_FILENO> fast_out;
FastOut<STDERR_FILENO> fast_err;
}
#include <vector>
#include <iostream>
#include <type_traits>
namespace suisen {
template <typename ...Constraints> using constraints_t = std::enable_if_t<std::conjunction_v<Constraints...>, std::nullptr_t>;
template <typename T, typename = std::nullptr_t> struct bitnum { static constexpr int value = 0; };
template <typename T> struct bitnum<T, constraints_t<std::is_integral<T>>> { static constexpr int value = std::numeric_limits<std::make_unsigned_t<T>>::digits; };
template <typename T> static constexpr int bitnum_v = bitnum<T>::value;
template <typename T, size_t n> struct is_nbit { static constexpr bool value = bitnum_v<T> == n; };
template <typename T, size_t n> static constexpr bool is_nbit_v = is_nbit<T, n>::value;
template <typename T, typename = std::nullptr_t> struct safely_multipliable { using type = T; };
template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 32>>> { using type = long long; };
template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 64>>> { using type = __int128_t; };
template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 32>>> { using type = unsigned long long; };
template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 64>>> { using type = __uint128_t; };
template <typename T> using safely_multipliable_t = typename safely_multipliable<T>::type;
template <typename T, typename = void> struct rec_value_type { using type = T; };
template <typename T> struct rec_value_type<T, std::void_t<typename T::value_type>> {
using type = typename rec_value_type<typename T::value_type>::type;
};
template <typename T> using rec_value_type_t = typename rec_value_type<T>::type;
template <typename T> class is_iterable {
template <typename T_> static auto test(T_ e) -> decltype(e.begin(), e.end(), std::true_type{});
static std::false_type test(...);
public:
static constexpr bool value = decltype(test(std::declval<T>()))::value;
};
template <typename T> static constexpr bool is_iterable_v = is_iterable<T>::value;
template <typename T> class is_writable {
template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::ostream&>() << e, std::true_type{});
static std::false_type test(...);
public:
static constexpr bool value = decltype(test(std::declval<T>()))::value;
};
template <typename T> static constexpr bool is_writable_v = is_writable<T>::value;
template <typename T> class is_readable {
template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::istream&>() >> e, std::true_type{});
static std::false_type test(...);
public:
static constexpr bool value = decltype(test(std::declval<T>()))::value;
};
template <typename T> static constexpr bool is_readable_v = is_readable<T>::value;
} // namespace suisen
namespace suisen {
struct BitVector {
explicit BitVector(int n) : n(n), nl((n >> LOG_BLOCK_L) + 1), ns((n >> LOG_BLOCK_S) + 1), cum_l(nl, 0), cum_s(ns, 0), bits(ns, 0) {}
BitVector() : BitVector(0) {}
template <typename Gen, constraints_t<std::is_invocable_r<bool, Gen, int>> = nullptr>
BitVector(int n, Gen gen) : BitVector(n) {
build(gen);
}
template <typename Gen, constraints_t<std::is_invocable_r<bool, Gen, int>> = nullptr>
void build(Gen gen) {
int i = 0;
for (int index_s = 1; index_s < ns; ++index_s) {
int count = cum_s[index_s - 1];
for (; i < index_s << LOG_BLOCK_S; ++i) {
bool b = gen(i);
bits[index_s - 1] |= b << (i & MASK_S);
count += b;
}
if (index_s & ((1 << (LOG_BLOCK_L - LOG_BLOCK_S)) - 1)) {
cum_s[index_s] = count;
} else {
int index_l = i >> LOG_BLOCK_L;
cum_l[index_l] = cum_l[index_l - 1] + count;
}
}
for (; i < n; ++i) bits[ns - 1] |= gen(i) << (i & MASK_S);
}
bool operator[](int i) const {
return (bits[i >> LOG_BLOCK_S] >> (i & MASK_S)) & 1;
}
// returns the i'th val (i: 0-indexed)
bool access(int i) const {
return (*this)[i];
}
// returns the number of val in [0, i)
int rank(bool val, int i) const {
int res_1 = cum_l[i >> LOG_BLOCK_L] + cum_s[i >> LOG_BLOCK_S] + popcount8(bits[i >> LOG_BLOCK_S] & ((1 << (i & MASK_S)) - 1));
return val ? res_1 : i - res_1;
}
// returns the number of val in [l, r)
int rank(bool val, int l, int r) const {
return rank(val, r) - rank(val, l);
}
// find the index of num'th val. (num: 1-indexed). if not exists, returns default_value.
int select(bool val, int num, int default_value = -1) const {
int l = -1, r = n + 1;
while (r - l > 1) {
int m = (l + r) >> 1;
(rank(val, m) >= num ? r : l) = m;
}
return r == n + 1 ? default_value : r;
}
private:
static constexpr int LOG_BLOCK_L = 8;
static constexpr int LOG_BLOCK_S = 3;
static constexpr int MASK_S = (1 << LOG_BLOCK_S) - 1;
int n, nl, ns;
std::vector<int> cum_l;
std::vector<std::uint8_t> cum_s, bits;
static constexpr std::uint8_t popcount8(std::uint8_t x) {
x = (x & 0b01010101) + ((x >> 1) & 0b01010101);
x = (x & 0b00110011) + ((x >> 2) & 0b00110011);
return (x & 0b00001111) + (x >> 4);
}
};
} // namespace suisen
using suisen::BitVector;
template <typename T, T(*add)(T, T), T(*zero)(), T(*neg)(T), typename Index = int>
struct RectangleSum {
private:
template <typename U> using Point = std::array<U, 2>;
public:
void build() {
_built = true;
const int n = _points.size();
const auto compare_points = [](const auto& p1, const auto& p2) { return p1.first[0] < p2.first[0]; };
std::sort(_points.begin(), _points.end(), compare_points);
_xs.resize(n), _ys.resize(n);
for (int i = 0; i < n; ++i) {
auto [x, y] = _points[i].first;
_xs[i] = x, _ys[i] = y;
}
std::sort(_ys.begin(), _ys.end()), _ys.erase(std::unique(_ys.begin(), _ys.end()), _ys.end());
_ynum = _ys.size();
for (_log_ynum = 0; 1 << _log_ynum < _ynum; ) ++_log_ynum;
_mid.resize(_log_ynum);
_bvs.resize(_log_ynum);
_acc.assign(_log_ynum + 1, std::vector<T>(n + 1, zero()));
std::vector<std::pair<int, T>> layer(n, { 0, zero() });
for (int i = 0; i < n; ++i) {
auto [p, w] = _points[i];
layer[i] = { _lb_y(p[1]), w };
}
for (int i = 0; i < n; ++i) _acc[_log_ynum][i + 1] = add(_acc[_log_ynum][i], layer[i].second);
for (int lev = _log_ynum - 1; lev >= 0; --lev) {
_bvs[lev] = BitVector(n, [lev, &layer](int i) { return bool((layer[i].first >> lev) & 1); });
_mid[lev] = std::stable_partition(layer.begin(), layer.end(), [lev](const auto& p) { return ((p.first >> lev) & 1) == 0; }) - layer.begin();
for (int i = 0; i < n; ++i) _acc[lev][i + 1] = add(_acc[lev][i], layer[i].second);
}
}
void add_point(Index x, Index y, T w) {
_built = false;
_points.emplace_back(Point<Index>{ x, y }, w);
}
T sum(Index xl, Index xr, Index yl, Index yr) const {
assert(_built);
const int cxl = _lb_x(xl), cxr = _lb_x(xr), cyl = _lb_y(yl), cyr = _lb_y(yr);
return _sum(cxl, cxr, cyl, cyr);
}
T operator()(Index xl, Index xr, Index yl, Index yr) const { return sum(xl, xr, yl, yr); }
private:
std::vector<std::pair<Point<Index>, T>> _points{};
std::vector<Index> _xs{}, _ys{};
int _ynum{};
int _log_ynum{};
std::vector<int> _mid{};
std::vector<BitVector> _bvs{};
std::vector<std::vector<T>> _acc{};
bool _built = false;
T _sum(int l, int r, int v) const {
if (v == 0) return zero();
if (v == _ynum) return add(_acc[_log_ynum][r], neg(_acc[_log_ynum][l]));
T pos_res = zero(), neg_res = zero();
for (int lev = _log_ynum - 1; lev >= 0; --lev) {
const int l0 = _bvs[lev].rank(0, l);
const int r0 = _bvs[lev].rank(0, r);
if ((v >> lev) & 1) {
pos_res = add(pos_res, _acc[lev][r0]);
neg_res = add(neg_res, _acc[lev][l0]);
l = _mid[lev] + l - l0, r = _mid[lev] + r - r0;
} else {
l = l0, r = r0;
}
}
return add(pos_res, neg(neg_res));
}
T _sum(const int l, const int r, const int vl, const int vr) const {
if (vl == _ynum or vr == 0) return zero();
if (vl == 0) return _sum(l, r, vr);
if (vr == _ynum) return add(_acc[_log_ynum][r], neg(add(_acc[_log_ynum][l], _sum(l, r, vl))));
const int v[2]{ vl, vr };
int p[2][2]{ l, r, l, r };
T res[2][2]{ zero(), zero(), zero(), zero() };
for (int lev = _log_ynum - 1; lev >= 0; --lev) {
const int np[2][2]{
_bvs[lev].rank(0, p[0][0]),
_bvs[lev].rank(0, p[0][1]),
_bvs[lev].rank(0, p[1][0]),
_bvs[lev].rank(0, p[1][1]),
};
if ((v[0] >> lev) & 1) {
res[0][0] = add(res[0][0], _acc[lev][np[0][0]]);
res[0][1] = add(res[0][1], _acc[lev][np[0][1]]);
p[0][0] = _mid[lev] + p[0][0] - np[0][0];
p[0][1] = _mid[lev] + p[0][1] - np[0][1];
} else {
p[0][0] = np[0][0];
p[0][1] = np[0][1];
}
if ((v[1] >> lev) & 1) {
res[1][0] = add(res[1][0], _acc[lev][np[1][0]]);
res[1][1] = add(res[1][1], _acc[lev][np[1][1]]);
p[1][0] = _mid[lev] + p[1][0] - np[1][0];
p[1][1] = _mid[lev] + p[1][1] - np[1][1];
} else {
p[1][0] = np[1][0];
p[1][1] = np[1][1];
}
}
return add(add(res[0][0], res[1][1]), neg(add(res[0][1], res[1][0])));
}
int _lb_x(Index x) const {
if (_xs.size()) {
if (x <= _xs.front()) return 0;
if (x > _xs.back()) return _xs.size();
}
return std::lower_bound(_xs.begin(), _xs.end(), x) - _xs.begin();
}
int _lb_y(Index y) const {
if (_ys.size()) {
if (y <= _ys.front()) return 0;
if (y > _ys.back()) return _ys.size();
}
return std::lower_bound(_ys.begin(), _ys.end(), y) - _ys.begin();
}
};
//modint+畳み込み+逆元テーブル
// from: https://gist.github.com/yosupo06/ddd51afb727600fd95d9d8ad6c3c80c9
// (based on AtCoder STL)
#include <algorithm>
#include <array>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
} // namespace internal
} // namespace atcoder
#include <utility>
namespace atcoder {
namespace internal {
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
struct barrett {
unsigned int _m;
unsigned long long im;
barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
unsigned int umod() const { return _m; }
unsigned int mul(unsigned int a, unsigned int b) const {
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned int v = (unsigned int)(z - x * _m);
if (_m <= v) v += _m;
return v;
}
};
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
for (long long a : {2, 7, 61}) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 < 0) m0 += b / s;
return {s, m0};
}
constexpr int primitive_root_constexpr(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <numeric>
#include <type_traits>
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <numeric>
#include <type_traits>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
} // namespace internal
template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
static_modint(bool v) { _v = ((unsigned int)(v) % umod()); }
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template <int id> struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
dynamic_modint(bool v) { _v = ((unsigned int)(v) % mod()); }
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt = 998244353;
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <type_traits>
#include <vector>
namespace atcoder {
namespace internal {
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
void butterfly(std::vector<mint>& a) {
static constexpr int g = internal::primitive_root<mint::mod()>;
int n = int(a.size());
int h = internal::ceil_pow2(n);
static bool first = true;
static mint sum_e[30]; // sum_e[i] = ies[0] * ... * ies[i - 1] * es[i]
if (first) {
first = false;
mint es[30], ies[30]; // es[i]^(2^(2+i)) == 1
int cnt2 = bsf(mint::mod() - 1);
mint e = mint(g).pow((mint::mod() - 1) >> cnt2), ie = e.inv();
for (int i = cnt2; i >= 2; i--) {
es[i - 2] = e;
ies[i - 2] = ie;
e *= e;
ie *= ie;
}
mint now = 1;
for (int i = 0; i < cnt2 - 2; i++) {
sum_e[i] = es[i] * now;
now *= ies[i];
}
}
for (int ph = 1; ph <= h; ph++) {
int w = 1 << (ph - 1), p = 1 << (h - ph);
mint now = 1;
for (int s = 0; s < w; s++) {
int offset = s << (h - ph + 1);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p] * now;
a[i + offset] = l + r;
a[i + offset + p] = l - r;
}
now *= sum_e[bsf(~(unsigned int)(s))];
}
}
}
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
void butterfly_inv(std::vector<mint>& a) {
static constexpr int g = internal::primitive_root<mint::mod()>;
int n = int(a.size());
int h = internal::ceil_pow2(n);
static bool first = true;
static mint sum_ie[30]; // sum_ie[i] = es[0] * ... * es[i - 1] * ies[i]
if (first) {
first = false;
mint es[30], ies[30]; // es[i]^(2^(2+i)) == 1
int cnt2 = bsf(mint::mod() - 1);
mint e = mint(g).pow((mint::mod() - 1) >> cnt2), ie = e.inv();
for (int i = cnt2; i >= 2; i--) {
es[i - 2] = e;
ies[i - 2] = ie;
e *= e;
ie *= ie;
}
mint now = 1;
for (int i = 0; i < cnt2 - 2; i++) {
sum_ie[i] = ies[i] * now;
now *= es[i];
}
}
for (int ph = h; ph >= 1; ph--) {
int w = 1 << (ph - 1), p = 1 << (h - ph);
mint inow = 1;
for (int s = 0; s < w; s++) {
int offset = s << (h - ph + 1);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p];
a[i + offset] = l + r;
a[i + offset + p] =
(unsigned long long)(mint::mod() + l.val() - r.val()) *
inow.val();
}
inow *= sum_ie[bsf(~(unsigned int)(s))];
}
}
}
} // namespace internal
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution(std::vector<mint> a, std::vector<mint> b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
if (std::min(n, m) <= 60) {
if (n < m) {
std::swap(n, m);
std::swap(a, b);
}
std::vector<mint> ans(n + m - 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans[i + j] += a[i] * b[j];
}
}
return ans;
}
int z = 1 << internal::ceil_pow2(n + m - 1);
a.resize(z);
internal::butterfly(a);
b.resize(z);
internal::butterfly(b);
for (int i = 0; i < z; i++) {
a[i] *= b[i];
}
internal::butterfly_inv(a);
a.resize(n + m - 1);
mint iz = mint(z).inv();
for (int i = 0; i < n + m - 1; i++) a[i] *= iz;
return a;
}
template <unsigned int mod = 998244353,
class T,
std::enable_if_t<internal::is_integral<T>::value>* = nullptr>
std::vector<T> convolution(const std::vector<T>& a, const std::vector<T>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
using mint = static_modint<mod>;
std::vector<mint> a2(n), b2(m);
for (int i = 0; i < n; i++) {
a2[i] = mint(a[i]);
}
for (int i = 0; i < m; i++) {
b2[i] = mint(b[i]);
}
auto c2 = convolution(move(a2), move(b2));
std::vector<T> c(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
c[i] = c2[i].val();
}
return c;
}
std::vector<long long> convolution_ll(const std::vector<long long>& a,
const std::vector<long long>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
static constexpr unsigned long long MOD1 = 754974721; // 2^24
static constexpr unsigned long long MOD2 = 167772161; // 2^25
static constexpr unsigned long long MOD3 = 469762049; // 2^26
static constexpr unsigned long long M2M3 = MOD2 * MOD3;
static constexpr unsigned long long M1M3 = MOD1 * MOD3;
static constexpr unsigned long long M1M2 = MOD1 * MOD2;
static constexpr unsigned long long M1M2M3 = MOD1 * MOD2 * MOD3;
static constexpr unsigned long long i1 =
internal::inv_gcd(MOD2 * MOD3, MOD1).second;
static constexpr unsigned long long i2 =
internal::inv_gcd(MOD1 * MOD3, MOD2).second;
static constexpr unsigned long long i3 =
internal::inv_gcd(MOD1 * MOD2, MOD3).second;
auto c1 = convolution<MOD1>(a, b);
auto c2 = convolution<MOD2>(a, b);
auto c3 = convolution<MOD3>(a, b);
std::vector<long long> c(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
unsigned long long x = 0;
x += (c1[i] * i1) % MOD1 * M2M3;
x += (c2[i] * i2) % MOD2 * M1M3;
x += (c3[i] * i3) % MOD3 * M1M2;
long long diff =
c1[i] - internal::safe_mod((long long)(x), (long long)(MOD1));
if (diff < 0) diff += MOD1;
static constexpr unsigned long long offset[5] = {
0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3};
x -= offset[diff % 5];
c[i] = x;
}
return c;
}
} // namespace atcoder
using mint=atcoder::modint;
typedef long long ll;
struct S { mint v; };
S add(S x, S y) { return { x.v + y.v }; }
S zero() { return { 0LL }; }
S neg(S x) { return { -x.v }; }
int main() {
auto &scanner = suisen::fast_in;
auto &printer = suisen::fast_out;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
auto rd=[&](ll momo){
ll x=rng()%momo;
if(x<0) x+=momo;
return x;
};
ll H,W;
scanner>>H>>W;
ll N;
scanner>>N;
mint::set_mod(1999999943);
ll ha=rd(1999999943);
ll be=W+W;
vector<ll> X(10);
X[1]=rd(1999999943);
X[2]=rd(1999999943);
X[5]=rd(1999999943);
X[6]=rd(1999999943);
X[8]=rd(1999999943);
X[9]=rd(1999999943);
X[0]=rd(1999999943);
vector<ll> Y(10);
Y[0]=0;
Y[1]=1;
Y[2]=2;
Y[5]=5;
Y[9]=6;
Y[8]=8;
Y[6]=9;
RectangleSum<S, add, zero, neg> sum1,sum2;
for (int i = 0; i < N; ++i) {
ll x, y, w;
scanner >> x >> y >> w;x--;y--;
if(w==0) continue;
mint v=X[w];
v*=mint(ha).pow(be*x+y);
sum1.add_point(x, y, S{v});
w=Y[w];
x=H-1-x;
y=W-1-y;
v=X[w];
v*=mint(ha).pow(be*x+y);
sum2.add_point(x, y, S{v});
}
sum1.build();
sum2.build();
int Q;
scanner>>Q;
while (Q--) {
ll l, d, r, u;
scanner >> l >> d >> r >> u;
l--;d--;
mint x=sum1(l,r,d,u).v,y=sum2(H-r,H-l,W-u,W-d).v;
x/=mint(ha).pow(be*l+d);
y/=mint(ha).pow(be*(H-r)+W-u);
if(x==y) printer << "Yes" << '\n';
else printer << "No" << '\n';
}
}