QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#117862#6673. Be Careful 2maspyAC ✓7744ms4144kbC++2329.5kb2023-07-02 11:46:302023-07-02 11:46:33

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-02 11:46:33]
  • 评测
  • 测评结果:AC
  • 用时:7744ms
  • 内存:4144kb
  • [2023-07-02 11:46:30]
  • 提交

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 u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;

template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'000'000'000;
template <>
constexpr ll infty<ll> = ll(infty<int>) * infty<int> * 2;
template <>
constexpr u32 infty<u32> = infty<int>;
template <>
constexpr u64 infty<u64> = infty<ll>;
template <>
constexpr i128 infty<i128> = i128(infty<ll>) * infty<ll>;
template <>
constexpr double infty<double> = infty<ll>;
template <>
constexpr long double infty<long double> = infty<ll>;

using pi = pair<ll, ll>;
using vi = vector<ll>;
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, bool check_ok = true) {
  if (check_ok) 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 3 "main.cpp"

#line 2 "library/mod/modint_common.hpp"

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

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

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 (len(dat) <= n) {
    int k = len(dat);
    int q = (mod + k - 1) / k;
    dat.eb(dat[k * q - mod] * mint(q));
  }
  return dat[n];
}

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

template <typename mint>
mint fact_inv(int n) {
  static vector<mint> dat = {1, 1};
  if (n < 0) return mint(0);
  while (len(dat) <= n) dat.eb(dat[len(dat) - 1] * inv<mint>(len(dat)));
  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 multinomial<mint>(n, k, n - k);
  k = min(k, n - k);
  mint x(1);
  FOR(i, k) x *= mint(n - i);
  return x * fact_inv<mint>(k);
}

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);
}
#line 3 "library/mod/modint.hpp"

template <int mod>
struct modint {
  static_assert(mod < (1 << 30));
  int val;
  constexpr modint(const ll val = 0) noexcept
      : val(val >= 0 ? val % mod : (mod - (-val) % mod) % mod) {}
  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(ll n) const {
    assert(n >= 0);
    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() {
    fastio::scanner.read(val);
    val = (val >= 0 ? val % mod : (mod - (-val) % mod) % mod);
  }
#endif
  static constexpr int get_mod() { return mod; }
  // (n, r), r は 1 の 2^n 乗根
  static constexpr pair<int, int> ntt_info() {
    if (mod == 167772161) return {25, 17};
    if (mod == 469762049) return {26, 30};
    if (mod == 754974721) return {24, 362};
    if (mod == 880803841) return {23, 211};
    if (mod == 998244353) return {23, 31};
    if (mod == 1045430273) return {20, 363};
    if (mod == 1051721729) return {20, 330};
    if (mod == 1053818881) return {20, 2789};
    return {-1, -1};
  }
  static constexpr bool can_ntt() { return ntt_info().fi != -1; }
};

using modint107 = modint<1000000007>;
using modint998 = modint<998244353>;
#line 2 "library/ds/segtree/segtree.hpp"

template <class Monoid>
struct SegTree {
  using MX = Monoid;
  using X = typename MX::value_type;
  using value_type = X;
  vc<X> dat;
  int n, log, size;

  SegTree() {}
  SegTree(int n) { build(n); }
  template <typename F>
  SegTree(int n, F f) {
    build(n, f);
  }
  SegTree(const vc<X>& v) { build(v); }

  void build(int m) {
    build(m, [](int i) -> X { return MX::unit(); });
  }
  void build(const vc<X>& v) {
    build(len(v), [&](int i) -> X { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m, log = 1;
    while ((1 << log) < n) ++log;
    size = 1 << log;
    dat.assign(size << 1, MX::unit());
    FOR(i, n) dat[size + i] = f(i);
    FOR_R(i, 1, size) update(i);
  }

  X get(int i) { return dat[size + i]; }
  vc<X> get_all() { return {dat.begin() + size, dat.begin() + size + n}; }

  void update(int i) { dat[i] = Monoid::op(dat[2 * i], dat[2 * i + 1]); }
  void set(int i, const X& x) {
    assert(i < n);
    dat[i += size] = x;
    while (i >>= 1) update(i);
  }

  void multiply(int i, const X& x) {
    assert(i < n);
    i += size;
    dat[i] = Monoid::op(dat[i], x);
    while (i >>= 1) update(i);
  }

  X prod(int L, int R) {
    assert(0 <= L && L <= R && R <= n);
    X vl = Monoid::unit(), vr = Monoid::unit();
    L += size, R += size;
    while (L < R) {
      if (L & 1) vl = Monoid::op(vl, dat[L++]);
      if (R & 1) vr = Monoid::op(dat[--R], vr);
      L >>= 1, R >>= 1;
    }
    return Monoid::op(vl, vr);
  }

  X prod_all() { return dat[1]; }

  template <class F>
  int max_right(F check, int L) {
    assert(0 <= L && L <= n && check(Monoid::unit()));
    if (L == n) return n;
    L += size;
    X sm = Monoid::unit();
    do {
      while (L % 2 == 0) L >>= 1;
      if (!check(Monoid::op(sm, dat[L]))) {
        while (L < size) {
          L = 2 * L;
          if (check(Monoid::op(sm, dat[L]))) { sm = Monoid::op(sm, dat[L++]); }
        }
        return L - size;
      }
      sm = Monoid::op(sm, dat[L++]);
    } while ((L & -L) != L);
    return n;
  }

  template <class F>
  int min_left(F check, int R) {
    assert(0 <= R && R <= n && check(Monoid::unit()));
    if (R == 0) return 0;
    R += size;
    X sm = Monoid::unit();
    do {
      --R;
      while (R > 1 && (R % 2)) R >>= 1;
      if (!check(Monoid::op(dat[R], sm))) {
        while (R < size) {
          R = 2 * R + 1;
          if (check(Monoid::op(dat[R], sm))) { sm = Monoid::op(dat[R--], sm); }
        }
        return R + 1 - size;
      }
      sm = Monoid::op(dat[R], sm);
    } while ((R & -R) != R);
    return 0;
  }

  // prod_{l<=i<r} A[i xor x]
  X xor_prod(int l, int r, int xor_val) {
    static_assert(Monoid::commute);
    X x = Monoid::unit();
    for (int k = 0; k < log + 1; ++k) {
      if (l >= r) break;
      if (l & 1) { x = Monoid::op(x, dat[(size >> k) + ((l++) ^ xor_val)]); }
      if (r & 1) { x = Monoid::op(x, dat[(size >> k) + ((--r) ^ xor_val)]); }
      l /= 2, r /= 2, xor_val /= 2;
    }
    return x;
  }
};
#line 2 "library/alg/monoid/min.hpp"

template <typename E>
struct Monoid_Min {
  using X = E;
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return min(x, y); }
  static constexpr X unit() { return infty<E>; }
  static constexpr bool commute = true;
};
#line 1 "library/ds/fastset.hpp"
/* 64分木。
insert, erase
[]での存在判定
next, prev
*/
struct FastSet {
  using uint = unsigned;
  using ull = unsigned long long;

  int bsr(ull x) { return 63 - __builtin_clzll(x); }
  int bsf(ull x) { return __builtin_ctzll(x); }

  static constexpr uint B = 64;
  int n, lg;
  vector<vector<ull>> seg;
  FastSet(int _n) : n(_n) {
    do {
      seg.push_back(vector<ull>((_n + B - 1) / B));
      _n = (_n + B - 1) / B;
    } while (_n > 1);
    lg = int(seg.size());
  }
  bool operator[](int i) const { return (seg[0][i / B] >> (i % B) & 1) != 0; }
  void insert(int i) {
    for (int h = 0; h < lg; h++) {
      seg[h][i / B] |= 1ULL << (i % B);
      i /= B;
    }
  }
  void add(int i) { insert(i); }
  void erase(int i) {
    for (int h = 0; h < lg; h++) {
      seg[h][i / B] &= ~(1ULL << (i % B));
      if (seg[h][i / B]) break;
      i /= B;
    }
  }
  void remove(int i) { insert(i); }

  // x以上最小の要素を返す。存在しなければ n。
  int next(int i) {
    chmax(i, 0);
    if (i >= n) return n;
    for (int h = 0; h < lg; h++) {
      if (i / B == seg[h].size()) break;
      ull d = seg[h][i / B] >> (i % B);
      if (!d) {
        i = i / B + 1;
        continue;
      }
      // find
      i += bsf(d);
      for (int g = h - 1; g >= 0; g--) {
        i *= B;
        i += bsf(seg[g][i / B]);
      }
      return i;
    }
    return n;
  }

  // x以下最大の要素を返す。存在しなければ -1。
  int prev(int i) {
    if (i < 0) return -1;
    if (i >= n) i = n - 1;
    for (int h = 0; h < lg; h++) {
      if (i == -1) break;
      ull d = seg[h][i / B] << (63 - i % 64);
      if (!d) {
        i = i / B - 1;
        continue;
      }
      // find
      i += bsr(d) - (B - 1);
      for (int g = h - 1; g >= 0; g--) {
        i *= B;
        i += bsr(seg[g][i / B]);
      }
      return i;
    }
    return -1;
  }

  // [l, r)
  template <typename F>
  void enumerate(int l, int r, F f) {
    int x = l - 1;
    while (1) {
      x = next(x + 1);
      if (x >= r) break;
      f(x);
    }
  }

  void debug() {
    string s;
    for (int i = 0; i < n; ++i) s += ((*this)[i] ? '1' : '0');
    print(s);
  }
};
#line 2 "library/mod/mod_inv.hpp"
// long でも大丈夫
ll mod_inv(ll val, ll mod) {
  val %= mod;
  if (val < 0) val += mod;
  ll 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);
  }
  if (u < 0) u += mod;
  return u;
}
#line 9 "main.cpp"

using mint = modint998;

using ARR = array<mint, 4>;

ARR F4(ll n) {
  if (n < 0) return {mint(0), mint(0), mint(0), mint(0)};
  ARR res;
  mint n1 = n;
  mint n2 = n1 * n1;
  mint n3 = n1 * n2;
  mint n4 = n1 * n3;
  mint n5 = n1 * n4;
  res[0] = (n1 + n2) * mint(30);
  res[1] = (-n1 + n3) * mint(10);
  res[2] = (-n2 + n4) * mint(5);
  res[3] = (n1 + n1 - mint(5) * n3 + n5 + n5 + n5);
  return res;
}

ll call_zero = 0;
ll call_F = 0;

mint F2(ll a, ll b, ll c1, ll c2, mint p) {
  c1 += a - 1;
  c2 += a - 1;
  chmax(c1, 0);
  chmin(c2, a + b - 1);
  if (c1 >= c2) return mint(0);

  mint ANS = 0;

  ARR A = F4(c2);
  {
    ARR P = F4(c1);
    ARR Q = F4(c2 - a);
    ARR R = F4(c1 - a);
    FOR(i, 4) A[i] = A[i] - P[i] - Q[i] + R[i];
  }
  mint b1 = b;
  mint b2 = b1 * b1;
  mint b3 = b1 * b2;
  {
    ARR B = F4(c2 - b);
    ARR P = F4(c2 - b - a);
    ARR Q = F4(c1 - b);
    ARR R = F4(c1 - b - a);
    FOR(i, 4) B[i] = B[i] - P[i] - Q[i] + R[i];
    A[0] -= B[0];
    A[1] -= B[1] + b1 * B[0];
    A[2] -= B[2] + (b1 + b1) * B[1] + b2 * B[0];
    A[3] -= B[3] + (b1 + b1 + b1) * B[2] + (b2 + b2 + b2) * B[1] + b3 * B[0];
  }
  mint pp = p * p + p;
  mint pp1 = p + p + mint(1);
  ANS -= A[3] + A[3];
  ANS += (pp1 + pp1 + pp1) * A[2];
  ANS -= (mint(6) * pp + mint(1)) * A[1];
  ANS += pp * pp1 * A[0];
  return ANS;
}

mint F(ll a1, ll a2, ll b1, ll b2, ll c1, ll c2, ll p, ll q) {
  // ++call_F;
  ll a = a2 - a1;
  ll b = b2 - b1;
  c1 = c1 - b1 + a1;
  c2 = c2 + a1 - b1;
  p -= a1;
  q -= b1;
  if (c1 >= c2) return 0;

  mint ANS = 0;
  int th = q - p;
  chmax(th, c1);
  chmin(th, c2);
  if (c1 < th) ANS += F2(b, a, -th + 1, -c1 + 1, p);
  if (th < c2) ANS += F2(a, b, th, c2, q);
  return ANS;
}

mint solve_x_region(ll x_max, ll y_max, vc<pi>& XY, ll x1, ll x2) {
  // タイプ 1 の条件 (a,b)
  // y-x < a ならば f(x,y) <= b-y
  // タイプ 2 の条件 (a,b,c)
  // a <= y-x かつ y < b ならば f(x,y) <= c-x
  vc<pair<int, int>> cond_1;
  vc<tuple<int, int, int>> cond_2;
  cond_2.eb(-infty<int>, y_max, x_max);

  for (auto&& [a, b]: XY) {
    if (a < x2) continue;
    cond_1.eb(b - a, b);
    cond_2.eb(b - a, b, a);
  }
  cond_1.eb(infty<int>, y_max);

  sort(all(cond_1));
  FOR_R(k, len(cond_1) - 1) { chmin(cond_1[k].se, cond_1[k + 1].se); }

  sort(all(cond_2));

  // 境界となる y-x の値を集める
  vi A;
  for (auto&& [a, b]: cond_1) A.eb(a);
  for (auto&& [a, b, c]: cond_2) A.eb(a);
  UNIQUE(A);

  // タイプ 2 の条件 (a,b,c)
  // a <= y-x かつ y < b ならば f(x,y) <= c-x
  // y-x を increment していくと、条件が増えていく
  vc<int> Y;
  for (auto&& [a, b, c]: cond_2) Y.eb(b);
  UNIQUE(Y);
  for (auto&& [a, b, c]: cond_2) b = LB(Y, b);
  ll NY = len(Y);
  FastSet ss(NY);
  SegTree<Monoid_Min<int>> seg(NY);

  int p = 0;
  int q = 0;
  mint ANS = 0;
  FOR(k, len(A) - 1) {
    ll c1 = A[k], c2 = A[k + 1];
    while (cond_1[p].fi < c2) ++p;
    ll b = cond_1[p].se;
    // タイプ 2 の条件を追加
    while (q < len(cond_2)) {
      auto [a, b, c] = cond_2[q];
      if (a <= c1) {
        ss.insert(b);
        seg.multiply(b, c);
        ++q;
      } else {
        break;
      }
    }

    ll y1 = x1 + c1, y2 = x2 + c2;
    y1 = LB(Y, y1), y2 = LB(Y, y2);
    ll c = seg.prod(y2, NY);

    vc<pair<int, int>> cond;
    {
      int idx = y1;
      while (1) {
        idx = ss.next(idx);
        if (idx >= y2) break;
        cond.eb(Y[idx], seg.get(idx));
        ++idx;
      }
    }

    cond.insert(cond.begin(), {0, -infty<int>});
    if (cond.back().fi != y_max) cond.eb(y_max, c);
    chmin(cond.back().se, c);
    FOR_R(k, len(cond) - 1) { chmin(cond[k].se, cond[k + 1].se); }

    vc<tuple<int, int, int>> tmp;
    FOR(k, len(cond) - 1) {
      ll y1 = cond[k].fi;
      ll y2 = cond[k + 1].fi;
      ll cc = min<int>(c, cond[k + 1].se);
      if (len(tmp) && (get<2>(tmp.back())) == cc) {
        get<1>(tmp.back()) = y2;
        continue;
      }
      tmp.eb(y1, y2, cc);
    }
    for (auto&& [y1, y2, cc]: tmp) { ANS += F(x1, x2, y1, y2, c1, c2, cc, b); }

    /*
    FOR(k, len(cond) - 1) {
      ll y1 = cond[k].fi;
      ll y2 = cond[k + 1].fi;
      ll cc = min(c, cond[k + 1].se);
      ANS += F(x1, x2, y1, y2, c1, c2, cc, b);
    }
    */
  }

  return ANS;
}

void solve() {
  LL(x_max, y_max, K);
  VEC(pi, XY, K);

  // sort(all(XY),
  //      [&](auto& a, auto& b) -> bool { return a.se - a.fi < b.se - b.fi; });

  vi X;
  X = {0, x_max};
  for (auto&& [x, y]: XY) { X.eb(x); }
  UNIQUE(X);

  mint ANS = 0;
  FOR(k, len(X) - 1) ANS += solve_x_region(x_max, y_max, XY, X[k], X[k + 1]);
  ANS *= inv<mint>(360);
  print(ANS);
  // print(call_F);
  // print(call_zero);
}

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

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3592kb

input:

3 3 1
2 2

output:

21

result:

ok 1 number(s): "21"

Test #2:

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

input:

5 5 2
2 1
2 4

output:

126

result:

ok 1 number(s): "126"

Test #3:

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

input:

6 6 5
4 1
3 2
2 4
1 5
5 3

output:

161

result:

ok 1 number(s): "161"

Test #4:

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

input:

15 38 6
12 6
7 15
2 18
3 19
4 2
14 29

output:

80066

result:

ok 1 number(s): "80066"

Test #5:

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

input:

5145 5419 9
547 285
294 284
375 385
217 857
348 925
14 274
3104 853
184 953
794 603

output:

334363567

result:

ok 1 number(s): "334363567"

Test #6:

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

input:

5 5 16
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4

output:

25

result:

ok 1 number(s): "25"

Test #7:

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

input:

9145 9419 12
123 456
223 456
547 285
294 284
375 385
217 857
348 925
14 274
1104 853
184 953
794 603
2234 5678

output:

921360185

result:

ok 1 number(s): "921360185"

Test #8:

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

input:

6 8 4
2 3
3 3
4 2
1 1

output:

444

result:

ok 1 number(s): "444"

Test #9:

score: 0
Accepted
time: 3307ms
memory: 3816kb

input:

1000000000 1000000000 5000
1657 1
1644 1
1000000 116362
1186 1
2392 1
1560 1
995 1
2340 1
1916 1
2143 1
1762 1
1000000 116109
1651 1
1000000 116059
2289 1
1000000 115730
1000000 115896
1000000 116499
1608 1
342 1
1000000 116949
1965 1
1000000 114571
1000000 116602
2171 1
1000000 114848
1000000 11627...

output:

80025633

result:

ok 1 number(s): "80025633"

Test #10:

score: 0
Accepted
time: 1078ms
memory: 3856kb

input:

1000000000 1000000000 5000
1 2581
1 2273
115983 1000000
116105 1000000
114552 1000000
1 1955
1 2254
116061 1000000
116182 1000000
115783 1000000
114564 1000000
116614 1000000
116229 1000000
116087 1000000
114956 1000000
1 2453
114766 1000000
115750 1000000
115448 1000000
1 1748
116665 1000000
1 2237...

output:

80025633

result:

ok 1 number(s): "80025633"

Test #11:

score: 0
Accepted
time: 2455ms
memory: 3856kb

input:

1000000000 1000000000 5000
824 1
811 1
2300000 114696
353 1
1559 1
727 1
162 1
1507 1
1083 1
1310 1
929 1
1000000 116109
818 1
1000000 116059
1456 1
1000000 115730
1000000 115896
2300000 114833
775 1
2300000 115576
2300000 115283
1132 1
1000000 114571
2300000 114936
1338 1
1000000 114848
2300000 114...

output:

537083161

result:

ok 1 number(s): "537083161"

Test #12:

score: 0
Accepted
time: 979ms
memory: 3976kb

input:

1000000000 1000000000 5000
1 1748
1 1440
115983 1000000
116105 1000000
114552 1000000
1 1122
1 1421
116061 1000000
114516 2300000
115783 1000000
114564 1000000
114948 2300000
114563 2300000
116087 1000000
114956 1000000
1 1620
114766 1000000
115750 1000000
115448 1000000
1 915
114999 2300000
1 1404
...

output:

537083161

result:

ok 1 number(s): "537083161"

Test #13:

score: 0
Accepted
time: 40ms
memory: 3852kb

input:

1000000000 1000000000 5000
2300000 115622
1000000 116216
1000000 116852
2300000 115827
2300000 116715
1000000 116212
2300000 116390
2300000 114646
1000000 114857
2300000 116404
1000000 116398
1000000 115409
2300000 115721
1000000 116136
2300000 114925
2300000 114869
2300000 116176
1000000 115774
100...

output:

129612365

result:

ok 1 number(s): "129612365"

Test #14:

score: 0
Accepted
time: 2242ms
memory: 3860kb

input:

1000000000 1000000000 5000
116495 1000000
116269 1000000
115204 2300000
115724 1000000
116508 1000000
115095 2300000
116712 1000000
114789 2300000
115009 2300000
114795 1000000
115093 2300000
115612 1000000
116183 2300000
116140 2300000
116148 2300000
115608 2300000
115111 1000000
115058 1000000
115...

output:

129612365

result:

ok 1 number(s): "129612365"

Test #15:

score: 0
Accepted
time: 83ms
memory: 3792kb

input:

999999992 999999990 5000
1035170 5702575
3959104 3959104
3887901 7432303
11377527 9794948
6282049 47695
11781994 2037659
11292228 47695
6787467 878630
10441683 5492431
1240650 1129736
5631557 11377527
4863442 5631557
6662382 4863442
8837935 7070049
8837935 10441683
4878561 5702575
5610718 2664505
58...

output:

892807048

result:

ok 1 number(s): "892807048"

Test #16:

score: 0
Accepted
time: 7744ms
memory: 4116kb

input:

999999948 999999898 5000
6033860 10854965
57219333 28077882
18498300 33290576
34559919 16960059
40765867 73389700
9985342 17984966
54717579 26853732
13059544 23513592
56562634 27758141
19776481 35613289
6632028 11929378
14942564 7329745
7337824 13208993
33584464 60460021
13330979 6539654
32561958 58...

output:

461431823

result:

ok 1 number(s): "461431823"

Test #17:

score: 0
Accepted
time: 7278ms
memory: 4144kb

input:

999999524 999999758 5000
28630401 15905366
49821653 27672863
52823763 29343863
14406464 29362320
3914600 2178863
15379626 31340404
2382937 4856861
26445243 14692595
15255307 8475517
23233725 12911959
8922530 4954657
80413834 44658470
59845170 33233185
38234833 21236207
48814787 27111180
7919671 4397...

output:

811760775

result:

ok 1 number(s): "811760775"

Test #18:

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

input:

999999991 999999996 5000
191981012 91509738
114514 75994027
113271868 114514
191981012 74412508
73311176 114514
55237456 114514
157017806 114514
114514 38589289
114514 48208495
50968309 114514
151891598 191981012
34509833 191981012
112566922 191981012
54162112 191981012
99866720 114514
191981012 404...

output:

477858401

result:

ok 1 number(s): "477858401"

Test #19:

score: 0
Accepted
time: 2555ms
memory: 3860kb

input:

999999997 999999992 5000
157493349 191981012
191981012 739725
191981012 103830381
191981012 56086190
163612413 114514
191981012 56630806
191981012 56513816
170698088 114514
97262819 114514
130313445 191981012
114514 113985965
114514 112636345
114514 76391763
114514 36458624
114514 35952358
114514 33...

output:

109114433

result:

ok 1 number(s): "109114433"

Test #20:

score: 0
Accepted
time: 2528ms
memory: 3792kb

input:

999999999 999999992 5000
114514 21049898
101232053 191981012
114514 14704290
114514 85418326
191981012 17641251
90959749 191981012
114514 48586425
114514 85286676
114514 85318864
180324603 191981012
73453197 114514
191981012 96571986
191981012 42295145
114514 113760745
166197584 191981012
129916604 ...

output:

239360106

result:

ok 1 number(s): "239360106"

Test #21:

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

input:

100 100 40
13 77
15 17
74 83
25 51
49 65
60 19
83 86
71 87
47 2
7 31
34 65
84 32
58 69
89 92
67 61
49 79
92 74
76 87
96 37
45 21
56 84
53 72
16 30
59 41
55 9
31 72
86 53
95 53
80 87
51 99
55 83
13 93
3 90
61 83
65 27
66 57
52 34
3 46
6 30
92 80

output:

12252760

result:

ok 1 number(s): "12252760"

Test #22:

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

input:

100 100 100
91 50
58 1
93 95
58 77
32 60
36 77
18 3
67 33
25 6
23 77
69 2
24 77
96 17
50 99
81 22
22 46
88 54
50 18
74 40
4 38
77 3
2 7
98 37
14 98
68 33
13 23
17 51
40 63
43 58
27 76
77 19
48 73
14 92
27 72
63 33
33 54
98 96
47 2
49 37
36 85
5 43
23 69
5 19
78 98
99 91
48 12
26 51
11 90
93 31
27 26...

output:

4466541

result:

ok 1 number(s): "4466541"

Test #23:

score: 0
Accepted
time: 9ms
memory: 3420kb

input:

100 100 500
87 54
94 64
78 54
80 11
74 87
84 2
72 96
8 8
19 29
3 78
62 38
28 44
60 14
56 81
91 57
64 33
75 35
98 8
26 65
87 81
94 63
86 96
1 4
74 69
90 71
96 33
13 97
97 68
52 61
50 84
27 20
22 31
7 36
15 18
17 41
49 64
13 63
18 5
57 62
38 66
54 65
35 5
62 29
2 30
21 30
83 44
40 22
29 11
83 11
30 69...

output:

550657

result:

ok 1 number(s): "550657"

Test #24:

score: 0
Accepted
time: 17ms
memory: 3580kb

input:

100 100 1500
74 35
31 76
66 71
12 96
74 92
68 67
3 4
86 29
60 40
24 12
50 11
19 20
51 95
3 14
85 64
22 60
79 18
28 48
60 70
20 88
37 23
8 75
92 46
91 13
39 18
91 88
77 47
16 96
34 58
18 44
39 70
33 21
99 99
56 27
70 32
71 32
73 98
33 51
10 35
41 29
5 70
24 44
84 51
53 71
78 33
14 55
7 25
71 1
85 24
...

output:

142410

result:

ok 1 number(s): "142410"

Test #25:

score: 0
Accepted
time: 41ms
memory: 3756kb

input:

100 100 3000
18 46
35 86
98 87
79 87
56 43
87 40
7 74
41 65
81 42
58 82
20 94
85 97
94 68
64 27
67 19
71 58
51 85
19 55
29 17
27 52
54 24
35 22
85 61
88 83
94 59
62 3
32 97
36 29
57 99
79 62
42 23
39 12
61 44
67 21
72 17
52 66
99 40
36 25
80 51
68 3
15 15
59 20
35 75
16 5
86 93
83 6
41 33
99 2
31 98...

output:

63891

result:

ok 1 number(s): "63891"

Test #26:

score: 0
Accepted
time: 64ms
memory: 3828kb

input:

100 100 4999
90 57
24 41
25 59
46 59
16 49
17 15
88 89
56 25
18 8
74 30
68 34
75 37
58 74
72 19
40 23
54 81
3 95
9 75
85 57
8 40
45 30
96 13
63 63
27 51
40 26
56 9
39 12
7 63
66 17
11 37
44 26
79 99
65 34
49 77
70 46
38 48
31 69
44 19
82 80
2 84
30 68
6 94
85 65
97 56
19 34
14 21
26 80
29 58
34 20
5...

output:

34812

result:

ok 1 number(s): "34812"

Test #27:

score: 0
Accepted
time: 60ms
memory: 3768kb

input:

100 100 5000
4 96
13 14
29 98
17 27
5 49
98 22
15 87
23 15
17 67
97 30
49 6
45 98
70 70
90 2
98 5
65 17
63 43
41 26
76 82
30 48
52 4
26 53
73 67
71 92
59 36
33 46
15 14
98 27
55 69
98 52
50 17
69 25
82 95
49 28
87 10
98 36
8 82
16 97
32 18
10 30
47 33
30 88
33 93
92 85
9 3
31 89
27 20
38 76
88 64
58...

output:

34455

result:

ok 1 number(s): "34455"

Test #28:

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

input:

100 2000 40
82 172
10 1709
49 504
80 1874
54 1543
65 1552
68 1116
89 501
62 1279
36 1385
36 1027
78 1662
58 1031
17 545
68 875
93 1837
56 1758
27 1845
46 1007
57 721
35 1153
77 76
18 889
68 27
49 863
15 885
72 264
88 1747
28 1808
26 1265
94 1838
21 1947
71 1220
51 709
80 491
34 1121
29 1878
57 638
4...

output:

476630897

result:

ok 1 number(s): "476630897"

Test #29:

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

input:

100 2000 100
64 1327
7 1857
34 130
52 998
50 122
98 1720
90 15
37 305
66 1956
97 1335
5 1223
98 717
94 182
18 931
58 159
92 1212
47 815
23 59
87 1735
76 133
98 1397
45 17
87 1529
16 1071
87 1722
56 645
17 408
34 1599
96 1684
16 843
35 1245
62 1630
38 539
4 598
92 849
92 1424
68 892
5 1304
66 103
94 ...

output:

874863095

result:

ok 1 number(s): "874863095"

Test #30:

score: 0
Accepted
time: 14ms
memory: 3532kb

input:

100 2000 500
60 1213
50 1837
19 1974
70 1136
92 1979
54 1180
49 211
76 1898
56 536
85 1091
6 118
3 254
66 393
28 1889
72 72
27 1122
35 112
75 616
44 1378
60 69
28 806
37 929
94 735
76 1146
5 707
40 1638
8 1900
90 760
18 135
43 1519
85 775
28 579
36 935
4 1458
46 1499
8 1613
82 540
75 1700
74 210
96 ...

output:

545166322

result:

ok 1 number(s): "545166322"

Test #31:

score: 0
Accepted
time: 35ms
memory: 3744kb

input:

100 2000 1500
49 1888
86 1376
46 856
79 17
45 697
92 1752
52 1378
63 1442
7 882
71 1370
96 702
52 497
93 897
74 249
63 1655
80 90
46 1904
27 371
15 1265
92 214
89 1812
87 719
45 823
15 1708
3 827
99 850
63 1180
6 401
87 124
77 32
2 377
85 627
40 169
14 281
14 1101
12 314
14 447
19 1781
51 626
90 745...

output:

148961647

result:

ok 1 number(s): "148961647"

Test #32:

score: 0
Accepted
time: 72ms
memory: 3800kb

input:

100 2000 3000
93 1277
2 1750
66 1555
38 1627
23 1251
4 332
68 266
18 1078
24 1386
6 1444
70 673
28 806
28 629
31 456
42 1407
26 545
22 1643
27 409
79 1991
95 394
94 1614
15 680
26 399
20 86
66 94
75 306
18 345
30 836
46 1023
11 1655
26 513
77 1336
72 588
86 505
38 274
98 96
34 691
84 627
2 1788
53 1...

output:

56815774

result:

ok 1 number(s): "56815774"

Test #33:

score: 0
Accepted
time: 119ms
memory: 3840kb

input:

100 2000 4999
69 141
90 319
92 570
13 503
74 817
41 1656
33 1735
29 1366
52 419
26 1608
15 417
17 1193
91 1056
31 1797
18 544
5 1792
81 1881
12 255
24 1177
75 1534
96 277
84 1562
8 1665
49 91
13 120
72 953
29 539
96 1831
51 1903
50 1843
27 1337
22 1178
73 307
59 1951
28 1431
79 911
66 1530
89 969
5 ...

output:

29031348

result:

ok 1 number(s): "29031348"

Test #34:

score: 0
Accepted
time: 115ms
memory: 3804kb

input:

100 2000 5000
78 1655
79 1968
97 1538
75 1328
75 780
24 1025
64 1775
99 1319
59 877
49 705
95 597
83 921
9 523
49 367
76 553
28 1623
30 1616
52 145
23 296
98 662
5 249
6 1095
18 982
2 793
31 1941
49 1670
9 1596
88 467
40 1178
34 220
34 318
15 1014
98 130
64 465
56 1356
40 257
46 108
60 1406
54 373
9...

output:

28106075

result:

ok 1 number(s): "28106075"

Test #35:

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

input:

100 1000000000 40
91 906492795
44 220406215
46 697653054
57 115159754
41 410299001
2 856461372
11 829769415
19 154206891
87 111013909
2 558231357
53 227124152
8 25775632
77 819248359
66 956427714
23 438568455
40 885638653
93 953383697
97 674250396
91 168010516
71 425324837
84 679265396
92 438925795
...

output:

308636238

result:

ok 1 number(s): "308636238"

Test #36:

score: 0
Accepted
time: 3ms
memory: 3512kb

input:

100 1000000000 100
13 107090664
57 269885036
71 253364299
23 124674877
34 158640158
34 212481096
97 96462559
5 905248661
7 721358783
36 406914955
93 304044767
10 758826649
86 870834795
22 78209124
95 821043354
15 747758089
79 209048751
10 92632533
40 167864124
54 140677453
8 260747605
32 673110337
3...

output:

15721069

result:

ok 1 number(s): "15721069"

Test #37:

score: 0
Accepted
time: 21ms
memory: 3580kb

input:

100 1000000000 500
9 884176880
92 685216500
60 349365908
33 909262376
80 346546370
90 933603462
52 93869530
44 694779448
96 634413542
16 534218862
98 895186467
18 257872364
50 304205239
24 979628465
10 212894893
61 705524564
66 695239491
58 881000335
1 718387750
29 744828497
37 746039846
17 96409865...

output:

732332250

result:

ok 1 number(s): "732332250"

Test #38:

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

input:

100 1000000000 1500
3 874996650
86 465478752
71 678518381
8 721100871
65 36660500
46 628307861
25 249070752
48 926487045
51 101624043
78 8109175
75 39868981
67 361110166
44 222180507
91 738700669
37 490125317
94 462382018
80 201684972
10 80444765
15 309604275
37 731634425
5 810314270
24 229206345
47...

output:

753671314

result:

ok 1 number(s): "753671314"

Test #39:

score: 0
Accepted
time: 122ms
memory: 3776kb

input:

100 1000000000 3000
46 315468771
89 795555094
87 273919299
75 763599031
39 557565439
69 561796240
29 858884876
98 867636821
76 947865397
13 149920455
45 960937190
30 581327774
82 994611919
48 695928933
27 814619938
41 453055204
57 78794097
97 664376126
79 381113636
39 183850392
13 863767314
52 77581...

output:

165068431

result:

ok 1 number(s): "165068431"

Test #40:

score: 0
Accepted
time: 201ms
memory: 3956kb

input:

100 1000000000 4999
23 981436455
78 697469606
14 778058249
45 580983878
98 690859674
94 768219874
7 799618639
14 218210131
9 313076636
33 658739035
97 571652795
20 699689049
43 479246235
49 563485912
99 130776916
32 135723448
17 658033163
90 77170696
28 663286691
28 383151393
4 26990484
21 856223099...

output:

162258766

result:

ok 1 number(s): "162258766"

Test #41:

score: 0
Accepted
time: 199ms
memory: 4020kb

input:

100 1000000000 5000
28 127064660
67 990623740
19 94387764
21 184315217
94 518385844
85 794171229
37 583105000
84 199077103
4 549302796
56 626057952
70 523247708
86 920946496
59 996375805
66 707676893
58 418428414
39 518883170
65 402514408
23 581452060
23 804453957
39 532845441
24 729930201
46 445780...

output:

493451776

result:

ok 1 number(s): "493451776"

Test #42:

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

input:

1000 100 40
815 84
52 18
361 39
621 81
492 73
694 1
88 43
393 97
369 21
758 85
905 68
461 73
392 45
866 32
26 96
816 17
858 49
828 10
976 41
169 91
327 82
669 20
796 50
559 24
314 82
547 14
473 74
715 77
235 76
896 15
548 34
451 80
387 97
223 49
713 17
828 57
758 70
103 64
687 39
560 85

output:

258922145

result:

ok 1 number(s): "258922145"

Test #43:

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

input:

1000 100 100
490 7
149 93
485 65
309 82
31 86
267 56
687 1
711 65
877 66
417 19
871 45
652 43
430 42
777 45
486 45
764 99
690 73
446 68
850 41
470 62
805 93
510 89
32 97
482 84
300 38
60 74
861 8
828 32
790 24
913 38
847 81
229 19
393 39
492 55
379 58
503 57
398 1
700 27
916 21
888 72
28 25
382 3
26...

output:

887311204

result:

ok 1 number(s): "887311204"

Test #44:

score: 0
Accepted
time: 28ms
memory: 3584kb

input:

1000 100 500
834 15
787 54
830 24
187 21
541 10
188 68
772 94
979 37
177 85
369 20
99 85
552 14
115 40
234 22
814 81
72 95
921 53
804 50
74 66
675 5
69 54
279 80
444 68
420 47
885 84
414 72
983 45
628 41
938 28
810 46
630 81
549 75
102 82
412 4
234 66
672 70
394 76
784 21
421 50
943 57
994 35
601 33...

output:

127131287

result:

ok 1 number(s): "127131287"

Test #45:

score: 0
Accepted
time: 170ms
memory: 3704kb

input:

1000 100 1500
603 80
292 38
376 94
475 36
688 75
225 80
775 94
369 70
191 9
73 82
242 78
707 8
914 67
600 54
651 80
482 12
616 95
320 62
775 40
75 63
141 93
33 14
943 88
432 88
136 8
766 13
638 19
840 4
644 22
169 65
919 74
836 19
295 75
247 72
627 25
213 17
840 38
144 99
584 43
618 8
557 4
129 50
8...

output:

27193936

result:

ok 1 number(s): "27193936"

Test #46:

score: 0
Accepted
time: 424ms
memory: 3780kb

input:

1000 100 3000
350 91
134 52
423 12
820 31
185 26
915 54
985 53
509 98
49 22
566 53
522 70
588 85
547 48
372 62
795 47
753 2
467 63
964 66
149 94
415 26
709 90
581 51
614 11
35 63
423 57
705 27
279 69
319 36
576 13
962 76
728 53
854 73
282 98
541 89
858 15
376 55
972 62
435 26
405 43
82 74
98 89
453 ...

output:

11057434

result:

ok 1 number(s): "11057434"

Test #47:

score: 0
Accepted
time: 730ms
memory: 3840kb

input:

1000 100 4999
641 94
258 7
643 83
270 3
811 31
813 24
707 76
570 61
239 80
817 96
917 17
785 24
875 50
120 51
8 46
930 33
464 73
748 82
377 28
162 14
861 84
358 46
20 10
299 22
159 20
298 41
758 83
124 67
388 21
422 56
593 60
831 61
421 88
181 54
664 40
42 30
419 83
200 21
759 67
737 57
698 39
305 7...

output:

5859428

result:

ok 1 number(s): "5859428"

Test #48:

score: 0
Accepted
time: 726ms
memory: 3940kb

input:

1000 100 5000
106 35
76 76
8 23
308 70
88 32
265 32
463 67
567 43
156 32
52 2
584 81
833 90
689 42
192 30
237 25
184 68
497 21
999 33
850 49
189 18
660 66
478 83
273 18
496 72
466 38
316 66
549 89
354 26
894 77
765 70
581 47
937 85
767 50
424 96
319 8
399 26
493 92
222 99
655 14
933 94
806 15
284 68...

output:

5722436

result:

ok 1 number(s): "5722436"

Test #49:

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

input:

1000 2000 40
64 701
722 362
64 1299
754 1805
380 616
566 1903
781 1619
903 1871
230 977
497 922
209 637
656 261
576 894
222 733
900 104
277 1872
523 1756
297 132
250 538
523 689
650 749
567 648
114 1231
311 1835
205 1980
18 371
919 665
920 274
46 908
40 1034
409 1476
319 1301
44 168
444 990
445 986
...

output:

142200714

result:

ok 1 number(s): "142200714"

Test #50:

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

input:

1000 2000 100
684 1360
268 1574
85 1382
690 114
705 863
453 1825
15 201
919 559
579 944
970 1464
111 419
169 560
898 1549
453 1278
732 302
50 735
216 1223
617 1523
635 250
139 153
253 299
887 102
556 1217
765 301
772 70
533 806
961 1556
723 1040
800 1576
93 1307
342 1975
507 1802
783 864
225 1421
87...

output:

173515609

result:

ok 1 number(s): "173515609"

Test #51:

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

input:

1000 2000 500
108 1246
470 217
947 37
568 252
216 722
374 768
537 398
626 153
236 1522
405 411
855 1168
506 243
226 1614
347 91
418 70
793 938
446 666
538 227
858 1229
826 606
953 1561
701 497
968 277
703 1039
358 1200
405 1799
3 1195
86 571
431 1362
427 1837
481 1505
186 89
492 1260
144 428
22 1896...

output:

554189117

result:

ok 1 number(s): "554189117"

Test #52:

score: 0
Accepted
time: 285ms
memory: 3648kb

input:

1000 2000 1500
410 1420
794 1051
182 1573
884 1027
170 1309
828 1237
310 1854
239 389
499 1053
817 1610
981 803
391 750
415 63
33 560
348 1588
350 1615
235 45
762 1535
419 174
732 1593
488 1128
781 162
816 38
171 1544
813 250
16 1039
910 1947
955 350
512 1439
314 1188
810 877
838 95
90 549
932 1594
...

output:

238838802

result:

ok 1 number(s): "238838802"

Test #53:

score: 0
Accepted
time: 692ms
memory: 3660kb

input:

1000 2000 3000
594 810
636 1425
310 936
25 1300
104 381
955 334
3 80
941 25
715 748
748 1539
342 257
273 1059
565 1794
242 104
492 822
826 1552
86 1930
888 92
792 900
509 1481
57 1594
250 1976
50 1614
649 1921
664 34
874 494
631 1113
791 785
801 1821
108 148
699 1013
294 141
951 821
788 1964
648 671...

output:

654807693

result:

ok 1 number(s): "654807693"

Test #54:

score: 0
Accepted
time: 1163ms
memory: 3864kb

input:

1000 2000 4999
805 1010
323 1847
13 1950
37 1366
731 1283
417 1658
804 213
877 312
468 443
642 1848
737 664
470 1445
377 367
553 1962
703 1958
440 654
163 168
315 1419
21 1939
336 915
646 256
544 713
892 735
913 1409
961 1542
467 1805
31 1306
596 1263
738 1073
210 336
485 1691
271 500
92 687
865 126...

output:

793206926

result:

ok 1 number(s): "793206926"

Test #55:

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

input:

1000 2000 5000
832 1187
140 308
813 919
75 856
7 56
305 218
997 1588
438 411
822 239
314 946
966 35
80 1174
628 1834
62 532
933 1967
51 1294
989 1902
5 1163
493 1868
284 43
8 1418
664 393
226 198
673 629
706 1364
485 1859
821 364
469 417
682 494
910 712
473 818
582 1526
437 364
110 1778
109 418
47 1...

output:

597537195

result:

ok 1 number(s): "597537195"

Test #56:

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

input:

1000 1000000000 40
77 103727882
653 318241889
946 349212567
393 387746557
885 713394545
863 439584423
809 84023534
125 492837794
326 987465290
296 889547838
698 216417880
662 236899348
679 329988738
116 920708460
251 927778395
14 489733306
495 238693006
282 638590509
569 679174340
40 787268400
274 6...

output:

723916280

result:

ok 1 number(s): "723916280"

Test #57:

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

input:

1000 1000000000 100
618 526348331
775 100181278
816 708261363
293 993365232
551 369890766
112 882347154
346 89786899
513 579936592
685 536753990
148 210330348
234 442777116
454 549159447
491 379099400
96 394301462
115 192337929
462 981936402
661 375633818
769 847174570
479 566659166
543 799533412
94...

output:

346357608

result:

ok 1 number(s): "346357608"

Test #58:

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

input:

1000 1000000000 500
962 8467247
494 810480042
243 726115118
91 482985432
499 340977533
595 898436821
868 792226569
782 369467379
904 744776050
225 337634255
541 328886116
354 48205162
738 812469843
552 590688103
880 584189468
768 644735576
892 783676704
690 340575073
264 412150093
230 620503903
129 ...

output:

670463729

result:

ok 1 number(s): "670463729"

Test #59:

score: 0
Accepted
time: 466ms
memory: 3656kb

input:

1000 1000000000 1500
565 597119310
705 944900872
380 439122090
539 233695406
4 109762178
22 999884242
981 387467107
541 871838968
399 164310220
124 623159092
91 11151400
656 990020054
786 871634647
298 193779180
224 507996155
589 678921029
865 463293945
499 444952960
82 966633948
528 229262266
673 8...

output:

404642399

result:

ok 1 number(s): "404642399"

Test #60:

score: 0
Accepted
time: 1161ms
memory: 3840kb

input:

1000 1000000000 3000
669 742624131
547 569944515
990 407638161
242 493013012
455 552519263
195 638405322
112 997281231
244 29808191
257 88699430
55 175035772
451 854071755
100 427057109
981 939033361
507 72859590
931 127458077
985 964561516
153 340403071
144 323851623
455 333110611
947 681478231
884...

output:

446439892

result:

ok 1 number(s): "446439892"

Test #61:

score: 0
Accepted
time: 2051ms
memory: 4112kb

input:

1000 1000000000 4999
960 920378562
671 176891727
773 833629257
691 388545713
2 58928654
93 844828956
913 938014994
742 163562054
10 158943367
868 351936808
846 542935214
297 328598938
231 423667676
256 18564423
143 148647753
117 647229760
230 919642136
490 736646191
683 615283665
694 175746533
474 4...

output:

791232707

result:

ok 1 number(s): "791232707"

Test #62:

score: 0
Accepted
time: 2056ms
memory: 3976kb

input:

1000 1000000000 5000
550 849187319
489 470045862
12 933139325
729 618761897
402 886454822
62 870780310
107 721501355
739 144429026
802 690136827
620 319255724
76 494530127
345 844823685
562 235764547
764 162755404
373 731266552
290 30389483
700 742271235
259 240927556
157 539631486
285 325440581
273...

output:

446268006

result:

ok 1 number(s): "446268006"

Test #63:

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

input:

1000000000 100 40
21614929 93
461614784 91
163670262 33
72329990 4
199472984 67
197079615 75
161450122 26
153888336 40
181669402 73
949917941 43
349622219 24
685955706 99
639790680 46
896317931 82
86939246 1
197769492 46
18406347 85
188847409 77
544939792 95
95989928 97
433612971 86
189176572 10
792...

output:

278181899

result:

ok 1 number(s): "278181899"

Test #64:

score: 0
Accepted
time: 3ms
memory: 3540kb

input:

1000000000 100 100
703598234 33
679420696 99
459844259 42
247638096 23
531187439 11
514864276 86
928352439 15
226394771 40
582739114 74
691361549 56
619858990 44
446438993 79
435484645 5
571470252 60
932846928 62
869086232 35
34976846 25
283887384 96
557316443 38
783035519 18
380375287 49
707654671 ...

output:

907196240

result:

ok 1 number(s): "907196240"

Test #65:

score: 0
Accepted
time: 35ms
memory: 3568kb

input:

1000000000 100 500
37676728 40
146304984 55
922483582 96
279700879 61
519173413 43
458465776 12
945276583 17
318599181 12
734389968 97
605826684 61
446655594 76
593979204 46
221328700 2
904100825 41
301499593 7
845719367 22
435265824 5
38917958 78
70851618 72
900316808 56
287897041 10
762155928 97
3...

output:

578434571

result:

ok 1 number(s): "578434571"

Test #66:

score: 0
Accepted
time: 338ms
memory: 3624kb

input:

1000000000 100 1500
539057299 25
510373193 5
957916743 60
215142360 11
208555244 78
186174891 11
689332299 48
714137024 63
643512474 63
814835521 8
976255879 73
894866044 82
858458026 80
809317325 71
339769646 60
421218188 9
632900853 73
738164659 49
136957493 77
319831753 95
376397381 89
17535660 6...

output:

547189117

result:

ok 1 number(s): "547189117"

Test #67:

score: 0
Accepted
time: 1459ms
memory: 3784kb

input:

1000000000 100 3000
57962185 36
521003394 18
884142201 77
915136367 6
587440993 29
29679590 92
512518500 12
320514743 95
690210025 65
489515660 74
981468379 70
808650664 60
41379556 66
989065606 79
370937671 15
430081150 8
264347706 40
880294951 56
948905588 24
503869746 59
369878599 98
769442112 11...

output:

692562099

result:

ok 1 number(s): "692562099"

Test #68:

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

input:

1000000000 100 4999
641497714 47
138715189 72
78068864 53
373170967 77
892394361 38
208598953 59
111383758 35
542988108 59
581128968 32
145563849 22
563420803 9
923010307 99
705334747 72
459796154 72
565362184 23
571174529 31
381906027 51
629899942 85
62577469 53
954487986 46
670031173 91
885616036 ...

output:

206304920

result:

ok 1 number(s): "206304920"

Test #69:

score: 0
Accepted
time: 4204ms
memory: 3964kb

input:

1000000000 100 5000
330788761 87
32259569 46
834461952 87
110241555 36
864985635 39
50136980 66
137121750 25
885426761 41
284880867 78
870719640 26
656935379 85
618848463 65
162700693 68
275991214 55
539179702 5
993776757 66
715491578 7
300254687 28
131748344 82
261829365 54
363921950 69
592819326 4...

output:

567850893

result:

ok 1 number(s): "567850893"

Test #70:

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

input:

1000000000 2000 40
328732610 1533
240893236 939
813513894 1157
288361777 783
322906279 1237
684440391 1266
550243021 936
243022320 422
360082346 1876
740173768 240
472935397 1883
763395160 1670
233721194 1408
6866945 1251
307911386 1961
845276578 1195
352623714 1587
309858675 1457
432223498 3
920362...

output:

712672083

result:

ok 1 number(s): "712672083"

Test #71:

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

input:

1000000000 2000 100
775977785 444
724755135 1604
574357395 413
722812396 774
508222374 968
496026832 639
663076820 1826
615109826 1646
781290384 1033
74221336 1236
662897295 1241
582339782 1552
164300426 208
394029319 666
48828959 261
432708253 901
221702063 243
369325646 1541
894774259 1708
9579480...

output:

342614501

result:

ok 1 number(s): "342614501"

Test #72:

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

input:

1000000000 2000 500
893236832 330
191639423 1583
36996719 259
459907879 912
791175648 680
66513179 1435
680000964 23
785462090 1094
227908539 1612
693719170 183
567841753 282
729879994 1752
950144480 418
648512038 961
495629477 1510
409341388 811
916958341 1022
419323520 99
191489988 835
75229352 11...

output:

729935351

result:

ok 1 number(s): "729935351"

Test #73:

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

input:

1000000000 2000 1500
55713573 722
15614544 819
249168742 151
306845971 365
465597217 642
499128297 1936
866644038 1364
498491504 1920
293211816 728
264794489 1886
296394246 860
645940372 196
473550777 412
656415813 1817
966815938 1612
59604338 396
956080226 454
574130949 210
41702266 321
555491627 1...

output:

837878018

result:

ok 1 number(s): "837878018"

Test #74:

score: 0
Accepted
time: 1664ms
memory: 3876kb

input:

1000000000 2000 3000
984683856 112
26244745 1047
175394200 996
711872679 639
549515666 1713
637600296 516
984797539 1296
809901921 1410
966794213 569
644507327 1814
596574046 168
559724992 650
361505005 1997
131131395 25
997983963 1364
146615154 997
214411925 194
11228542 248
263715761 1710
11264477...

output:

127347397

result:

ok 1 number(s): "127347397"

Test #75:

score: 0
Accepted
time: 4876ms
memory: 3872kb

input:

1000000000 2000 4999
941334541 975
938923839 1615
369320862 156
169907279 704
854469034 469
521552359 358
288695497 1722
32375287 1697
857713156 1454
517374963 788
961707023 58
752232489 1037
103608052 1380
680009796 1220
270556331 1837
582675833 99
410118100 431
838981386 1947
750502795 896
2682957...

output:

747741505

result:

ok 1 number(s): "747741505"

Test #76:

score: 0
Accepted
time: 4894ms
memory: 3868kb

input:

1000000000 2000 5000
925592888 489
832468219 1412
125713952 833
280093021 194
43879756 1096
658057686 917
392581343 952
669781241 1796
561465055 60
242530754 1884
272041045 92
369922792 619
482826143 555
496204856 1789
461193295 1846
927130207 1929
665555796 167
431188277 1983
741525817 162
79245653...

output:

857804518

result:

ok 1 number(s): "857804518"

Test #77:

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

input:

1000000000 1000000000 40
721000297 752272409
685488581 920220980
298337630 592825837
426516997 87159395
359055567 536870279
126087969 464660004
546821615 746967842
265381300 405501965
614587336 930082327
960685523 222793049
974661504 891501692
354869824 446143492
608245678 837038323
114096841 933588...

output:

266954901

result:

ok 1 number(s): "266954901"

Test #78:

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

input:

1000000000 1000000000 100
612842256 807720481
196970815 29285486
238553189 10838241
353932766 443678370
183681332 579774218
41735320 810109534
238236755 297498419
246712249 386436384
487914569 184479924
374113109 47977961
874436721 473786067
770498946 286982738
488505226 856316247
121865672 68475306...

output:

701848163

result:

ok 1 number(s): "701848163"

Test #79:

score: 0
Accepted
time: 63ms
memory: 3560kb

input:

1000000000 1000000000 500
25068604 289839398
663855103 366469096
701192513 106839850
307847695 523233170
466634606 845828285
395402220 904347055
960193598 999938089
633883958 254115025
639565423 392501983
915463089 880314567
701233324 769960467
701219712 786028452
352497135 662801845
454496244 88113...

output:

635279564

result:

ok 1 number(s): "635279564"

Test #80:

score: 0
Accepted
time: 591ms
memory: 3744kb

input:

1000000000 1000000000 1500
966796879 512961013
732119526 294054610
353473681 284190803
325061104 754537059
291982200 422650216
188284231 267816297
755330891 333233654
107824794 437418474
529876589 738643703
606116546 761913204
124628036 991683710
262839713 768246902
325699903 266755149
306032820 338...

output:

193782150

result:

ok 1 number(s): "193782150"

Test #81:

score: 0
Accepted
time: 2458ms
memory: 3784kb

input:

1000000000 1000000000 3000
895767164 658465833
742749727 919098251
357846993 174559021
730087812 797035219
592720095 943555155
326756230 123156823
795336538 238015079
714202512 968502849
871541441 879852359
280796685 608757183
207988390 129571367
471591633 578399111
508621431 334153862
485781101 512...

output:

591602486

result:

ok 1 number(s): "591602486"

Test #82:

score: 0
Accepted
time: 7043ms
memory: 4056kb

input:

1000000000 1000000000 4999
852417848 619400818
360461522 604193317
473625801 678697971
483089711 909387366
897673463 76849391
210708293 34613157
472349650 588814241
936675877 24108860
467493084 28244152
641877574 707510365
494973513 740286971
664099130 401793086
250724478 740640322
34659502 16306486...

output:

70444985

result:

ok 1 number(s): "70444985"

Test #83:

score: 0
Accepted
time: 7075ms
memory: 3984kb

input:

1000000000 1000000000 5000
541708896 843176876
254005902 819199598
230018890 700060184
925192998 139603551
870264737 904375560
642180920 138712365
203120342 962235202
279114531 4975832
466212283 481289757
662000665 674829282
805307534 770029738
986822132 623050533
629942569 335917747
850854562 30725...

output:

23338781

result:

ok 1 number(s): "23338781"