Submission #73387138

---

Source Code Expand

#include <utility>
#if __has_include(<bits/stdc++.h>)
#include <bits/stdc++.h>
using namespace std;
#endif
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#if __has_include(<boost/multiprecision/cpp_int.hpp>)
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
#endif
#if !__has_include(<concepts>) || !__has_include(<optional>)
#error Either your C++ version is too old, or the included file is corrupted.
#endif

#ifndef ONLINE_JUDGE
#define debug(...) debug::debug_impl(#__VA_ARGS__, __VA_ARGS__)
#define debug_expr(...)                                                        \
  cerr << #__VA_ARGS__ << " = ";                                               \
  debug::_print(__VA_ARGS__);                                                  \
  cerr << endl;
#define _GLIBCXX_DEBUG
struct Initialization {
  Initialization() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(20) << fixed;
  }
} initialization;
#define endl '\n'
namespace debug {
template <typename T>
concept iterable = requires(T &t) {
  begin(t);
  end(t);
};
template <typename T> struct is_pair : false_type {};
template <typename T1, typename T2> struct is_pair<pair<T1, T2>> : true_type {};
template <typename T> inline constexpr bool is_pair_v = is_pair<T>::value;
template <typename T>
concept is_tuple = !is_pair_v<T> && requires {
  typename tuple_size<T>::type;
  get<0>(declval<T>());
};
template <typename T>
concept is_pos = requires(T &t) {
  t.x;
  t.y;
};
template <typename T>
concept is_grid = requires(T &t) {
  t.H;
  t.W;
  t.S;
};
template <typename T> void _print(const T &value);
template <typename T1, typename T2> void _print(const pair<T1, T2> &p) {
  cerr << "(first: ";
  _print(p.first);
  cerr << ", second: ";
  _print(p.second);
  cerr << ")";
}
template <typename T, size_t... Is>
void print_tuple_impl(const T &t, index_sequence<Is...>) {
  cerr << "(";
  ((cerr << (Is == 0 ? "" : ", "), _print(get<Is>(t))), ...);
  cerr << ")";
}

template <typename T> void _print(const T &value) {
  if constexpr (is_pair_v<T>) {
    _print(value);
  } else if constexpr (is_tuple<T>) {
    print_tuple_impl(value, make_index_sequence<tuple_size_v<T>>{});
  } else if constexpr (is_pos<T>) {
    cerr << "(x: " << value.x << ", y: " << value.y << ")";
  } else if constexpr (is_same_v<T, string>) {
    cerr << '"' << value << '"';
  } else if constexpr (is_grid<T>) {
    cerr << "\n";
    for (int i = 0; i < value.H; ++i)
      cerr << "  " << value.S[i] << "\n";
  } else if constexpr (iterable<T>) {
    using ElementType = decay_t<decltype(*begin(value))>;
    if constexpr (is_same_v<ElementType, string> || is_grid<ElementType> ||
                  iterable<ElementType>) {
      cerr << "\n";
      for (const auto &row : value) {
        cerr << "  ";
        _print(row);
        cerr << "\n";
      }
    } else {
      cerr << "(";
      bool first = true;
      for (const auto &v : value) {
        if (!first)
          cerr << ", ";
        _print(v);
        first = false;
      }
      cerr << ")";
    }
  } else {
    cerr << value;
  }
}

void debug_impl(const char *s) { cerr << endl; }
template <typename T, typename... Args>
void debug_impl(const char *s, const T &first, const Args &...rest) {
  const char *comma = strchr(s, ',');
  cerr << "[";
  if (comma) {
    cerr.write(s, comma - s);
  } else {
    cerr << s;
  }
  cerr << "] = ";
  _print(first);
  if (comma) {
    cerr << ", ";
    debug_impl(comma + 1, rest...);
  } else {
    cerr << endl;
  }
}

template <typename T> string to_string_impl(const T &v) {
  stringstream ss;
  ss << v;
  return ss.str();
}
} // namespace debug
#else
#define debug(...)
#define debug_expr(...)
#endif

#define int long long
#define double long double
#define all(a) (a).begin(), (a).end()

using ll = long long;
using P = pair<int, int>;

const string ALPHABET_L = "abcdefghijklmnopqrstuvwxyz";
const string ALPHABET_U = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

const double PI = acos(-1.0L);
const int MOD = 1000000007;
const int INF = (1LL << 62) - (1LL << 31) - 1;
const double DINF = numeric_limits<double>::infinity();

template <typename T, typename U, typename V> struct triple {
  T first;
  U second;
  V third;
  triple() : first{}, second{}, third{} {}
  triple(const T &a, const U &b, const V &c) : first(a), second(b), third(c) {}
  triple(T &&a, U &&b, V &&c)
      : first(move(a)), second(move(b)), third(move(c)) {}

  triple(const triple &) = default;
  triple &operator=(const triple &) = default;
  triple(triple &&) = default;
  triple &operator=(triple &&) = default;

  void swap(triple &other) {
    using std::swap;
    swap(first, other.first);
    swap(second, other.second);
    swap(third, other.third);
  }
};
template <typename T, typename U, typename V>
bool operator==(const triple<T, U, V> &lhs, const triple<T, U, V> &rhs) {
  return lhs.first == rhs.first && lhs.second == rhs.second &&
         lhs.third == rhs.third;
}
template <typename T, typename U, typename V>
bool operator!=(const triple<T, U, V> &lhs, const triple<T, U, V> &rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U, typename V>
bool operator<(const triple<T, U, V> &lhs, const triple<T, U, V> &rhs) {
  return tie(lhs.first, lhs.second, lhs.third) <
         tie(rhs.first, rhs.second, rhs.third);
}
template <typename T, typename U, typename V>
bool operator<=(const triple<T, U, V> &lhs, const triple<T, U, V> &rhs) {
  return !(rhs > lhs);
}
template <typename T, typename U, typename V>
bool operator>(const triple<T, U, V> &lhs, const triple<T, U, V> &rhs) {
  return rhs < lhs;
}
template <typename T, typename U, typename V>
bool operator>=(const triple<T, U, V> &lhs, const triple<T, U, V> &rhs) {
  return !(lhs < rhs);
}
template <typename T, typename U, typename V>
ostream &operator<<(ostream &os, const triple<T, U, V> &t) {
  os << "(" << t.first << ", " << t.second << ", " << t.third << ")";
  return os;
}
template <typename T, typename U, typename V>
istream &operator>>(istream &is, triple<T, U, V> &t) {
  is >> t.first >> t.second >> t.third;
  return is;
}

template <typename T, typename U, typename V>
struct tuple_size<triple<T, U, V>> : integral_constant<size_t, 3> {};
template <size_t N, typename T, typename U, typename V>
struct tuple_element<N, triple<T, U, V>> {
  using type = decltype(declval<triple<T, U, V>>().first);
};
template <typename T, typename U, typename V>
struct tuple_element<1, triple<T, U, V>> {
  using type = U;
};
template <typename T, typename U, typename V>
struct tuple_element<2, triple<T, U, V>> {
  using type = V;
};
template <size_t N, typename T, typename U, typename V>
auto &get(triple<T, U, V> &t) {
  if constexpr (N == 0)
    return t.first;
  else if constexpr (N == 1)
    return t.second;
  else if constexpr (N == 2)
    return t.third;
}
template <size_t N, typename T, typename U, typename V>
const auto &get(const triple<T, U, V> &t) {
  if constexpr (N == 0)
    return t.first;
  else if constexpr (N == 1)
    return t.second;
  else if constexpr (N == 2)
    return t.third;
}
template <size_t N, typename T, typename U, typename V>
auto &&get(triple<T, U, V> &&t) {
  if constexpr (N == 0)
    return move(t.first);
  else if constexpr (N == 1)
    return move(t.second);
  else if constexpr (N == 2)
    return move(t.third);
}

// 座標情報
struct Pos {
  int x, y;
  Pos() : x(0), y(0) {}
  template <typename T>
    requires integral<T>
  Pos(T x) : x(x), y(0) {}
  template <typename T, typename Y>
    requires integral<T> && integral<Y>
  Pos(T x, Y y) : x(x), y(y) {}
  Pos(P p) : x(p.first), y(p.second) {}

  bool operator<(const Pos &other) const {
    if (x != other.x)
      return x < other.x;
    return y < other.y;
  }
  bool operator>(const Pos &other) const {
    if (x != other.x)
      return x > other.x;
    return y > other.y;
  }
  bool operator==(const Pos &other) const {
    return x == other.x && y == other.y;
  }
  bool operator!=(const Pos &other) const { return !(*this == other); }
  bool operator<=(const Pos &other) const { return !(*this > other); }
  bool operator>=(const Pos &other) const { return !(*this < other); }
  Pos operator+() const { return *this; }
  Pos operator-() const { return Pos(-x, -y); }
  Pos operator+(const Pos &other) const {
    return Pos(x + other.x, y + other.y);
  }
  Pos operator-(const Pos &other) const {
    return Pos(x - other.x, y - other.y);
  }
  Pos operator*(int scalar) const { return Pos(x * scalar, y * scalar); }
  Pos operator/(int scalar) const { return Pos(x / scalar, y / scalar); }
  Pos &operator+=(int num) {
    x += num;
    y += num;
    return *this;
  }
  Pos &operator+=(const Pos &other) {
    x += other.x;
    y += other.y;
    return *this;
  }
  Pos &operator-=(int num) {
    x -= num;
    y -= num;
    return *this;
  }
  Pos &operator-=(const Pos &other) {
    x -= other.x;
    y -= other.y;
    return *this;
  }
  Pos &operator*=(int scalar) {
    x *= scalar;
    y *= scalar;
    return *this;
  }
  Pos &operator/=(int scalar) {
    x /= scalar;
    y /= scalar;
    return *this;
  }
  Pos &operator++() {
    x++;
    y++;
    return *this;
  }
  Pos &operator--() {
    x--;
    y--;
    return *this;
  }
  Pos operator++(signed) {
    Pos old = *this;
    ++(*this);
    return old;
  }
  Pos operator--(signed) {
    Pos old = *this;
    --(*this);
    return old;
  }

  // ベクトルの大きさ（ノルム）の2乗を計算します。
  int norm_sq() const { return (int)x * x + (int)y * y; }

  // ベクトルの大きさ（ノルム）の2乗を計算します。
  double norm() const { return sqrt((double)norm_sq()); }

  // 2つのベクトルの内積を計算します。
  int dot(const Pos &other) const {
    return (int)x * other.x + (int)y * other.y;
  }
  static int dot(const Pos &a, const Pos &b) { return a.dot(b); }
  // 2つのベクトルの外積を計算します。
  int cross(const Pos &other) const {
    return (int)x * other.y - (int)y * other.x;
  }
  static int cross(const Pos &a, const Pos &b) { return a.cross(b); }

  // 原点を中心に、この点を時計回りに90度回転させます。
  void rotate90() {
    int old_x = x;
    x = y;
    y = -old_x;
  }
  // この点と別の点 `other` とのマンハッタン距離を計算します。
  int manhattan_distance(const Pos &other) const {
    return abs(x - other.x) + abs(y - other.y);
  }
  static int manhattan_distance(const Pos &a, const Pos &b) {
    return a.manhattan_distance(b);
  }
  // この点と別の点otherとのユークリッド距離の2乗を計算します。
  int distance_sq(const Pos &other) const {
    return (int)(x - other.x) * (x - other.x) +
           (int)(y - other.y) * (y - other.y);
  }
  static int distance_sq(const Pos &a, const Pos &b) {
    return a.distance_sq(b);
  }
  // この点と別の点 `other` とのユークリッド距離を計算します。
  double distance(const Pos &other) const {
    return sqrt((double)distance_sq(other));
  }
  static double distance(const Pos &a, const Pos &b) { return a.distance(b); }
  // 八近傍での距離を計算します。
  int distance_8(const Pos &other) const {
    return max(abs(x - other.x), abs(y - other.y));
  }
  static int distance_8(const Pos &a, const Pos &b) { return a.distance_8(b); }
  // 四近傍での距離を計算します。
  int distance_4(const Pos &other) const {
    return abs(x - other.x) + abs(y - other.y);
  }
  static int distance_4(const Pos &a, const Pos &b) { return a.distance_4(b); }
  // 座標を0に戻します。
  Pos reset() {
    x = 0;
    y = 0;
    return Pos{0, 0};
  }
  // xとyを逆にした座標を返します
  Pos reverse() {
    Pos old = Pos{x, y};
    x = old.y;
    y = old.x;
    return Pos{y, x};
  }
  // 与えられたすべての点を巡回する最短移動距離を計算します
  static double dis_pass(const vector<Pos> &points) {
    int n = points.size();
    if (n <= 1)
      return 0.0;
    vector<vector<double>> dp(1 << n, vector<double>(n, DINF));
    vector<vector<double>> dist(n, vector<double>(n));
    for (int i = 0; i < n; ++i)
      for (int j = i; j < n; ++j)
        dist[i][j] = dist[j][i] = points[i].distance(points[j]);
    dp[1 << 0][0] = 0.0;
    for (int S = 1; S < (1 << n); ++S) {
      for (int v = 0; v < n; ++v) {
        if (!((S >> v) & 1))
          continue;
        if (dp[S][v] == DINF)
          continue;
        for (int u = 0; u < n; ++u) {
          if ((S >> u) & 1)
            continue;
          int next_S = S | (1 << u);
          double new_dist = dp[S][v] + dist[v][u];
          if (dp[next_S][u] > new_dist)
            dp[next_S][u] = new_dist;
        }
      }
    }
    int final_S = (1 << n) - 1;
    double min_total_dist = DINF;
    for (int v = 0; v < n; ++v)
      if (dp[final_S][v] != DINF)
        min_total_dist = min(min_total_dist, dp[final_S][v] + dist[v][0]);
    return min_total_dist;
  }
};
Pos pos;

const vector<Pos> dir4 = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const vector<Pos> dir8 = {{1, 0}, {-1, 0}, {0, 1},   {0, -1},
                          {1, 1}, {-1, 1}, {-1, -1}, {1, -1}};

template <typename T>
vector<T> operator+(const vector<T> &lhs, const vector<T> &rhs) {
  vector<T> result;
  result.reserve(lhs.size() + rhs.size());
  result.insert(result.end(), lhs.begin(), lhs.end());
  result.insert(result.end(), rhs.begin(), rhs.end());
  return result;
}
template <typename T>
vector<T> operator+(vector<T> &&lhs, const vector<T> &rhs) {
  lhs.insert(lhs.end(), rhs.begin(), rhs.end());
  return move(lhs);
}
template <typename T>
vector<T> operator+(const vector<T> &lhs, vector<T> &&rhs) {
  rhs.insert(rhs.begin(), lhs.begin(), lhs.end());
  return move(rhs);
}
template <typename T> vector<T> operator+(vector<T> &&lhs, vector<T> &&rhs) {
  lhs.insert(lhs.end(), make_move_iterator(rhs.begin()),
             make_move_iterator(rhs.end()));
  return move(lhs);
}
template <typename T> vector<T> operator*(vector<T> &&lhs, int num) {
  vector<T> res = {};
  while (num--)
    res = res + lhs;
  return res;
}
template <typename T> vector<T> operator*=(vector<T> &&lhs, int num) {
  lhs = lhs * num;
  return lhs;
}

// 行列演算をサポートする構造体。
template <typename T> struct Matrix {
  vector<vector<T>> mat;
  int size; // 行列のサイズ (正方行列)
  // コンストラクタ
  Matrix(int sz) : size(sz), mat(sz, vector<T>(sz, 0)) {}
  // 単位行列を生成する静的メソッド
  static Matrix identity(int sz) {
    Matrix I(sz);
    for (int i = 0; i < sz; ++i)
      I.mat[i][i] = 1;
    return I;
  }
  // 行へのアクセス
  vector<T> &operator[](int i) { return mat[i]; }
  const vector<T> &operator[](int i) const { return mat[i]; }
  // 行列の積
  Matrix operator*(const Matrix &other) const {
    Matrix result(size);
    for (int i = 0; i < size; ++i)
      for (int j = 0; j < size; ++j)
        for (int k = 0; k < size; ++k)
          result[i][j] = (result[i][j] + mat[i][k] * other[k][j]);
    return result;
  }
  // 行列のべき乗
  Matrix pow(ll n) const {
    Matrix result = Matrix::identity(size);
    Matrix x = *this;
    while (n > 0) {
      if (n & 1)
        result = result * x;
      x = x * x;
      n >>= 1;
    }
    return result;
  }
};
// 回転・反転・全体への加算をO(1)で行えるvector風コンテナ。
template <typename T> struct OperableVector {
private:
  vector<T> data;
  int start_pos = 0;
  bool is_reversed = false;
  T lazy_add = 0;
  int _get_actual_index(int i) const {
    const int n = data.size();
    if (n == 0)
      return 0;
    if (!is_reversed)
      return (start_pos + i) % n;
    else
      return (start_pos - 1 - i + n) % n;
  }

public:
  OperableVector() = default;
  explicit OperableVector(int n, T val = T{}) : data(n, val) {}
  OperableVector(const vector<T> &v) : data(v) {}
  OperableVector(initializer_list<T> init) : data(init) {}
  struct Proxy {
    OperableVector &ov;
    int index;
    operator T() const {
      return ov.data[ov._get_actual_index(index)] + ov.lazy_add;
    }
    Proxy &operator=(const T &value) {
      ov.data[ov._get_actual_index(index)] = value - ov.lazy_add;
      return *this;
    }
  };

  Proxy operator[](int i) { return {*this, i}; }
  T operator[](int i) const { return data[_get_actual_index(i)] + lazy_add; }

  Proxy front() { return (*this)[0]; }
  T front() const { return (*this)[0]; }
  Proxy back() { return (*this)[size() - 1]; }
  T back() const { return (*this)[size() - 1]; }
  int size() const { return data.size(); }
  bool empty() const { return data.empty(); }
  void reverse() { is_reversed = !is_reversed; }
  void rotate_left(ll k) {
    int n = size();
    if (n == 0)
      return;
    k %= n;
    if (!is_reversed)
      start_pos = (start_pos + k) % n;
    else
      start_pos = (start_pos - k + n) % n;
  }
  void rotate_right(ll k) { rotate_left(-k); }
  void add_all(const T &value) { lazy_add += value; }
  OperableVector &operator+=(const T &value) {
    add_all(value);
    return *this;
  }
  OperableVector &operator-=(const T &value) {
    add_all(-1 * value);
    return *this;
  }
  // 現在の状態を反映した通常の vector を生成して返す。
  vector<T> to_vector() const {
    vector<T> result(size());
    for (int i = 0; i < size(); ++i)
      result[i] = (*this)[i];
    return result;
  }
};
// 最小値で変数を更新します。
template <typename T> bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T> bool chmin(T &a, signed b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
// 最大値で変数を更新します。
template <typename T> bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T> bool chmax(T &a, signed b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
// グリッド
template <typename T> struct GenGrid {
  int H = 0;
  int W = 0;
  vector<vector<T>> data;
  T init_val = T{};

  GenGrid(const GenGrid &) = default;
  GenGrid &operator=(const GenGrid &) = default;
  GenGrid(GenGrid &&) = default;
  GenGrid &operator=(GenGrid &&) = default;
  ~GenGrid() = default;

  GenGrid(int h = 0, int w = 0) {
    set_init_val();
    resize(h, w, init_val);
  }
  GenGrid(const vector<vector<T>> &v)
      : H(v.size()), W(v.empty() ? 0 : v[0].size()), data(v) {
    set_init_val();
  }

  void set_init_val() {
    if constexpr (is_same_v<T, char>)
      init_val = '.';
    else if constexpr (is_integral_v<T>)
      init_val = 0;
  }

  void resize(int h, int w, T val) {
    if (h < 0)
      h = 0;
    if (w < 0)
      w = 0;
    data.assign(h, vector<T>(w, val));
    H = h;
    W = w;
  }

  vector<T> &operator[](int i) { return data[i]; }
  const vector<T> &operator[](int i) const { return data[i]; }
  T &operator[](Pos &p) { return data[p.x][p.y]; }
  const T &operator[](Pos &p) const { return data[p.x][p.y]; }
  T &operator[](P p) { return data[p.first][p.second]; }
  const T &operator[](P p) const { return data[p.first][p.second]; }

  bool operator==(const GenGrid &other) const {
    return (H == other.H) && (W == other.W) && (data == other.data);
  }
  bool operator!=(const GenGrid &other) const { return !(*this == other); }
  bool operator<(const GenGrid &other) const { return area() < other.area(); }
  bool operator<=(const GenGrid &other) const { return area() <= other.area(); }
  bool operator>(const GenGrid &other) const { return area() > other.area(); }
  bool operator>=(const GenGrid &other) const { return area() >= other.area(); }

  GenGrid &operator+=(const GenGrid &other) {
    if (this->W == other.W) {
      this->data.insert(this->data.end(), other.data.begin(), other.data.end());
      this->H += other.H;
    } else if (this->H == other.H) {
      for (int i = 0; i < this->H; ++i)
        this->data[i].insert(this->data[i].end(), other.data[i].begin(),
                             other.data[i].end());
      this->W += other.W;
    } else
      throw invalid_argument(
          "Grid dimensions are not compatible for addition.");
    return *this;
  }

  GenGrid &operator+=(int val) {
    resize(H + val, W + val, init_val);
    return *this;
  }
  GenGrid &operator-=(int val) {
    resize(H - val, W - val, init_val);
    return *this;
  }
  GenGrid &operator*=(int val) {
    if (val <= 0) {
      resize(0, 0, init_val);
      return *this;
    }
    if (val == 1) {
      return *this;
    }
    vector<vector<T>> original_s = data;
    for (int i = 1; i < val; ++i)
      data.insert(data.end(), original_s.begin(), original_s.end());
    H *= val;
    return *this;
  }
  GenGrid &operator/=(int val) {
    if (val != 0)
      resize(H / val, W / val, init_val);
    return *this;
  }

  int height() const { return H; }
  int width() const { return W; }
  int area() const { return H * W; }
  bool is_inside(int r, int c) const {
    return 0 <= r && r < H && 0 <= c && c < W;
  }

  void reset() {
    H = data.size();
    W = data.empty() ? 0 : data[0].size();
  }

  // 列を指定した要素で埋める
  int fill_row(int R, T c, int init = 0) {
    for (int i = 0; i < this->width(); i++) {
      if (data[R][i] != c)
        init++;
      this->data[R][i] = c;
    }
    return init;
  }
  // 行を指定した要素で埋める
  int fill_col(int C, T c, int init = 0) {
    for (int i = 0; i < this->height(); i++) {
      if (data[i][C] != c)
        init++;
      this->data[i][C] = c;
    }
    return init;
  }

  // 列ごとに指定した文字がいくつあるか求める
  vector<int> count_row(T c, int init = 0) const {
    vector<int> res(this->height(), init);
    for (int i = 0; i < this->height(); i++)
      res[i] += count(all(data[i]), c);
    return res;
  }
  // 行ごとに指定した文字がいくつあるか求める
  vector<int> count_col(T c, int init = 0) const {
    vector<int> res(this->width(), init);
    for (int j = 0; j < this->width(); j++)
      for (int i = 0; i < this->height(); i++)
        res[j] += data[i][j] == c;
    return res;
  }

  // 指定した文字が最もある列のインデックスを求める(複数の場合は最初のもの)
  int specified_row(T c, int init = 0) const {
    const auto a = count_row(c, init);
    return max_element(all(a)) - a.begin();
  }
  // 指定した文字が最もある行のインデックスを求める(複数の場合は最初のもの)
  int specified_col(T c, int init = 0) const {
    const auto a = count_col(c, init);
    return max_element(all(a)) - a.begin();
  }

  // 指定した文字が何個あるかを求める
  int count_all(T c, int init = 0) const {
    for (auto &&i : this->data)
      for (auto &&j : i)
        init += j == c;
    return init;
  }

  // 指定した行、列の部分を抽出する
  template <typename Y>
    requires integral<Y>
  GenGrid fetch_partial_grid(vector<Y> R, vector<Y> C) const {
    sort(all(R));
    sort(all(C));
    GenGrid res(R.size(), C.size());
    for (int i = 0; i < R.size(); i++)
      for (int j = 0; j < C.size(); j++)
        res[i][j] = this->data[R[i]][C[i]];
    return res;
  }

  // 指定した文字が最初にあるインデックス
  optional<Pos> find(T target) const {
    for (int i = 0; i < this->height(); i++)
      for (int j = 0; j < this->width(); j++)
        if (data[i][j] == target)
          return Pos{i, j};
    return nullopt;
  }

  // 時計回りに回転
  void rotate_right() {
    if (this->height() == 0 || this->width() == 0)
      return;
    vector<vector<T>> new_S(this->width(), vector<T>(H, this->init_val));
    for (int i = 0; i < this->height(); i++)
      for (int j = 0; j < this->width(); j++)
        new_S[j][H - 1 - i] = data[i][j];
    this->data = new_S;
    swap(H, W);
  }

  // グリッドを上下に反転させる
  void flip_vertical() { reverse(all(data)); }
  // グリッドを左右に反転させる
  void flip_horizontal() {
    for (int i = 0; i < this->height(); i++)
      reverse(all(data[i]));
  }

  // 部分グリッドを抽出する
  GenGrid get_subgrid(int r, int c, int h, int w) const {
    GenGrid sub(h, w);
    for (int i = 0; i < h; i++)
      for (int j = 0; j < w; j++)
        if (is_inside(r + i, c + j))
          sub[i][j] = data[r + i][c + j];
    return sub;
  }

  // 指定したパターンが存在するかを判定する
  bool contains(const GenGrid &pattern) const {
    if (pattern.height() > this->height() || pattern.width() > this->width())
      return false;
    for (int i = 0; i <= H - pattern.height(); i++) {
      for (int j = 0; j <= W - pattern.width(); j++) {
        bool match = true;
        for (int k = 0; k < pattern.height(); k++) {
          for (int l = 0; l < pattern.width(); l++) {
            if (data[i + k][j + l] != pattern[k][l]) {
              match = false;
              break;
            }
          }
          if (!match)
            break;
        }
        if (match)
          return true;
      }
    }
    return false;
  }

  // グリッドの中にインデックスが存在するか
  bool is_inside(Pos p) const {
    return 0 <= p.x && p.x < H && 0 <= p.y && p.y < W;
  }

  // すべての要素に操作をする
  template <typename Func> void foreach (Func func) {
    for (auto &&i : this->data)
      for (auto &&j : i)
        func(j);
  }
  // 特定の行に操作をする
  template <typename Func> void foreach_row(int r, Func func) {
    if (r < 0 || r >= this->height())
      return;
    for (int j = 0; j < this->width(); j++)
      func(data[r][j]);
  }
  // 特定の列に操作をする
  template <typename Func> void foreach_col(int c, Func func) {
    if (c < 0 || c >= this->width())
      return;
    for (int i = 0; i < this->height(); i++)
      func(data[i][c]);
  }
};
struct Grid : public GenGrid<char> {
  using GenGrid<char>::GenGrid;

  // vector<vector<bool>>型に変換します(tに設定した文字がtrue)
  vector<vector<bool>> change_bool(char t = '#') const {
    vector<vector<bool>> res(H, vector<bool>(W, false));
    for (int i = 0; i < H; i++)
      for (int j = 0; j < W; j++)
        res[i][j] = (data[i][j] == t);
    return res;
  }
};
inline Grid operator+(Grid lhs, const Grid &rhs) {
  lhs += rhs;
  return lhs;
}
inline Grid operator+(Grid lhs, int val) {
  lhs += val;
  return lhs;
}
inline Grid operator-(Grid lhs, int val) {
  lhs -= val;
  return lhs;
}
inline Grid operator*(Grid lhs, int val) {
  lhs *= val;
  return lhs;
}
inline Grid operator/(Grid lhs, int val) {
  lhs /= val;
  return lhs;
}
template <class T, class U>
inline GenGrid<T> operator+(GenGrid<T> lhs, const GenGrid<U> &rhs) {
  lhs += rhs;
  return lhs;
}
template <class T, class U>
inline GenGrid<T> operator+(GenGrid<T> lhs, int val) {
  lhs += val;
  return lhs;
}
template <class T, class U>
inline GenGrid<T> operator-(GenGrid<T> lhs, int val) {
  lhs -= val;
  return lhs;
}
template <class T, class U>
inline GenGrid<T> operator*(GenGrid<T> lhs, int val) {
  lhs *= val;
  return lhs;
}
template <class T, class U>
inline GenGrid<T> operator/(GenGrid<T> lhs, int val) {
  lhs /= val;
  return lhs;
}

template <class T, class U> istream &operator>>(istream &is, pair<T, U> &p) {
  is >> p.first >> p.second;
  return is;
}
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << p.first << " " << p.second;
  return os;
}
template <class C, typename = decltype(begin(declval<C>())),
          typename = enable_if_t<!is_same_v<C, string>>>
istream &operator>>(istream &is, C &c) {
  for (auto &e : c)
    is >> e;
  return is;
}
template <class C, typename = decltype(begin(declval<C>())),
          typename = enable_if_t<!is_same_v<C, string>>>
ostream &operator<<(ostream &os, const C &c) {
  bool f = true;
  for (const auto &e : c)
    os << (f ? "" : " ") << e, f = false;
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v) {
  for (const auto &e : v)
    os << e << endl;
  return os;
}
template <typename T> set<T> read_set(int n) {
  set<T> s;
  for (int i = 0; i < n; ++i) {
    T e;
    cin >> e;
    s.insert(e);
  }
  return s;
}
template <typename T> multiset<T> read_multiset(int n) {
  multiset<T> s;
  for (int i = 0; i < n; ++i) {
    T e;
    cin >> e;
    s.insert(e);
  }
  return s;
}
istream &operator>>(istream &is, Pos &p) {
  is >> p.x >> p.y;
  return is;
}
ostream &operator<<(ostream &os, const Pos &p) {
  os << p.x << " " << p.y;
  return os;
}
istream &operator>>(istream &is, Grid &grid) {
  is >> grid.data;
  grid.reset();
  return is;
}
ostream &operator<<(ostream &os, const Grid &grid) {
  os << grid.data;
  return os;
}
template <class T> istream &operator>>(istream &is, GenGrid<T> &grid) {
  is >> grid.data;
  grid.reset();
  return is;
}
template <class T> ostream &operator<<(ostream &os, const GenGrid<T> &grid) {
  os << grid.data;
  return os;
}

// エラトステネスの篩
struct Sieve {
  int n;
  vector<int> min_prime_factor, primes;
  Sieve(int num = 1) : n(num), min_prime_factor(num + 1) {
    min_prime_factor[0] = min_prime_factor[1] = -1;
    for (int i = 2; i <= n; ++i) {
      if (min_prime_factor[i] == 0) {
        min_prime_factor[i] = i;
        primes.push_back(i);
        for (long long j = (long long)i * i; j <= n; j += i)
          if (min_prime_factor[j] == 0)
            min_prime_factor[j] = i;
      }
    }
  }
  // 素数判定
  bool is_prime(int x) {
    if (x < 2)
      return false;
    return min_prime_factor[x] == x;
  }
};
// べき乗を計算します。
template <typename T, typename Y, typename M>
  requires integral<T> && integral<Y> && integral<M>
int power(T a, Y n, M mod = -1) {
  int res = 1;
  if (mod != -1)
    a %= mod;
  while (n > 0) {
    if (n & 1)
      res = (mod != -1) ? (res * a) % mod : res * a;
    a = (mod != -1) ? (a * a) % mod : a * a;
    n >>= 1;
  }
  return res;
}
// 整数nを素因数分解します。
template <typename T>
  requires integral<T>
map<int, int> prime_factorize(T n) {
  map<int, int> res;
  for (int i = 2; i * i <= n; ++i) {
    while (n % i == 0) {
      res[i]++;
      n /= i;
    }
  }
  if (n != 1)
    res[n] = 1;
  return res;
}
// 整数の各桁の和を計算します。
template <typename T>
  requires integral<T>
int digit_sum(T n) {
  int res = 0;
  n = abs(n);
  while (n > 0) {
    res += n % 10;
    n /= 10;
  }
  return res;
}
// 文字列・整数が回文かどうかを判定します。
bool is_palindrome(const string &s) {
  int n = s.length();
  for (int i = 0; i < n / 2; ++i)
    if (s[i] != s[n - 1 - i])
      return false;
  return true;
}
template <typename T>
  requires integral<T>
bool is_palindrome(const T &val) {
  string s = to_string(val);
  return is_palindrome(s);
}
// 座標圧縮を行います。
template <typename T> vector<int> compress(const vector<T> &v) {
  map<T, int> mp;
  for (const T &e : v)
    mp[e] = 0;
  int id = 0;
  for (auto &p : mp)
    p.second = id++;
  vector<int> res(v.size());
  for (int i = 0; i < (int)v.size(); ++i)
    res[i] = mp[v[i]];
  return res;
}
// ランレングス圧縮を行います
template <typename C>
vector<pair<typename C::value_type, int>> run_length_encoding(const C &s) {
  if (s.empty())
    return {};
  using T = typename C::value_type;
  vector<pair<T, int>> res;
  T current_char = s.front();
  int count = 1;
  for (size_t i = 1; i < s.size(); ++i) {
    if (s[i] == current_char)
      count++;
    else {
      res.push_back({current_char, count});
      current_char = s[i];
      count = 1;
    }
  }
  res.push_back({current_char, count});
  return res;
}
// nCr mod p を高速に計算するための構造体。
struct Combination {
  vector<ll> fact, inv_fact;
  ll MOD;
  // プリコンピュートする階乗の最大値。
  Combination(ll sz, ll mod) : MOD(mod) {
    fact.resize(sz + 1);
    inv_fact.resize(sz + 1);
    fact[0] = 1;
    for (ll i = 1; i <= sz; ++i)
      fact[i] = (fact[i - 1] * i) % MOD;
    inv_fact[sz] = power(fact[sz], MOD - 2, MOD);
    for (ll i = sz - 1; i >= 0; --i)
      inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
  }
  // nCr (n個からr個選ぶ組み合わせの数) を計算します。
  ll nCr(ll n, ll r) {
    return (n < r ? 0
                  : (((fact[n] * inv_fact[r]) % MOD) * inv_fact[n - r]) % MOD);
  }
};
// 文字列の部分文字列のハッシュ値を高速に計算します。
struct RollingHash {
  ll base1 = 1007, base2 = 2009;
  ll mod1 = 1e9 + 7, mod2 = 1e9 + 9;
  vector<ll> hash1, hash2, pow1, pow2;
  RollingHash(const string &s) {
    int n = s.length();
    hash1.resize(n + 1, 0);
    hash2.resize(n + 1, 0);
    pow1.resize(n + 1, 1);
    pow2.resize(n + 1, 1);
    for (int i = 0; i < n; ++i) {
      hash1[i + 1] = (hash1[i] * base1 + s[i]) % mod1;
      hash2[i + 1] = (hash2[i] * base2 + s[i]) % mod2;
      pow1[i + 1] = (pow1[i] * base1) % mod1;
      pow2[i + 1] = (pow2[i] * base2) % mod2;
    }
  }
  // 部分文字列 s[l...r-1] のハッシュ値を取得します。
  P get(int l, int r) {
    ll res1 = (hash1[r] - hash1[l] * pow1[r - l] % mod1 + mod1) % mod1;
    ll res2 = (hash2[r] - hash2[l] * pow2[r - l] % mod2 + mod2) % mod2;
    return {res1, res2};
  }
};
// 常に正の値になる余剰計算
template <typename T, typename Y>
  requires integral<T> && integral<Y>
int modInt(T N, Y mod) {
  return (N % mod + mod) % mod;
}
// 階乗
template <typename T>
  requires integral<T>
int factorial(T N) {
  return (N == 1 ? 1 : factorial(N - 1) * N);
}
// 平方数判定
template <typename T>
  requires integral<T>
bool is_sqrt(T N) {
  int M = sqrt(N);
  return (M * M == N);
}

// 二分探索の拡張
namespace binary {
// val に最も近い要素を指すイテレータを返します。
template <typename Iterator, typename T, typename Compare>
Iterator near(Iterator first, Iterator last, const T &val,
              Compare comp = less<T>()) {
  if (first == last)
    return last;
  Iterator low = lower_bound(first, last, val, comp);
  if (low == first)
    return low;
  if (low == last)
    return prev(low);
  auto diff1 = abs(*low - val);
  auto diff2 = abs(*prev(low) - val);
  return (diff1 < diff2) ? low : prev(low);
}
/*指定した値以上の要素数と、未満の要素数を計算します
firstが以上の要素数で、secondが未満の要素数。*/
template <typename ForwardIterator, typename T, typename Compare>
P count_val(ForwardIterator first, ForwardIterator last, const T &val,
            Compare comp = less<T>()) {
  auto it = lower_bound(first, last, val, comp);
  return {distance(it, last), distance(first, it)};
}
// 閉空間[L,R]に含まれる要素の数を返します。
template <typename ForwardIterator, typename T, typename Compare>
int count_range(ForwardIterator first, ForwardIterator last, const T &L,
                const T &R, Compare comp = less<T>()) {
  return distance(lower_bound(first, last, L, comp),
                  upper_bound(first, last, R, comp));
}
// val以下の最後の要素を探します。
template <typename ForwardIterator, typename T, typename Compare>
ForwardIterator find_le(ForwardIterator first, ForwardIterator last,
                        const T &val, Compare comp = less<T>()) {
  auto it = upper_bound(first, last, val, comp);
  if (it != first)
    return prev(it);
  return last;
}
// val未満の最後の要素を探します。
template <typename ForwardIterator, typename T, typename Compare>
ForwardIterator find_lt(ForwardIterator first, ForwardIterator last,
                        const T &val, Compare comp = less<T>()) {
  auto it = lower_bound(first, last, val, comp);
  if (it != first)
    return prev(it);
  return last;
}
}; // namespace binary

// 累積和を扱う構造体
template <typename T> struct cumulative {
  vector<T> data;
  // コンストラクタ
  cumulative(const vector<T> &v) {
    data.resize(v.size() + 1, 0);
    for (int i = 0; i < v.size(); i++)
      data[i + 1] = data[i] + v[i];
  }
  // 元の配列のサイズを返す
  int size() const { return data.size() - 1; }
  // すべての要素の和を返す
  int sum() const { return data[data.size() - 1]; }
  // [l, r) の区間和を返す (0-indexed)
  T query(int l, int r) const {
    return (l < 0 || r > data.size() - 1 || l > r ? 0 : data[r] - data[l]);
  }
  // [l, data.size() - 1) の区間和を返す (0-indexed)
  T query(int l) const { return (l < 0 ? 0 : data[data.size() - 1] - data[l]); }
  // [l, r] の閉区間和を返す (0-indexed)
  T query_closed(int l, int r) const {
    return (l < 0 || r >= size() || l > r ? 0 : query(l, r + 1));
  }
  // 最大区間和を求めます
  T max_subarray_sum() const {
    if (size() == 0)
      return 0;
    T max_sum = 0, min_prefix_sum = 0;
    for (int i = 1; i < data.size(); i++) {
      chmax(max_sum, data[i] - min_prefix_sum);
      chmin(min_prefix_sum, data[i]);
    }
    return max_sum;
  }
  // 最小区間和を求めます
  T min_subarray_sum() const {
    if (size() == 0)
      return 0;
    T min_sum = 0, max_prefix_sum = 0;
    for (int i = 1; i < data.size(); i++) {
      chmin(min_sum, data[i] - max_prefix_sum);
      chmax(max_prefix_sum, data[i]);
    }
    return min_sum;
  }
  // 和がvalとなる連続部分列が存在するかを判定します
  bool has_subarray_of_sum(T val) const {
    unordered_set<T> seen_sums;
    for (int i = 0; i < data.size(); i++) {
      T cnt_sum = data[i];
      T target = cnt_sum - val;
      if (seen_sums.count(target))
        return true;
      seen_sums.insert(cnt_sum);
    }
    return false;
  }
  /* 和がvalとなる連続部分列[l,r]を一つ見つけます(0-indexed)
  見つからなければnulloptを返します*/
  optional<pair<int, int>> find_subarray_of_sum(T val) const {
    unordered_map<T, int> seen_sums_map;
    for (int i = 0; i < data.size(); ++i) {
      T current_sum = data[i];
      T target = current_sum - val;
      if (seen_sums_map.count(target)) {
        int l = seen_sums_map.at(target);
        int r = i - 1;
        return P{l, r};
      }
      if (seen_sums_map.find(current_sum) == seen_sums_map.end())
        seen_sums_map[current_sum] = i;
    }
    return nullopt;
  }
};
// 2次元累積和を扱う構造体
template <typename T> struct cumulative_2d {
  int H, W;
  vector<vector<T>> data;
  cumulative_2d(const vector<vector<T>> &v) {
    H = v.size();
    W = v.empty() ? 0 : v[0].size();
    data.assign(H + 1, vector<T>(W + 1, 0));
    for (int i = 0; i < H; ++i)
      for (int j = 0; j < W; ++j)
        data[i + 1][j + 1] =
            v[i][j] + data[i][j + 1] + data[i + 1][j] - data[i][j];
  }
  size_t height() const { return H; }
  size_t size() const { return H; }
  size_t width() const { return W; }
  // すべての要素の和
  T sum() const { return data[H][W]; }
  // 左上(r1, c1), 右下(r2-1, c2-1)の半開区間の和を返す (0-indexed)
  T query(int r1, int c1, int r2, int c2) const {
    return (r1 < 0 || r2 > H || c1 < 0 || c2 > W || r1 > r2 || c1 > c2
                ? 0
                : data[r2][c2] - data[r1][c2] - data[r2][c1] + data[r1][c1]);
  }
  // 左上(r1, c1), 右下(r2, c2)の閉区間の和を返す (0-indexed)
  T query_closed(int r1, int c1, int r2, int c2) const {
    return query(r1, c1, r2 + 1, c2 + 1);
  }
  template <typename X, typename Y, typename Z>
    requires integral<X> && integral<Y> && integral<Z>
  void add(X x, Y y, Z z) {
    x++;
    y++;
    if (x >= data.size() || y >= data[0].size())
      return;
    data[x][y] += z;
  }
};
// 時間
struct Time {
  int hour, minute, second;
  Time(int h = 0, int min = 0, int s = 0) : hour(h), minute(min), second(s) {
    normalize();
  };
  Time(Time &t) : hour(t.hour), minute(t.minute), second(t.second) {
    normalize();
  };
  static Time from_total_seconds(int secs) {
    return Time{secs / 360, (secs % 3600) / 60, secs % 60};
  }
  // 正規化
  void normalize() {
    int total_sec = this->totalsec();
    hour = total_sec / 3600;
    int remain = total_sec % 3600;
    if (remain < 0) {
      remain += 3600;
      hour -= 1;
    }
    minute = remain / 60;
    second = remain % 60;
  }
  int totalsec() const { return hour * 3600 + minute * 60 + second; }
  int totalmin() const { return hour * 60 + minute; }
  Time &operator+=(const Time &other) {
    this->hour += other.hour;
    this->minute += other.minute;
    this->second += other.second;
    this->normalize();
    return *this;
  }
  Time &operator-=(const Time &other) {
    this->hour -= other.hour;
    this->minute -= other.minute;
    this->second -= other.second;
    this->normalize();
    return *this;
  }
  Time &operator*=(int scalar) {
    int total_sec = this->totalsec();
    total_sec *= scalar;
    *this = Time::from_total_seconds(total_sec);
    return *this;
  }
  triple<int, int, int> to_triple() {
    return triple<int, int, int>(hour, minute, second);
  }
  bool operator==(const Time &other) const {
    return this->totalsec() == other.totalsec();
  }
  bool operator!=(const Time &other) const { return !(*this == other); }
  bool operator<(const Time &other) const {
    return this->totalsec() < other.totalsec();
  }
  bool operator>(const Time &other) const {
    return this->totalsec() > other.totalsec();
  }
  bool operator<=(const Time &other) const {
    return this->totalsec() <= other.totalsec();
  }
  bool operator>=(const Time &other) const {
    return this->totalsec() >= other.totalsec();
  }
};
Time operator+(Time lhs, const Time &rhs) { return lhs += rhs; }
Time operator-(Time lhs, const Time &rhs) { return lhs -= rhs; }
Time operator*(Time t, long long s) { return t *= s; }
Time operator*(long long s, Time t) { return t *= s; }
template <typename T> vector<pair<T, int>> RLE(vector<T> data) {
  if (data.empty())
    return vector<pair<T, int>>{};
  if (data.size() == 1)
    return vector<pair<T, int>>{{data[0], 1}};
  vector<pair<T, int>> res;
  T last = data[0];
  int last_t = 0;
  for (int i = 1; i < data.size(); i++) {
    if (last == data[i])
      continue;
    else {
      res.push_back({last, i - last_t});
      last_t = i;
      last = data[i];
    }
  }
  if (last_t != data.size())
    res.push_back({last, data.size() - last_t});
  return res;
}
vector<pair<char, int>> RLE(string S) {
  vector<char> Sc(S.size());
  for (int i = 0; i < S.size(); i++) {
    Sc[i] = S[i];
  }
  return RLE(Sc);
}
template <typename T> struct RleVector {
private:
  vector<pair<T, size_t>> data;

public:
  RleVector() = default;
  RleVector(const vector<T> &v) {
    if (v.empty())
      return;
    for (const T &val : v)
      this->push_back(val);
    this->combine();
  }
  size_t size() const { return (data.empty() ? 0 : data.back().second); }
  bool empty() const { return data.empty(); }
  size_t num_runs() const { return data.size(); }
  void clear() { data.clear(); }
  const T &at(size_t idx) const {
    if (idx >= this->size())
      throw out_of_range("RleVector::at");
    auto it = lower_bound(all(data), idx + 1,
                          [](const pair<T, size_t> &element, size_t val) {
                            return element.second < val;
                          });
    return it->first;
  }
  const T &operator[](size_t idx) const { return at(idx); }
  const T &front() const { return data.front.first; }
  const T &back() const { return data.back().first; }
  void push_back(const T &val, size_t count = 1) {
    if (count == 0)
      return;
    if (data.empty()) {
      data.push_back({val, count});
      return;
    }
    if (val == data.back().first)
      data.back().second += count;
    else {
      size_t prev_size = data.back().second;
      data.push_back({val, prev_size + count});
    }
  }
  void pop_back() {
    if (data.empty())
      return;
    size_t prev_size = (data.size() > 1) ? data[data.size() - 2].second : 0;
    if (data.back().second == prev_size + 1)
      data.pop_back();
    else
      data.back().second--;
  }
  void combine() {
    if (data.size() <= 1)
      return;
    vector<pair<T, size_t>> new_data;
    new_data.push_back(data[0]);
    new_data.back().second = data[0].second;
    for (size_t i = 1; i < data.size(); ++i) {
      new_data.push_back({data[i].first, data[i].second - data[i - 1].second});
    }
    vector<pair<T, size_t>> combined;
    if (!new_data.empty()) {
      combined.push_back(new_data[0]);
      for (size_t i = 1; i < new_data.size(); i++) {
        if (new_data[i].first == combined.back().first)
          combined.back().second += new_data[i].second;
        else
          combined.push_back(new_data[i]);
      }
    }
    data = combined;
    for (size_t i = 1; i < data.size(); i++)
      data[i].second += data[i - 1].second;
  }
  vector<pair<T, size_t>> get_raw_data() {
    combine();
    return data;
  }
  vector<pair<T, size_t>> get_diff_data() {
    combine();
    vector<pair<T, size_t>> res(data.size());
    res[0] = data[0];
    for (int i = 1; i < res.size(); i++) {
      res[i] = data[i];
      res[i].second -= data[i - 1].second;
    }
    return res;
  }
  void output_diff_data() {
    auto out_data = this->get_diff_data();
    for (auto &&i : out_data)
      cerr << "{data: " << i.first << ", count: " << i.second << "}" << endl;
  }
  vector<T> to_vec() {
    vector<pair<T, size_t>> diff_data = this->get_diff_data();
    vector<T> res;
    for (auto &i : diff_data)
      for (int j = 0; j < i.second; j++)
        res.push_back(i.first);
    return res;
  }
};

signed main() {
  int N, A, B;
  cin >> N >> A >> B;
  vector<vector<bool>> takahashi(507, vector<bool>(507));
  auto aoki = takahashi;
  for (int i = 0; i < A; i++) {
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    for (int r = r1; r <= r2; r++) {
      for (int c = c1; c <= c2; c++) {
        takahashi[r][c] = true;
      }
    }
  }
  for (int i = 0; i < B; i++) {
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    for (int r = r1; r <= r2; r++) {
      for (int c = c1; c <= c2; c++) {
        aoki[r][c] = true;
      }
    }
  }
  int ans = 0;
  for (int r = 1; r <= N; r++) {
    for (int c = 1; c <= N; c++) {
      if (takahashi[r][c] && aoki[r][c]) {
        ans++;
      }
    }
  }
  cout << ans << endl;

  return 0;
}

Submission Info

Compile Error

./Main.cpp: In member function 'Time& Time::operator*=(long long int)':
./Main.cpp:1414:47: warning: implicitly-declared 'constexpr Time& Time::operator=(const Time&)' is deprecated [-Wdeprecated-copy]
 1414 |     *this = Time::from_total_seconds(total_sec);
      |                                               ^
./Main.cpp:1377:3: note: because 'Time' has user-provided 'Time::Time(Time&)'
 1377 |   Time(Time &t) : hour(t.hour), minute(t.minute), second(t.second) {
      |   ^~~~
./Main.cpp: In function 'std::vector<std::pair<char, long long int> > RLE(std::string)':
./Main.cpp:1464:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
 1464 |   for (int i = 0; i < S.size(); i++) {
      |                   ~~^~~~~~~~~~
./Main.cpp: In instantiation of 'std::vector<std::pair<T, long long int> > RLE(std::vector<_Tp>) [with T = char]':
./Main.cpp:1467:13:   required from here
 1467 |   return RLE(Sc);
      |          ~~~^~~~
./Main.cpp:1449:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<char, std::allocator<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
 1449 |   for (int i = 1; i < data.size(); i++) {
      |                   ~~^~~~~~~~~~~~~
./Main.cpp:1458:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<char, std::allocator<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
 1458 |   if (last_t != data.size())
      |       ~~~~~~~^~~~~~~~~~~~~~

Judge Result