QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#74278#5443. Security at Museumsjapan022022RE 571ms5540kbC++2032.1kb2023-01-31 13:02:002023-01-31 13:02:01

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-31 13:02:01]
  • 评测
  • 测评结果:RE
  • 用时:571ms
  • 内存:5540kb
  • [2023-01-31 13:02:00]
  • 提交

answer

#line 1 "library/my_template.hpp"
#if defined(LOCAL)
#include <my_template_compiled.hpp>
#else
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;

template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

#define vv(type, name, h, ...) \
  vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...)   \
  vector<vector<vector<type>>> name( \
      h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...)       \
  vector<vector<vector<vector<type>>>> name( \
      a, vector<vector<vector<type>>>(       \
             b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))

// https://trap.jp/post/1224/
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)

#define FOR_subset(t, s) \
  for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if

#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second

#define stoi stoll

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }

template <typename T, typename U>
T ceil(T x, U y) {
  return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U>
T floor(T x, U y) {
  return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T, typename U>
pair<T, T> divmod(T x, U y) {
  T q = floor(x, y);
  return {q, x - q * y};
}

template <typename T, typename U>
T SUM(const vector<U> &A) {
  T sum = 0;
  for (auto &&a: A) sum += a;
  return sum;
}

#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) \
  sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()

template <typename T>
T POP(deque<T> &que) {
  T a = que.front();
  que.pop_front();
  return a;
}
template <typename T>
T POP(pq<T> &que) {
  T a = que.top();
  que.pop();
  return a;
}
template <typename T>
T POP(pqg<T> &que) {
  assert(!que.empty());
  T a = que.top();
  que.pop();
  return a;
}
template <typename T>
T POP(vc<T> &que) {
  assert(!que.empty());
  T a = que.back();
  que.pop_back();
  return a;
}

template <typename F>
ll binary_search(F check, ll ok, ll ng) {
  assert(check(ok));
  while (abs(ok - ng) > 1) {
    auto x = (ng + ok) / 2;
    tie(ok, ng) = (check(x) ? mp(x, ng) : mp(ok, x));
  }
  return ok;
}
template <typename F>
double binary_search_real(F check, double ok, double ng, int iter = 100) {
  FOR(iter) {
    double x = (ok + ng) / 2;
    tie(ok, ng) = (check(x) ? mp(x, ng) : mp(ok, x));
  }
  return (ok + ng) / 2;
}

template <class T, class S>
inline bool chmax(T &a, const S &b) {
  return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
  return (a > b ? a = b, 1 : 0);
}

// ? は -1
vc<int> s_to_vi(const string &S, char first_char) {
  vc<int> A(S.size());
  FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); }
  return A;
}

template <typename T, typename U>
vector<T> cumsum(vector<U> &A, int off = 1) {
  int N = A.size();
  vector<T> B(N + 1);
  FOR(i, N) { B[i + 1] = B[i] + A[i]; }
  if (off == 0) B.erase(B.begin());
  return B;
}

// stable sort
template <typename T>
vector<int> argsort(const vector<T> &A) {
  vector<int> ids(len(A));
  iota(all(ids), 0);
  sort(all(ids),
       [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
  return ids;
}

// A[I[0]], A[I[1]], ...
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
  vc<T> B(len(I));
  FOR(i, len(I)) B[i] = A[I[i]];
  return B;
}
#endif
#line 1 "library/other/io.hpp"
// based on yosupo's fastio
#include <unistd.h>

namespace fastio {
#define FASTIO
// クラスが read(), print() を持っているかを判定するメタ関数
struct has_write_impl {
  template <class T>
  static auto check(T &&x) -> decltype(x.write(), std::true_type{});

  template <class T>
  static auto check(...) -> std::false_type;
};

template <class T>
class has_write : public decltype(has_write_impl::check<T>(std::declval<T>())) {
};

struct has_read_impl {
  template <class T>
  static auto check(T &&x) -> decltype(x.read(), std::true_type{});

  template <class T>
  static auto check(...) -> std::false_type;
};

template <class T>
class has_read : public decltype(has_read_impl::check<T>(std::declval<T>())) {};

struct Scanner {
  FILE *fp;
  char line[(1 << 15) + 1];
  size_t st = 0, ed = 0;
  void reread() {
    memmove(line, line + st, ed - st);
    ed -= st;
    st = 0;
    ed += fread(line + ed, 1, (1 << 15) - ed, fp);
    line[ed] = '\0';
  }
  bool succ() {
    while (true) {
      if (st == ed) {
        reread();
        if (st == ed) return false;
      }
      while (st != ed && isspace(line[st])) st++;
      if (st != ed) break;
    }
    if (ed - st <= 50) {
      bool sep = false;
      for (size_t i = st; i < ed; i++) {
        if (isspace(line[i])) {
          sep = true;
          break;
        }
      }
      if (!sep) reread();
    }
    return true;
  }
  template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
  bool read_single(T &ref) {
    if (!succ()) return false;
    while (true) {
      size_t sz = 0;
      while (st + sz < ed && !isspace(line[st + sz])) sz++;
      ref.append(line + st, sz);
      st += sz;
      if (!sz || st != ed) break;
      reread();
    }
    return true;
  }
  template <class T, enable_if_t<is_integral<T>::value, int> = 0>
  bool read_single(T &ref) {
    if (!succ()) return false;
    bool neg = false;
    if (line[st] == '-') {
      neg = true;
      st++;
    }
    ref = T(0);
    while (isdigit(line[st])) { ref = 10 * ref + (line[st++] & 0xf); }
    if (neg) ref = -ref;
    return true;
  }
  template <typename T,
            typename enable_if<has_read<T>::value>::type * = nullptr>
  inline bool read_single(T &x) {
    x.read();
    return true;
  }
  bool read_single(double &ref) {
    string s;
    if (!read_single(s)) return false;
    ref = std::stod(s);
    return true;
  }
  bool read_single(char &ref) {
    string s;
    if (!read_single(s) || s.size() != 1) return false;
    ref = s[0];
    return true;
  }
  template <class T>
  bool read_single(vector<T> &ref) {
    for (auto &d: ref) {
      if (!read_single(d)) return false;
    }
    return true;
  }
  template <class T, class U>
  bool read_single(pair<T, U> &p) {
    return (read_single(p.first) && read_single(p.second));
  }
  template <size_t N = 0, typename T>
  void read_single_tuple(T &t) {
    if constexpr (N < std::tuple_size<T>::value) {
      auto &x = std::get<N>(t);
      read_single(x);
      read_single_tuple<N + 1>(t);
    }
  }
  template <class... T>
  bool read_single(tuple<T...> &tpl) {
    read_single_tuple(tpl);
    return true;
  }
  void read() {}
  template <class H, class... T>
  void read(H &h, T &... t) {
    bool f = read_single(h);
    assert(f);
    read(t...);
  }
  Scanner(FILE *fp) : fp(fp) {}
};

struct Printer {
  Printer(FILE *_fp) : fp(_fp) {}
  ~Printer() { flush(); }

  static constexpr size_t SIZE = 1 << 15;
  FILE *fp;
  char line[SIZE], small[50];
  size_t pos = 0;
  void flush() {
    fwrite(line, 1, pos, fp);
    pos = 0;
  }
  void write(const char val) {
    if (pos == SIZE) flush();
    line[pos++] = val;
  }
  template <class T, enable_if_t<is_integral<T>::value, int> = 0>
  void write(T val) {
    if (pos > (1 << 15) - 50) flush();
    if (val == 0) {
      write('0');
      return;
    }
    if (val < 0) {
      write('-');
      val = -val; // todo min
    }
    size_t len = 0;
    while (val) {
      small[len++] = char(0x30 | (val % 10));
      val /= 10;
    }
    for (size_t i = 0; i < len; i++) { line[pos + i] = small[len - 1 - i]; }
    pos += len;
  }
  void write(const string s) {
    for (char c: s) write(c);
  }
  void write(const char *s) {
    size_t len = strlen(s);
    for (size_t i = 0; i < len; i++) write(s[i]);
  }
  void write(const double x) {
    ostringstream oss;
    oss << fixed << setprecision(15) << x;
    string s = oss.str();
    write(s);
  }
  void write(const long double x) {
    ostringstream oss;
    oss << fixed << setprecision(15) << x;
    string s = oss.str();
    write(s);
  }
  template <typename T,
            typename enable_if<has_write<T>::value>::type * = nullptr>
  inline void write(T x) {
    x.write();
  }
  template <class T>
  void write(const vector<T> val) {
    auto n = val.size();
    for (size_t i = 0; i < n; i++) {
      if (i) write(' ');
      write(val[i]);
    }
  }
  template <class T, class U>
  void write(const pair<T, U> val) {
    write(val.first);
    write(' ');
    write(val.second);
  }
  template <size_t N = 0, typename T>
  void write_tuple(const T t) {
    if constexpr (N < std::tuple_size<T>::value) {
      if constexpr (N > 0) { write(' '); }
      const auto x = std::get<N>(t);
      write(x);
      write_tuple<N + 1>(t);
    }
  }
  template <class... T>
  bool write(tuple<T...> tpl) {
    write_tuple(tpl);
    return true;
  }
  template <class T, size_t S>
  void write(const array<T, S> val) {
    auto n = val.size();
    for (size_t i = 0; i < n; i++) {
      if (i) write(' ');
      write(val[i]);
    }
  }
  void write(i128 val) {
    string s;
    bool negative = 0;
    if (val < 0) {
      negative = 1;
      val = -val;
    }
    while (val) {
      s += '0' + int(val % 10);
      val /= 10;
    }
    if (negative) s += "-";
    reverse(all(s));
    if (len(s) == 0) s = "0";
    write(s);
  }
};
Scanner scanner = Scanner(stdin);
Printer printer = Printer(stdout);
void flush() { printer.flush(); }
void print() { printer.write('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
  printer.write(head);
  if (sizeof...(Tail)) printer.write(' ');
  print(forward<Tail>(tail)...);
}

void read() {}
template <class Head, class... Tail>
void read(Head &head, Tail &... tail) {
  scanner.read(head);
  read(tail...);
}
} // namespace fastio
using fastio::print;
using fastio::flush;
using fastio::read;

#define INT(...)   \
  int __VA_ARGS__; \
  read(__VA_ARGS__)
#define LL(...)   \
  ll __VA_ARGS__; \
  read(__VA_ARGS__)
#define STR(...)      \
  string __VA_ARGS__; \
  read(__VA_ARGS__)
#define CHAR(...)   \
  char __VA_ARGS__; \
  read(__VA_ARGS__)
#define DBL(...)      \
  double __VA_ARGS__; \
  read(__VA_ARGS__)

#define VEC(type, name, size) \
  vector<type> name(size);    \
  read(name)
#define VV(type, name, h, w)                     \
  vector<vector<type>> name(h, vector<type>(w)); \
  read(name)

void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
#line 2 "library/geo/base.hpp"
template <typename T>
struct Point {
  T x, y;

  Point() = default;

  template <typename A, typename B>
  Point(A x, B y) : x(x), y(y) {}

  template <typename A, typename B>
  Point(pair<A, B> p) : x(p.fi), y(p.se) {}

  Point operator+(Point p) const { return {x + p.x, y + p.y}; }
  Point operator-(Point p) const { return {x - p.x, y - p.y}; }
  bool operator==(Point p) const { return x == p.x && y == p.y; }
  Point operator-() const { return {-x, -y}; }

  bool operator<(Point p) const {
    if (x != p.x) return x < p.x;
    return y < p.y;
  }
  T dot(Point other) { return x * other.x + y * other.y; }
  T det(Point other) { return x * other.y - y * other.x; }

  void read() { fastio::read(x), fastio::read(y); }
  void write() { fastio::printer.write(pair<T, T>({x, y})); }
};

template <typename REAL, typename T>
REAL dist(Point<T> A, Point<T> B) {
  A = A - B;
  T p = A.dot(A);
  return sqrt(REAL(p));
}

template <typename T>
struct Line {
  T a, b, c;

  Line(T a, T b, T c) : a(a), b(b), c(c) {}
  Line(Point<T> A, Point<T> B) {
    a = A.y - B.y;
    b = B.x - A.x;
    c = A.x * B.y - A.y * B.x;
  }
  Line(T x1, T y1, T x2, T y2) : Line(Point<T>(x1, y1), Point<T>(x2, y2)) {}

  template <typename U>
  U eval(Point<U> P) {
    return a * P.x + b * P.y + c;
  }

  template <typename U>
  T eval(U x, U y) {
    return a * x + b * y + c;
  }

  bool is_parallel(Line other) { return a * other.b - b * other.a == 0; }

  bool is_orthogonal(Line other) { return a * other.a + b * other.b == 0; }
};

template <typename T>
struct Segment {
  Point<T> A, B;

  Segment(Point<T> A, Point<T> B) : A(A), B(B) {}
  Segment(T x1, T y1, T x2, T y2)
      : Segment(Point<T>(x1, y1), Point<T>(x2, y2)) {}

  template <enable_if_t<is_integral<T>::value, int> = 0>
  bool contain(Point<T> C) {
    T det = (C - A).det(B - A);
    if (det != 0) return 0;
    return (C - A).dot(B - A) >= 0 && (C - B).dot(A - B) >= 0;
  }

  Line<T> to_Line() { return Line(A, B); }
};

template <typename T>
struct Circle {
  Point<T> O;
  T r;
  Circle(Point<T> O, T r) : O(O), r(r) {}
  Circle(T x, T y, T r) : O(Point<T>(x, y)), r(r) {}
};

template <typename T>
struct Polygon {
  vc<Point<T>> points;
  T a;

  template <typename A, typename B>
  Polygon(vc<pair<A, B>> pairs) {
    for (auto&& [a, b]: pairs) points.eb(Point<T>(a, b));
    build();
  }
  Polygon(vc<Point<T>> points) : points(points) { build(); }

  int size() { return len(points); }

  template <typename REAL>
  REAL area() {
    return a * 0.5;
  }

  template <enable_if_t<is_integral<T>::value, int> = 0>
  T area_2() {
    return a;
  }

  bool is_convex() {
    FOR(j, len(points)) {
      int i = (j == 0 ? len(points) - 1 : j - 1);
      int k = (j == len(points) - 1 ? 0 : j + 1);
      if ((points[j] - points[i]).det(points[k] - points[j]) < 0) return false;
    }
    return true;
  }

private:
  void build() {
    a = 0;
    FOR(i, len(points)) {
      int j = (i + 1 == len(points) ? 0 : i + 1);
      a += points[i].det(points[j]);
    }
    if (a < 0) {
      a = -a;
      reverse(all(points));
    }
  }
};
#line 2 "library/geo/cross_point.hpp"

// 平行でないことを仮定
template <typename REAL, typename T>
Point<REAL> cross_point(const Line<T> L1, const Line<T> L2) {
  T det = L1.a * L2.b - L1.b * L2.a;
  assert(det != 0);
  REAL x = -REAL(L1.c) * L2.b + REAL(L1.b) * L2.c;
  REAL y = -REAL(L1.a) * L2.c + REAL(L1.c) * L2.a;
  return Point<REAL>(x / det, y / det);
}

// 0: 交点なし
// 1: 一意な交点
// 2:2 つ以上の交点(整数型を利用して厳密にやる)
template <typename T, enable_if_t<is_integral<T>::value, int> = 0>
int count_cross(Segment<T> S1, Segment<T> S2, bool include_ends) {
  Line<T> L1 = S1.to_Line();
  Line<T> L2 = S2.to_Line();
  if (L1.is_parallel(L2)) {
    if (L1.eval(S2.A) != 0) return 0;
    // 4 点とも同一直線上にある
    T a1 = S1.A.x, b1 = S1.B.x;
    T a2 = S2.A.x, b2 = S2.B.x;
    if (a1 == b1) {
      a1 = S1.A.y, b1 = S1.B.y;
      a2 = S2.A.y, b2 = S2.B.y;
    }
    if (a1 > b1) swap(a1, b1);
    if (a2 > b2) swap(a2, b2);
    T a = max(a1, a2);
    T b = min(b1, b2);
    if (a < b) return 2;
    if (a > b) return 0;
    return (include_ends ? 1 : 0);
  }
  // 平行でない場合
  T a1 = L2.eval(S1.A), b1 = L2.eval(S1.B);
  T a2 = L1.eval(S2.A), b2 = L1.eval(S2.B);
  if (a1 > b1) swap(a1, b1);
  if (a2 > b2) swap(a2, b2);
  bool ok1 = 0, ok2 = 0;

  if (include_ends) {
    ok1 = (a1 <= 0) && (0 <= b1);
    ok2 = (a2 <= 0) && (0 <= b2);
  } else {
    ok1 = (a1 < 0) && (0 < b1);
    ok2 = (a2 < 0) && (0 < b2);
  }
  return (ok1 && ok2 ? 1 : 0);
}

// 0 または 1
// real だと誤差によっては間違った答を返す可能性あり。
/*
template <typename T>
int count_cross(Segment<T> S1, Segment<T> S2) {
  Line<T> L1 = S1.to_Line();
  Line<T> L2 = S2.to_Line();
  T a1 = L2.eval(S1.A), b1 = L2.eval(S1.B);
  T a2 = L1.eval(S2.A), b2 = L1.eval(S2.B);
  if (a1 > b1) swap(a1, b1);
  if (a2 > b2) swap(a2, b2);
  bool ok1 = 0, ok2 = 0;
  ok1 = (a1 <= 0) && (0 <= b1);
  ok2 = (a2 <= 0) && (0 <= b2);
  return (ok1 && ok2 ? 1 : 0);
}
*/

// 唯一の交点を持つことを仮定
template <typename REAL, typename T>
Point<REAL> cross_point(Segment<T> S1, Segment<T> S2) {
  Line<T> L1 = S1.to_Line();
  Line<T> L2 = S2.to_Line();
  return cross_point<REAL, T>(L1, L2);
}
#line 2 "library/mod/modint.hpp"

template <int mod>
struct modint {
  int val;
  constexpr modint(ll x = 0) noexcept {
    if (0 <= x && x < mod)
      val = x;
    else {
      x %= mod;
      val = (x < 0 ? x + mod : x);
    }
  }
  bool operator<(const modint &other) const {
    return val < other.val;
  } // To use std::map
  modint &operator+=(const modint &p) {
    if ((val += p.val) >= mod) val -= mod;
    return *this;
  }
  modint &operator-=(const modint &p) {
    if ((val += mod - p.val) >= mod) val -= mod;
    return *this;
  }
  modint &operator*=(const modint &p) {
    val = (int)(1LL * val * p.val % mod);
    return *this;
  }
  modint &operator/=(const modint &p) {
    *this *= p.inverse();
    return *this;
  }
  modint operator-() const { return modint(-val); }
  modint operator+(const modint &p) const { return modint(*this) += p; }
  modint operator-(const modint &p) const { return modint(*this) -= p; }
  modint operator*(const modint &p) const { return modint(*this) *= p; }
  modint operator/(const modint &p) const { return modint(*this) /= p; }
  bool operator==(const modint &p) const { return val == p.val; }
  bool operator!=(const modint &p) const { return val != p.val; }
  modint inverse() const {
    int a = val, b = mod, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b), swap(u -= t * v, v);
    }
    return modint(u);
  }
  modint pow(int64_t n) const {
    modint ret(1), mul(val);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
#ifdef FASTIO
  void write() { fastio::printer.write(val); }
  void read() {
    ll x;
    fastio::scanner.read(x);
    if (x < 0 || x >= mod) x %= mod;
    if (x < 0) x += mod;
    val += x;
  }
#endif
  static constexpr int get_mod() { return mod; }
};

struct ArbitraryModInt {
  static constexpr bool is_modint = true;
  int val;
  ArbitraryModInt() : val(0) {}
  ArbitraryModInt(int64_t y)
      : val(y >= 0 ? y % get_mod()
                   : (get_mod() - (-y) % get_mod()) % get_mod()) {}
  bool operator<(const ArbitraryModInt &other) const {
    return val < other.val;
  } // To use std::map<ArbitraryModInt, T>
  static int &get_mod() {
    static int mod = 0;
    return mod;
  }
  static void set_mod(int md) { get_mod() = md; }
  ArbitraryModInt &operator+=(const ArbitraryModInt &p) {
    if ((val += p.val) >= get_mod()) val -= get_mod();
    return *this;
  }
  ArbitraryModInt &operator-=(const ArbitraryModInt &p) {
    if ((val += get_mod() - p.val) >= get_mod()) val -= get_mod();
    return *this;
  }
  ArbitraryModInt &operator*=(const ArbitraryModInt &p) {
    long long a = (long long)val * p.val;
    int xh = (int)(a >> 32), xl = (int)a, d, m;
    asm("divl %4; \n\t" : "=a"(d), "=d"(m) : "d"(xh), "a"(xl), "r"(get_mod()));
    val = m;
    return *this;
  }
  ArbitraryModInt &operator/=(const ArbitraryModInt &p) {
    *this *= p.inverse();
    return *this;
  }
  ArbitraryModInt operator-() const { return ArbitraryModInt(get_mod() - val); }
  ArbitraryModInt operator+(const ArbitraryModInt &p) const {
    return ArbitraryModInt(*this) += p;
  }
  ArbitraryModInt operator-(const ArbitraryModInt &p) const {
    return ArbitraryModInt(*this) -= p;
  }
  ArbitraryModInt operator*(const ArbitraryModInt &p) const {
    return ArbitraryModInt(*this) *= p;
  }
  ArbitraryModInt operator/(const ArbitraryModInt &p) const {
    return ArbitraryModInt(*this) /= p;
  }
  bool operator==(const ArbitraryModInt &p) const { return val == p.val; }
  bool operator!=(const ArbitraryModInt &p) const { return val != p.val; }
  ArbitraryModInt inverse() const {
    int a = val, b = get_mod(), u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b), swap(u -= t * v, v);
    }
    return ArbitraryModInt(u);
  }
  ArbitraryModInt pow(int64_t n) const {
    ArbitraryModInt ret(1), mul(val);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
#ifdef FASTIO
  void write() { fastio::printer.write(val); }
  void read() { fastio::scanner.read(val); }
#endif
};

template <typename mint>
mint inv(int n) {
  static const int mod = mint::get_mod();
  static vector<mint> dat = {0, 1};
  assert(0 <= n);
  if (n >= mod) n %= mod;
  while (int(dat.size()) <= n) {
    int k = dat.size();
    auto q = (mod + k - 1) / k;
    int r = k * q - mod;
    dat.emplace_back(dat[r] * mint(q));
  }
  return dat[n];
}

template <typename mint>
mint fact(int n) {
  static const int mod = mint::get_mod();
  static vector<mint> dat = {1, 1};
  assert(0 <= n);
  if (n >= mod) return 0;
  while (int(dat.size()) <= n) {
    int k = dat.size();
    dat.emplace_back(dat[k - 1] * mint(k));
  }
  return dat[n];
}

template <typename mint>
mint fact_inv(int n) {
  static const int mod = mint::get_mod();
  static vector<mint> dat = {1, 1};
  assert(-1 <= n && n < mod);
  if (n == -1) return mint(0);
  while (int(dat.size()) <= n) {
    int k = dat.size();
    dat.emplace_back(dat[k - 1] * inv<mint>(k));
  }
  return dat[n];
}

template <class mint, class... Ts>
mint fact_invs(Ts... xs) {
  return (mint(1) * ... * fact_inv<mint>(xs));
}

template <typename mint, class Head, class... Tail>
mint multinomial(Head &&head, Tail &&... tail) {
  return fact<mint>(head) * fact_invs<mint>(std::forward<Tail>(tail)...);
}

template <typename mint>
mint C_dense(int n, int k) {
  static vvc<mint> C;
  static int H = 0, W = 0;

  auto calc = [&](int i, int j) -> mint {
    if (i == 0) return (j == 0 ? mint(1) : mint(0));
    return C[i - 1][j] + (j ? C[i - 1][j - 1] : 0);
  };

  if (W <= k) {
    FOR(i, H) {
      C[i].resize(k + 1);
      FOR(j, W, k + 1) { C[i][j] = calc(i, j); }
    }
    W = k + 1;
  }
  if (H <= n) {
    C.resize(n + 1);
    FOR(i, H, n + 1) {
      C[i].resize(W);
      FOR(j, W) { C[i][j] = calc(i, j); }
    }
    H = n + 1;
  }
  return C[n][k];
}

template <typename mint, bool large = false, bool dense = false>
mint C(ll n, ll k) {
  assert(n >= 0);
  if (k < 0 || n < k) return 0;
  if (dense) return C_dense<mint>(n, k);
  if (!large) return fact<mint>(n) * fact_inv<mint>(k) * fact_inv<mint>(n - k);
  k = min(k, n - k);
  mint x(1);
  FOR(i, k) { x *= mint(n - i); }
  x *= fact_inv<mint>(k);
  return x;
}

template <typename mint, bool large = false>
mint C_inv(ll n, ll k) {
  assert(n >= 0);
  assert(0 <= k && k <= n);
  if (!large) return fact_inv<mint>(n) * fact<mint>(k) * fact<mint>(n - k);
  return mint(1) / C<mint, 1>(n, k);
}

// [x^d] (1-x) ^ {-n} の計算
template <typename mint, bool large = false, bool dense = false>
mint C_negative(ll n, ll d) {
  assert(n >= 0);
  if (d < 0) return mint(0);
  if (n == 0) { return (d == 0 ? mint(1) : mint(0)); }
  return C<mint, large, dense>(n + d - 1, d);
}

using modint107 = modint<1000000007>;
using modint998 = modint<998244353>;
using amint = ArbitraryModInt;
#line 2 "library/nt/primetable.hpp"

template <typename T = long long>
vc<T> primetable(int LIM) {
  ++LIM;
  const int S = 32768;
  static int done = 2;
  static vc<T> primes = {2}, sieve(S + 1);

  if (done < LIM) {
    done = LIM;

    primes = {2}, sieve.assign(S + 1, 0);
    const int R = LIM / 2;
    primes.reserve(int(LIM / log(LIM) * 1.1));
    vc<pair<int, int>> cp;
    for (int i = 3; i <= S; i += 2) {
      if (!sieve[i]) {
        cp.eb(i, i * i / 2);
        for (int j = i * i; j <= S; j += 2 * i) sieve[j] = 1;
      }
    }
    for (int L = 1; L <= R; L += S) {
      array<bool, S> block{};
      for (auto& [p, idx]: cp)
        for (int i = idx; i < S + L; idx = (i += p)) block[i - L] = 1;
      FOR(i, min(S, R - L)) if (!block[i]) primes.eb((L + i) * 2 + 1);
    }
  }
  int k = LB(primes, LIM + 1);
  return {primes.begin(), primes.begin() + k};
}
#line 3 "library/mod/powertable.hpp"

// a^0, ..., a^N
template <typename mint>
vc<mint> powertable_1(mint a, ll N) {
  // table of a^i
  vc<mint> f(N + 1, 1);
  FOR(i, N) f[i + 1] = a * f[i];
  return f;
}

// 0^e, ..., N^e
template <typename mint>
vc<mint> powertable_2(ll e, ll N) {
  auto primes = primetable(N);
  vc<mint> f(N + 1, 1);
  f[0] = mint(0).pow(e);
  for (auto&& p: primes) {
    if (p > N) break;
    mint xp = mint(p).pow(e);
    ll pp = p;
    while (pp <= N) {
      ll i = pp;
      while (i <= N) {
        f[i] *= xp;
        i += pp;
      }
      pp *= p;
    }
  }
  return f;
}
#line 2 "library/geo/angle_sort.hpp"

#line 4 "library/geo/angle_sort.hpp"

// 偏角ソートに対する argsort
template <typename T>
vector<int> angle_argsort(vector<Point<T>>& P) {
  vector<int> lower, origin, upper;
  const Point<T> O = {0, 0};
  FOR(i, len(P)) {
    if (P[i] == O) origin.eb(i);
    elif ((P[i].y < 0) || (P[i].y == 0 && P[i].x > 0)) lower.eb(i);
    else upper.eb(i);
  }
  sort(all(lower), [&](auto& i, auto& j) { return P[i].det(P[j]) > 0; });
  sort(all(upper), [&](auto& i, auto& j) { return P[i].det(P[j]) > 0; });
  auto& I = lower;
  I.insert(I.end(), all(origin));
  I.insert(I.end(), all(upper));
  return I;
}

// 偏角ソートに対する argsort
template <typename T>
vector<int> angle_argsort(vector<pair<T, T>>& P) {
  vc<Point<T>> tmp(len(P));
  FOR(i, len(P)) tmp[i] = Point<T>(P[i]);
  return angle_argsort<T>(tmp);
}

// inplace に偏角ソートする
// index が欲しい場合は angle_argsort
template <typename T>
void angle_sort(vector<Point<T>>& P) {
  auto I = angle_argsort<T>(P);
  P = rearrange(P, I);
}

// inplace に偏角ソートする
// index が欲しい場合は angle_argsort
template <typename T>
void angle_sort(vector<pair<T, T>>& P) {
  auto I = angle_argsort<T>(P);
  P = rearrange(P, I);
}
#line 8 "main.cpp"

using P = Point<ll>;
using mint = modint998;

/*
凸多角形を作る dp。
・正の角まわる移動だけを考える。間の点があれば 2^n かける。
・「2 角形」はあとで処理する
*/

void solve() {
  LL(N);
  VEC(P, dat, N);
  vv(bool, CAN, N, N);
  vv(int, CNT, N, N);

  auto PREV = [&](int i) -> int { return (i == 0 ? N : i) - 1; };
  auto NXT = [&](int i) -> int { return (i == N - 1 ? 0 : i + 1); };

  FOR(a, N) FOR(b, N) {
    if (a == b) continue;
    P A = dat[a], B = dat[b];
    Segment<ll> AB(A, B);
    Line<ll> L = AB.to_Line();

    vc<bool> ON(N);
    FOR(c, N) {
      if (AB.contain(dat[c])) ON[c] = 1;
    }
    CNT[a][b] = SUM<int>(ON) - 2;
    bool ok = 1;

    // 線分との非自明な交差
    FOR(c, N) {
      int d = NXT(c);
      if (ON[c] || ON[d]) continue;
      P C = dat[c], D = dat[d];
      Segment<ll> CD(C, D);
      if (count_cross(AB, CD, 1)) { ok = 0; }
    }
    // ちょうど乗ってる 1 点の前後
    FOR(c, N) {
      if (a == c || b == c) continue;
      if (!ON[c]) continue;
      int x = PREV(c);
      int y = NXT(c);
      if (ON[x] || ON[y]) continue;
      ll xx = L.eval(dat[x]);
      ll yy = L.eval(dat[y]);
      if (xx > 0 && yy < 0) ok = 0;
      if (xx < 0 && yy > 0) ok = 0;
    }
    // 乗ってる 2 点の前後
    FOR(c, N) {
      int d = NXT(c);
      if (a == c || b == c || a == d || b == d) continue;
      if (!ON[c] || !ON[d]) continue;
      int x = (c == 0 ? N : c) - 1;
      int y = (d + 1 == N ? 0 : d + 1);
      ll xx = L.eval(dat[x]);
      ll yy = L.eval(dat[y]);
      if (xx > 0 && yy < 0) ok = 0;
      if (xx < 0 && yy > 0) ok = 0;
    }
    if (!ok) continue;
    // 交わっていないことまでチェックした。
    // 外側を進んでいないかどうかを確認しないといけない
    // A の近傍だけ見ればよい
    int c = a, d = a;
    while (c != b && ON[c]) c = PREV(c);
    while (d != b && ON[d]) d = NXT(d);
    if (c == b || d == b) {
      // ok
    } else {
      P A = dat[a], B = dat[b];
      P C = dat[c], D = dat[d];
      bool left = (A - C).det(D - A) > 0;
      if (left) {
        ok &= (A - C).det(B - A) >= 0 && (D - A).det(B - A) >= 0;
      } else {
        ok &= (A - C).det(B - A) >= 0 || (D - A).det(B - A) >= 0;
      }
    }
    CAN[a][b] = ok;
  }

  /*
  FOR(a, N) print(CAN[a]);
  print();

  FOR(a, N) print(CNT[a]);
  print();
  flush();
  */

  FOR(a, N) FOR(b, N) assert(CAN[a][b] == CAN[b][a]);
  FOR(a, N) FOR(b, N) assert(CNT[a][b] == CNT[b][a]);

  mint ANS = 0;
  vc<mint> POW = powertable_1<mint>(2, N);
  // 凸包が線分
  FOR(a, N) FOR(b, a) {
    if (CAN[a][b]) ANS += POW[CNT[a][b]];
  }

  // angle sort
  vc<pi> edge;
  vc<P> dir;
  FOR(a, N) FOR(b, N) {
    if (CAN[a][b]) {
      edge.eb(a, b);
      dir.eb(dat[b] - dat[a]);
    }
  }
  auto I = angle_argsort(dir);
  edge = rearrange(edge, I);
  dir = rearrange(dir, I);

  FOR(s, N) {
    // s スタート
    // [0][v]:1 回だけ進んだ
    // [1][v]:2 回以上進んだ
    vv(mint, dp, 2, N);
    // 同じ向きの線分での遷移をまとめて更新するようにする
    auto SAME = [&](int i, int j) -> bool {
      return (dir[i].det(dir[j]) == 0 && dir[i].dot(dir[j]) > 0);
    };
    int L = 0;
    while (L < len(edge)) {
      int R = L;
      while (R < len(edge) && SAME(L, R)) ++R;
      vc<tuple<int, int, mint>> upd;
      FOR(e, L, R) {
        auto [frm, to] = edge[e];
        mint cf = POW[CNT[frm][to]];
        if (frm == s) {
          upd.eb(0, to, cf);
        } else {
          if (to != s) upd.eb(1, to, dp[0][frm] * cf);
          upd.eb(1, to, dp[1][frm] * cf);
        }
      }
      L = R;
      for (auto&& [a, b, c]: upd) dp[a][b] += c;
    }
    ANS += dp[1][s];
  }
  print(ANS);
}

signed main() {
  solve();
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3336kb

input:

7
0 20
40 0
40 20
70 50
50 70
30 50
0 50

output:

56

result:

ok 1 number(s): "56"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3484kb

input:

3
0 2022
-2022 -2022
2022 0

output:

4

result:

ok 1 number(s): "4"

Test #3:

score: 0
Accepted
time: 2ms
memory: 3336kb

input:

3
4 0
0 3
0 0

output:

4

result:

ok 1 number(s): "4"

Test #4:

score: 0
Accepted
time: 2ms
memory: 3320kb

input:

3
-10 0
10 0
0 18

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: 0
Accepted
time: 2ms
memory: 3548kb

input:

4
0 0
-10 0
-10 -10
0 -10

output:

11

result:

ok 1 number(s): "11"

Test #6:

score: 0
Accepted
time: 2ms
memory: 3516kb

input:

4
-100 0
0 -100
100 0
0 100

output:

11

result:

ok 1 number(s): "11"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3364kb

input:

4
0 0
10 5
20 0
10 10

output:

7

result:

ok 1 number(s): "7"

Test #8:

score: 0
Accepted
time: 5ms
memory: 3368kb

input:

4
0 0
20 0
30 10
10 10

output:

11

result:

ok 1 number(s): "11"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3440kb

input:

4
-100 -10
100 -10
100 10
-100 10

output:

11

result:

ok 1 number(s): "11"

Test #10:

score: 0
Accepted
time: 2ms
memory: 3424kb

input:

4
0 0
100 0
60 30
0 30

output:

11

result:

ok 1 number(s): "11"

Test #11:

score: 0
Accepted
time: 2ms
memory: 3336kb

input:

4
0 0
100 0
60 30
40 30

output:

11

result:

ok 1 number(s): "11"

Test #12:

score: 0
Accepted
time: 2ms
memory: 3552kb

input:

7
0 0
10 10
20 0
30 11
20 22
10 11
0 22

output:

44

result:

ok 1 number(s): "44"

Test #13:

score: 0
Accepted
time: 1ms
memory: 3432kb

input:

10
0 0
10 10
20 0
30 10
40 0
40 21
30 11
20 21
10 11
0 21

output:

93

result:

ok 1 number(s): "93"

Test #14:

score: 0
Accepted
time: 1ms
memory: 3428kb

input:

7
0 0
50 50
80 20
110 50
70 90
40 60
0 100

output:

44

result:

ok 1 number(s): "44"

Test #15:

score: 0
Accepted
time: 2ms
memory: 3496kb

input:

16
0 0
20 0
20 10
40 10
40 20
60 20
60 30
70 30
70 40
50 40
50 30
30 30
30 20
10 20
10 10
0 10

output:

407

result:

ok 1 number(s): "407"

Test #16:

score: 0
Accepted
time: 2ms
memory: 3408kb

input:

12
0 0
400 0
400 500
0 500
0 200
200 200
200 300
100 300
100 400
300 400
300 100
0 100

output:

51

result:

ok 1 number(s): "51"

Test #17:

score: 0
Accepted
time: 2ms
memory: 3444kb

input:

10
0 500
-10 20
-350 350
-20 0
-350 -350
0 -20
350 -350
20 0
350 350
10 20

output:

93

result:

ok 1 number(s): "93"

Test #18:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

16
0 0
10 -5
20 0
30 15
40 0
45 10
40 20
25 30
40 40
30 45
20 40
10 25
0 40
-5 30
0 20
15 10

output:

247

result:

ok 1 number(s): "247"

Test #19:

score: 0
Accepted
time: 2ms
memory: 3452kb

input:

8
100 90
90 100
-90 100
-100 90
-100 -90
-90 -100
90 -100
100 -90

output:

247

result:

ok 1 number(s): "247"

Test #20:

score: 0
Accepted
time: 2ms
memory: 3344kb

input:

8
0 0
10 100
90 100
100 0
100 201
90 101
10 101
0 201

output:

31

result:

ok 1 number(s): "31"

Test #21:

score: 0
Accepted
time: 2ms
memory: 3436kb

input:

8
0 0
100 100
900 100
1000 0
1000 210
900 110
100 110
0 210

output:

31

result:

ok 1 number(s): "31"

Test #22:

score: 0
Accepted
time: 2ms
memory: 3476kb

input:

3
1000000 -1000000
1000000 1000000
-1000000 -1000000

output:

4

result:

ok 1 number(s): "4"

Test #23:

score: 0
Accepted
time: 2ms
memory: 3544kb

input:

4
1000000 -1000000
1000000 1000000
1 0
-1000000 -1000000

output:

7

result:

ok 1 number(s): "7"

Test #24:

score: 0
Accepted
time: 2ms
memory: 3340kb

input:

4
1000000 -1000000
1000000 1000000
0 1
-1000000 -1000000

output:

11

result:

ok 1 number(s): "11"

Test #25:

score: 0
Accepted
time: 571ms
memory: 5540kb

input:

200
-28269 899556
-52917 898443
-82904 896173
-112799 892903
-139901 889060
-167758 884227
-196328 878325
-220331 872613
-248497 865014
-277258 856229
-302321 847703
-331311 836799
-354953 827048
-381571 815109
-407788 802314
-431209 789973
-455810 776039
-479961 761338
-503639 745887
-529006 728115...

output:

982924531

result:

ok 1 number(s): "982924531"

Test #26:

score: 0
Accepted
time: 561ms
memory: 5424kb

input:

200
-28269 899556
-52917 898443
-82904 896173
-112799 892903
-139901 889060
-167758 884227
-196328 878325
-220331 872613
-248497 865014
-277258 856229
-302321 847703
-331311 836799
-354953 827048
-381571 815109
-407788 802314
-431209 789973
-455810 776039
-479961 761338
-503639 745887
-529006 728115...

output:

491462169

result:

ok 1 number(s): "491462169"

Test #27:

score: 0
Accepted
time: 144ms
memory: 4048kb

input:

200
-1000000 0
-984589 0
-959090 -1000000
-939997 0
-920698 -1000000
-903689 0
-878269 -1000000
-856526 0
-835872 -1000000
-824921 0
-802874 -1000000
-775273 0
-762503 -1000000
-736648 0
-723628 -1000000
-700062 0
-677324 -1000000
-655520 0
-638093 -1000000
-616069 0
-596730 -1000000
-578522 0
-5610...

output:

766756066

result:

ok 1 number(s): "766756066"

Test #28:

score: 0
Accepted
time: 167ms
memory: 4364kb

input:

200
-982632 0
-969103 -1000000
-940842 0
-921682 0
-906001 -1000000
-879789 0
-865042 0
-845192 -1000000
-816404 0
-802606 0
-787373 -1000000
-753645 0
-737956 0
-725228 -1000000
-692298 0
-681026 0
-651636 -1000000
-636348 0
-619790 0
-587407 -1000000
-573321 0
-558772 0
-527808 -1000000
-513494 0
...

output:

399992829

result:

ok 1 number(s): "399992829"

Test #29:

score: 0
Accepted
time: 2ms
memory: 3336kb

input:

7
30 0
30 20
60 40
90 40
90 60
20 50
0 0

output:

40

result:

ok 1 number(s): "40"

Test #30:

score: 0
Accepted
time: 2ms
memory: 3428kb

input:

9
30 0
30 20
20 30
50 50
60 40
90 40
90 60
20 50
0 0

output:

30

result:

ok 1 number(s): "30"

Test #31:

score: 0
Accepted
time: 0ms
memory: 3340kb

input:

10
0 0
400 0
400 200
300 200
300 100
100 100
100 300
400 300
400 400
0 400

output:

41

result:

ok 1 number(s): "41"

Test #32:

score: 0
Accepted
time: 2ms
memory: 3500kb

input:

10
0 -400
400 -400
400 -300
100 -300
100 -100
300 -100
300 -200
400 -200
400 0
0 0

output:

41

result:

ok 1 number(s): "41"

Test #33:

score: 0
Accepted
time: 2ms
memory: 3448kb

input:

20
-2 11
-6 3
-4 2
-1 8
9 3
3 -9
-5 -5
-4 -3
2 -6
6 2
0 5
-2 1
0 0
1 2
3 1
1 -3
-5 0
-8 -6
4 -12
12 4

output:

91

result:

ok 1 number(s): "91"

Test #34:

score: 0
Accepted
time: 152ms
memory: 3700kb

input:

200
-153811 101954
-110538 -13951
-21156 16822
20793 -224637
-105318 -28386
-184845 -25122
-55966 -252174
-65073 -240349
-402588 -55614
-319429 351875
-479382 92012
-213699 555429
112299 348899
687998 510477
379335 468944
157461 420548
102219 458523
148907 488400
610913 530181
430304 566961
821268 5...

output:

1687

result:

ok 1 number(s): "1687"

Test #35:

score: 0
Accepted
time: 156ms
memory: 3720kb

input:

200
122301 113556
338694 233402
368238 131577
446030 331311
535103 535679
781548 843294
666909 875595
442356 427784
374568 306449
-26086 6336
356963 370926
75420 132096
109676 185484
392958 553349
511233 697425
-105084 -25122
16287 361251
338613 501111
251648 493356
589628 908975
16500 972309
535022...

output:

1663

result:

ok 1 number(s): "1663"

Test #36:

score: 0
Accepted
time: 152ms
memory: 3536kb

input:

200
421640 547713
650121 928769
547442 928833
346206 886544
-452730 992357
102138 855965
111368 905793
366936 808814
97664 687998
306486 711903
22692 663762
-57963 885504
-55792 734234
-463485 989088
-157192 737144
-241500 603149
-444462 699033
-203932 580725
37067 568415
339672 708146
497484 744522...

output:

1599

result:

ok 1 number(s): "1599"

Test #37:

score: 0
Accepted
time: 144ms
memory: 3692kb

input:

200
207543 18138
233654 136908
700845 -843115
765038 -961705
480771 -367522
784833 -913671
931941 -853932
718884 -558630
197457 373259
426012 6606
359594 164931
795933 -587514
362999 173610
635496 -231358
517028 -17575
653370 -224637
779784 -468309
814878 -651810
970226 -830284
897312 -690219
653588...

output:

1403

result:

ok 1 number(s): "1403"

Test #38:

score: 0
Accepted
time: 150ms
memory: 3752kb

input:

200
384246 119904
515880 90069
537210 144074
706626 62156
434349 603996
378143 465476
443127 317247
164931 198306
533444 341568
239054 104826
37271 27579
161283 99692
-13462 22109
497481 748134
753303 786567
441458 667358
736625 725172
466416 609863
638721 590361
679778 436017
624801 526664
704712 1...

output:

1703

result:

ok 1 number(s): "1703"

Test #39:

score: 0
Accepted
time: 143ms
memory: 3640kb

input:

200
290300 170277
240567 128495
339132 87891
177572 360968
480771 164259
512115 17961
405629 5648
333267 87849
346164 -61209
737469 -277905
699884 -331989
552159 -233661
67764 13977
51210 -31561
624573 -303696
365547 -415143
596037 -320155
382416 -471408
455414 -430867
473946 -409309
653883 -416259
...

output:

1723

result:

ok 1 number(s): "1723"

Test #40:

score: 0
Accepted
time: 155ms
memory: 3728kb

input:

200
-55665 353610
-95883 490124
132390 -66873
58841 248211
516981 -547989
507597 -169864
509958 -216196
522693 -268425
681047 -280795
494694 -143556
266337 -45390
313914 -52921
223239 1950
194649 346206
384276 367670
369288 321381
762722 -204108
497747 152082
716706 205593
526883 280884
795998 34640...

output:

1959

result:

ok 1 number(s): "1959"

Test #41:

score: 0
Accepted
time: 150ms
memory: 3760kb

input:

200
283343 271859
383730 322703
365793 322247
450695 405629
434937 311613
486618 479943
358449 -12483
67130 -122775
416790 227442
-16551 -180451
295266 -315165
383364 28503
502124 440735
527090 528342
456162 243552
444408 -165328
648036 -459271
561377 -12972
539900 87975
597287 63161
566952 304059
7...

output:

1703

result:

ok 1 number(s): "1703"

Test #42:

score: 0
Accepted
time: 159ms
memory: 3736kb

input:

200
5009 71481
-20981 20885
-12 -30222
-99838 189696
103887 126708
351540 380079
242496 299244
527678 785484
336098 539408
101865 137745
64338 267396
147075 359897
524 197672
520671 794027
-45390 774477
408812 806877
32813 864956
-594379 939110
-400881 862851
-841240 825276
-623754 795456
-233265 84...

output:

1579

result:

ok 1 number(s): "1579"

Test #43:

score: 0
Accepted
time: 154ms
memory: 3652kb

input:

200
635384 485892
765764 574319
336258 334347
465048 520794
519375 558921
682283 607704
982737 801953
564318 664179
209807 405618
419262 582690
-7986 577806
-441678 673641
171933 603149
261948 582564
129839 653445
374771 807498
499641 893376
916239 999597
-190753 742980
162081 984042
-325008 701442
...

output:

1731

result:

ok 1 number(s): "1731"

Test #44:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

6
0 0
110828 157796
232685 157796
232685 331295
214662 305634
0 305634

output:

29

result:

ok 1 number(s): "29"

Test #45:

score: 0
Accepted
time: 2ms
memory: 3488kb

input:

10
0 0
110828 157796
233685 157796
233685 341295
232685 341295
232685 331295
214662 305634
-1000 305634
-1000 -10000
0 -10000

output:

49

result:

ok 1 number(s): "49"

Test #46:

score: 0
Accepted
time: 2ms
memory: 3548kb

input:

6
0 220492
-741872 220492
-750260 222985
-750260 205257
-690612 205257
0 0

output:

29

result:

ok 1 number(s): "29"

Test #47:

score: 0
Accepted
time: 2ms
memory: 3336kb

input:

10
0 -3000
10000 -3000
10000 220492
-741872 220492
-750260 222985
-750260 225985
-760260 225985
-760260 205257
-690612 205257
0 0

output:

49

result:

ok 1 number(s): "49"

Test #48:

score: 0
Accepted
time: 2ms
memory: 3484kb

input:

6
-999999 -1000000
1000000 999999
-999999 999999
-999999 -999999
-1000000 -999999
-1000000 -1000000

output:

25

result:

ok 1 number(s): "25"

Test #49:

score: 0
Accepted
time: 2ms
memory: 3528kb

input:

6
-999999 -1000000
-999999 -999999
1000000 -999999
1000000 999999
999998 999999
-1000000 -1000000

output:

17

result:

ok 1 number(s): "17"

Test #50:

score: 0
Accepted
time: 2ms
memory: 3552kb

input:

6
-999999 -1000000
-999998 -999999
1000000 -999999
1000000 999999
999998 999999
-1000000 -1000000

output:

33

result:

ok 1 number(s): "33"

Test #51:

score: 0
Accepted
time: 145ms
memory: 3900kb

input:

200
1000000 -999941
-999956 -999940
-998042 -997864
-998053 -997864
-994830 -994360
-994841 -994360
-990958 -990136
-990969 -990136
-983566 -982072
-983577 -982072
-978319 -976348
-978330 -976348
-976768 -974656
-976779 -974656
-975228 -972976
-975239 -972976
-973116 -970672
-973127 -970672
-972808 ...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #52:

score: 0
Accepted
time: 144ms
memory: 4004kb

input:

200
1000000 -998489
-999630 -998488
-992008 -959932
-992082 -959932
-989862 -948970
-989936 -948970
-989344 -946324
-989418 -946324
-978688 -891892
-978762 -891892
-967292 -833680
-967366 -833680
-966182 -828010
-966256 -828010
-965146 -822718
-965220 -822718
-964850 -821206
-964924 -821206
-964480 ...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #53:

score: 0
Accepted
time: 144ms
memory: 3848kb

input:

200
-1000000 999787
998030 999786
958630 978600
959024 978600
946810 972180
947204 972180
940112 968542
940506 968542
837278 912688
837672 912688
817972 902202
818366 902202
814426 900276
814820 900276
809698 897708
810092 897708
798272 891502
798666 891502
788028 885938
788422 885938
785270 884440
...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #54:

score: 0
Accepted
time: 147ms
memory: 3916kb

input:

200
-1000000 997586
999374 997585
897023 840127
897336 840127
789977 674941
790290 674941
783091 664315
783404 664315
759616 628090
759929 628090
708597 549361
708910 549361
704215 542599
704528 542599
702963 540667
703276 540667
700459 536803
700772 536803
699520 535354
699833 535354
624400 419434
...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #55:

score: 0
Accepted
time: 137ms
memory: 3908kb

input:

200
1000000 -999485
975920 -982198
965600 -974200
965256 -974200
964224 -973168
963880 -973168
962504 -971878
962160 -971878
961816 -971362
961472 -971362
961128 -970846
960784 -970846
948744 -961558
948400 -961558
931200 -948400
930856 -948400
906088 -929566
905744 -929566
881320 -910990
880976 -91...

output:

441250454

result:

ok 1 number(s): "441250454"

Test #56:

score: 0
Accepted
time: 143ms
memory: 4000kb

input:

200
1000000 -999175
975085 -976872
963760 -966134
963307 -966134
918460 -924834
918007 -924834
714157 -738571
713704 -738571
638959 -670013
638506 -670013
460477 -507291
460024 -507291
360364 -416018
359911 -416018
359458 -415192
359005 -415192
355381 -411475
354928 -411475
341338 -398672
340885 -39...

output:

441250454

result:

ok 1 number(s): "441250454"

Test #57:

score: 0
Accepted
time: 141ms
memory: 3992kb

input:

200
-1000000 998441
-996730 995710
-994441 992590
-994114 992590
-985285 981670
-984958 981670
-971878 965680
-971551 965680
-967627 960610
-967300 960610
-947026 936040
-946699 936040
-925771 910690
-925444 910690
-797587 757810
-797260 757810
-791374 750400
-791047 750400
-712240 656020
-711913 65...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #58:

score: 0
Accepted
time: 145ms
memory: 3996kb

input:

200
-1000000 998176
-999748 997810
-999496 996350
-999412 996350
-999160 994890
-999076 994890
-982360 921890
-982276 921890
-981352 917510
-981268 917510
-975136 890500
-975052 890500
-850144 347380
-850060 347380
-817216 204300
-817132 204300
-800920 133490
-800836 133490
-787816 76550
-787732 765...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #59:

score: 0
Accepted
time: 146ms
memory: 3960kb

input:

200
100000 -999633
239 -999632
3094 -999448
239 -999448
7467 -999264
239 -999264
4608 -998896
239 -998896
649 -998712
239 -998712
2980 -998528
239 -998528
1563 -998344
239 -998344
7731 -989788
239 -989788
744 -927504
239 -927504
2244 -838724
239 -838724
8203 -807628
239 -807628
4217 -780304
239 -780...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #60:

score: 0
Accepted
time: 2ms
memory: 3564kb

input:

4
-899998 -900000
0 0
450000 450001
449998 449999

output:

7

result:

ok 1 number(s): "7"

Test #61:

score: 0
Accepted
time: 2ms
memory: 3384kb

input:

4
-1000000 -1000000
0 -1
999999 999997
-1 0

output:

7

result:

ok 1 number(s): "7"

Test #62:

score: 0
Accepted
time: 2ms
memory: 3428kb

input:

5
1000000 -1000000
1000000 999999
999999 0
999999 999998
-1000000 -1000000

output:

10

result:

ok 1 number(s): "10"

Test #63:

score: 0
Accepted
time: 2ms
memory: 3508kb

input:

10
-800000 -799999
199991 199997
799987 799996
999985 999995
599988 599996
199990 199996
-200006 -200002
-600003 -600001
-800001 -800000
-1000000 -1000000

output:

73

result:

ok 1 number(s): "73"

Test #64:

score: 0
Accepted
time: 154ms
memory: 3672kb

input:

200
-677343 996088
-731021 806109
-703638 644867
-694433 455591
-698504 132249
-745640 -209598
-859170 -239875
-874703 -116547
-922684 -350844
-920583 296332
-867486 433468
-860134 490879
-849686 -2551
-813758 684881
-777869 965896
-905744 958941
-983905 544305
-996951 494366
-982454 -386675
-977004...

output:

5283

result:

ok 1 number(s): "5283"

Test #65:

score: -100
Dangerous Syscalls

input:

191
2 3
2 2
1 2
0 1
3 2
5 4
5 3
4 2
6 2
8 4
9 4
9 5
8 5
7 4
7 6
6 5
6 3
5 5
4 4
3 4
5 6
6 6
6 7
8 9
7 9
3 5
2 5
4 7
2 6
1 6
1 7
2 7
2 8
1 10
2 9
1 11
3 9
4 10
3 10
2 11
3 11
3 12
1 12
1 13
3 13
1 14
1 15
2 14
3 15
4 15
3 14
4 13
6 13
4 14
5 14
7 13
6 14
8 13
8 12
4 12
4 11
9 11
7 10
5 10
3 8
3 7
5 9...

output:


result: