QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#642771#8335. Fast Hash TransformmaspyAC ✓4904ms36756kbC++2018.6kb2024-10-15 16:14:072024-10-15 16:14:08

Judging History

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

  • [2024-10-15 16:14:08]
  • 评测
  • 测评结果:AC
  • 用时:4904ms
  • 内存:36756kb
  • [2024-10-15 16:14:07]
  • 提交

answer

#line 1 "/home/maspy/compro/library/my_template.hpp"
#if defined(LOCAL)
#include <my_template_compiled.hpp>
#else

// https://codeforces.com/blog/entry/96344
#pragma GCC optimize("Ofast,unroll-loops")
// いまの CF だとこれ入れると動かない?
// #pragma GCC target("avx2,popcnt")

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i128 = __int128;
using u128 = unsigned __int128;
using f128 = __float128;

template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'010'000'000;
template <>
constexpr ll infty<ll> = 2'020'000'000'000'000'000;
template <>
constexpr u32 infty<u32> = infty<int>;
template <>
constexpr u64 infty<u64> = infty<ll>;
template <>
constexpr i128 infty<i128> = i128(infty<ll>) * 2'000'000'000'000'000'000;
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); }
int popcnt_mod_2(int x) { return __builtin_parity(x); }
int popcnt_mod_2(u32 x) { return __builtin_parity(x); }
int popcnt_mod_2(ll x) { return __builtin_parityll(x); }
int popcnt_mod_2(u64 x) { return __builtin_parityll(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>
T floor(T a, T b) {
  return a / b - (a % b && (a ^ b) < 0);
}
template <typename T>
T ceil(T x, T y) {
  return floor(x + y - 1, y);
}
template <typename T>
T bmod(T x, T y) {
  return x - y * floor(x, y);
}
template <typename T>
pair<T, T> divmod(T x, T y) {
  T q = floor(x, y);
  return {q, x - q * y};
}

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

#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) {
  T a = que.top();
  que.pop();
  return a;
}
template <typename T>
T POP(vc<T> &que) {
  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;
    (check(x) ? ok : ng) = 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;
    (check(x) ? ok : ng) = 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;
}

template <typename T, typename... Vectors>
void concat(vc<T> &first, const Vectors &... others) {
  vc<T> &res = first;
  (res.insert(res.end(), others.begin(), others.end()), ...);
}
#endif
#line 1 "/home/maspy/compro/library/other/io.hpp"
#define FASTIO
#include <unistd.h>

// https://judge.yosupo.jp/submission/21623
namespace fastio {
static constexpr uint32_t SZ = 1 << 17;
char ibuf[SZ];
char obuf[SZ];
char out[100];
// pointer of ibuf, obuf
uint32_t pil = 0, pir = 0, por = 0;

struct Pre {
  char num[10000][4];
  constexpr Pre() : num() {
    for (int i = 0; i < 10000; i++) {
      int n = i;
      for (int j = 3; j >= 0; j--) {
        num[i][j] = n % 10 | '0';
        n /= 10;
      }
    }
  }
} constexpr pre;

inline void load() {
  memcpy(ibuf, ibuf + pil, pir - pil);
  pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);
  pil = 0;
  if (pir < SZ) ibuf[pir++] = '\n';
}

inline void flush() {
  fwrite(obuf, 1, por, stdout);
  por = 0;
}

void rd(char &c) {
  do {
    if (pil + 1 > pir) load();
    c = ibuf[pil++];
  } while (isspace(c));
}

void rd(string &x) {
  x.clear();
  char c;
  do {
    if (pil + 1 > pir) load();
    c = ibuf[pil++];
  } while (isspace(c));
  do {
    x += c;
    if (pil == pir) load();
    c = ibuf[pil++];
  } while (!isspace(c));
}

template <typename T>
void rd_real(T &x) {
  string s;
  rd(s);
  x = stod(s);
}

template <typename T>
void rd_integer(T &x) {
  if (pil + 100 > pir) load();
  char c;
  do
    c = ibuf[pil++];
  while (c < '-');
  bool minus = 0;
  if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
    if (c == '-') { minus = 1, c = ibuf[pil++]; }
  }
  x = 0;
  while ('0' <= c) { x = x * 10 + (c & 15), c = ibuf[pil++]; }
  if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
    if (minus) x = -x;
  }
}

void rd(int &x) { rd_integer(x); }
void rd(ll &x) { rd_integer(x); }
void rd(i128 &x) { rd_integer(x); }
void rd(u32 &x) { rd_integer(x); }
void rd(u64 &x) { rd_integer(x); }
void rd(u128 &x) { rd_integer(x); }
void rd(double &x) { rd_real(x); }
void rd(long double &x) { rd_real(x); }
void rd(f128 &x) { rd_real(x); }

template <class T, class U>
void rd(pair<T, U> &p) {
  return rd(p.first), rd(p.second);
}
template <size_t N = 0, typename T>
void rd_tuple(T &t) {
  if constexpr (N < std::tuple_size<T>::value) {
    auto &x = std::get<N>(t);
    rd(x);
    rd_tuple<N + 1>(t);
  }
}
template <class... T>
void rd(tuple<T...> &tpl) {
  rd_tuple(tpl);
}

template <size_t N = 0, typename T>
void rd(array<T, N> &x) {
  for (auto &d: x) rd(d);
}
template <class T>
void rd(vc<T> &x) {
  for (auto &d: x) rd(d);
}

void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
  rd(h), read(t...);
}

void wt(const char c) {
  if (por == SZ) flush();
  obuf[por++] = c;
}
void wt(const string s) {
  for (char c: s) wt(c);
}
void wt(const char *s) {
  size_t len = strlen(s);
  for (size_t i = 0; i < len; i++) wt(s[i]);
}

template <typename T>
void wt_integer(T x) {
  if (por > SZ - 100) flush();
  if (x < 0) { obuf[por++] = '-', x = -x; }
  int outi;
  for (outi = 96; x >= 10000; outi -= 4) {
    memcpy(out + outi, pre.num[x % 10000], 4);
    x /= 10000;
  }
  if (x >= 1000) {
    memcpy(obuf + por, pre.num[x], 4);
    por += 4;
  } else if (x >= 100) {
    memcpy(obuf + por, pre.num[x] + 1, 3);
    por += 3;
  } else if (x >= 10) {
    int q = (x * 103) >> 10;
    obuf[por] = q | '0';
    obuf[por + 1] = (x - q * 10) | '0';
    por += 2;
  } else
    obuf[por++] = x | '0';
  memcpy(obuf + por, out + outi + 4, 96 - outi);
  por += 96 - outi;
}

template <typename T>
void wt_real(T x) {
  ostringstream oss;
  oss << fixed << setprecision(15) << double(x);
  string s = oss.str();
  wt(s);
}

void wt(int x) { wt_integer(x); }
void wt(ll x) { wt_integer(x); }
void wt(i128 x) { wt_integer(x); }
void wt(u32 x) { wt_integer(x); }
void wt(u64 x) { wt_integer(x); }
void wt(u128 x) { wt_integer(x); }
void wt(double x) { wt_real(x); }
void wt(long double x) { wt_real(x); }
void wt(f128 x) { wt_real(x); }

template <class T, class U>
void wt(const pair<T, U> val) {
  wt(val.first);
  wt(' ');
  wt(val.second);
}
template <size_t N = 0, typename T>
void wt_tuple(const T t) {
  if constexpr (N < std::tuple_size<T>::value) {
    if constexpr (N > 0) { wt(' '); }
    const auto x = std::get<N>(t);
    wt(x);
    wt_tuple<N + 1>(t);
  }
}
template <class... T>
void wt(tuple<T...> tpl) {
  wt_tuple(tpl);
}
template <class T, size_t S>
void wt(const array<T, S> val) {
  auto n = val.size();
  for (size_t i = 0; i < n; i++) {
    if (i) wt(' ');
    wt(val[i]);
  }
}
template <class T>
void wt(const vector<T> val) {
  auto n = val.size();
  for (size_t i = 0; i < n; i++) {
    if (i) wt(' ');
    wt(val[i]);
  }
}

void print() { wt('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
  wt(head);
  if (sizeof...(Tail)) wt(' ');
  print(forward<Tail>(tail)...);
}

// gcc expansion. called automaticall after main.
void __attribute__((destructor)) _d() { flush(); }
} // namespace fastio
using fastio::read;
using fastio::print;
using fastio::flush;

#if defined(LOCAL)
#define SHOW(...) SHOW_IMPL(__VA_ARGS__, SHOW6, SHOW5, SHOW4, SHOW3, SHOW2, SHOW1)(__VA_ARGS__)
#define SHOW_IMPL(_1, _2, _3, _4, _5, _6, NAME, ...) NAME
#define SHOW1(x) print(#x, "=", (x)), flush()
#define SHOW2(x, y) print(#x, "=", (x), #y, "=", (y)), flush()
#define SHOW3(x, y, z) print(#x, "=", (x), #y, "=", (y), #z, "=", (z)), flush()
#define SHOW4(x, y, z, w) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w)), flush()
#define SHOW5(x, y, z, w, v) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w), #v, "=", (v)), flush()
#define SHOW6(x, y, z, w, v, u) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w), #v, "=", (v), #u, "=", (u)), flush()
#else
#define SHOW(...)
#endif

#define INT(...)   \
  int __VA_ARGS__; \
  read(__VA_ARGS__)
#define LL(...)   \
  ll __VA_ARGS__; \
  read(__VA_ARGS__)
#define U32(...)   \
  u32 __VA_ARGS__; \
  read(__VA_ARGS__)
#define U64(...)   \
  u64 __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 "/home/maspy/compro/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 "/home/maspy/compro/library/random/base.hpp"

u64 RNG_64() {
  static uint64_t x_
      = uint64_t(chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()) * 10150724397891781847ULL;
  x_ ^= x_ << 7;
  return x_ ^= x_ >> 9;
}

u64 RNG(u64 lim) { return RNG_64() % lim; }

ll RNG(ll l, ll r) { return l + RNG_64() % (r - l); }
#line 6 "main.cpp"

using ARR = array<u64, 64>;
using MAT = pair<ARR, u64>;

constexpr u64 RND = 941191446945809507;

ARR ZERO;

struct Mono {
  using value_type = MAT;
  using X = value_type;
  static X op(X &A, X &B) {
    if (A.se == RND) return B;
    if (B.se == RND) return A;
    auto [X, x] = A;
    auto [Y, y] = B;
    ARR Z = ZERO;
    u64 z = 0;

    FOR(i, 64) {
      FOR(j, 64) {
        if (X[i] >> j & 1) { Z[i] ^= Y[j]; }
      }
    }
    z ^= y;
    FOR(i, 64) if (x >> i & 1) z ^= Y[i];
    return {Z, z};
  }

  static constexpr X unit() { return {ZERO, RND}; }
  static constexpr bool commute = 0;
};

void solve() {
  LL(N, Q, ccc);

  auto read_matrix = [&](int idx) -> MAT {
    ARR X = ZERO;
    u64 add = 0;
    LL(m);
    FOR(m) {
      INT(s);
      INT(op);
      U64(a);
      // a op (x<<s) を XOR する
      if (op == 0) {
        // OR
        FOR(i, 64) {
          if (a >> i & 1) {
            // 必ず 1
            add ^= u64(1) << i;
          } else {
            X[(64 + i - s) & 63] ^= u64(1) << i;
          }
        }
      }
      if (op == 1) {
        // AND
        FOR(i, 64) {
          if (!(a >> i & 1)) {
            // 必ず 0
          } else {
            X[(64 + i - s) & 63] ^= u64(1) << i;
          }
        }
      }
    }
    U64(b);
    add ^= b;
    return {X, add};
  };
  SegTree<Mono> seg(N, read_matrix);

  FOR(Q) {
    INT(tp);
    if (tp == 0) {
      LL(L, R);
      U64(v);
      auto [X, add] = seg.prod(--L, R);
      u64 ANS = 0;
      FOR(i, 64) {
        if (v >> i & 1) ANS ^= X[i];
      }
      ANS ^= add;
      print(ANS);
    }
    if (tp == 1) {
      INT(idx);
      --idx;
      seg.set(idx, read_matrix(idx));
    }
  }
}

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

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 5 1
1 4 0 0 51966
1 60 0 0 0
1 0 0 16 15
0 1 1 771
0 2 2 32368
0 3 3 0
1 2 2 0 0 15 61 1 4095 46681
0 1 3 2023

output:

64206
2023
31
1112

result:

ok 4 tokens

Test #2:

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

input:

9 9 3
32 9 0 17785061119123981789 33 0 10890571864137198682 42 0 9437574736788763477 34 0 5239651887868507470 55 0 14741743279679654187 27 1 1444116632918569317 38 1 5740886562180922636 1 1 8113356142324084796 3 0 10955266306442425904 60 0 16421026339459788005 53 0 1595107134632608917 48 1 923204972...

output:

9487331362121050549
3906661590723083106
15757672015979182109
4975471776251039345
11503109206538591140
3763610618439604410

result:

ok 6 tokens

Test #3:

score: 0
Accepted
time: 11ms
memory: 3980kb

input:

1 20000 400
32 13 0 1721926083061553294 52 1 8951352260297008058 6 0 3180917732545757991 63 1 14978562500072226750 50 1 7331113732303115313 59 0 688182721924779475 12 0 16291922173168822489 61 0 16018198440613086698 8 0 12494084957448674305 7 0 2834422858291562646 42 1 10354539547309738529 28 0 2541...

output:

11827781865759498816
7454610526276185721
9581050724293785387
2177163806257271094
14004004964877510141
18073834598135159471
16966489063087641088
12289032565388413023
17823140805867698239
18104549908461644670
15570008264282957124
12400954982104000299
9842549278742638708
16535034933613060362
1561642006...

result:

ok 19600 tokens

Test #4:

score: 0
Accepted
time: 1709ms
memory: 3980kb

input:

500 20000 400
32 3 0 9869926173615303101 39 1 11114680792832491178 54 1 3380955246053990760 31 0 16868042247314276464 26 0 5814925615581342395 30 1 1114053898154397400 46 1 9215698002668459992 38 1 12938485987410997250 58 0 8030873196223549640 0 0 16055471402053138912 47 1 16568729207788187629 63 0 ...

output:

9119093329811149961
16901643057538871933
17161855998497876349
3964234071281411558
13588188063229334268
15557968976322375381
4612345875926431452
9507168112801039022
9504318642653891468
217407202160767706
12982350345598971306
17957502630817476223
6353877977318728572
15552768639781831485
16778108770682...

result:

ok 19600 tokens

Test #5:

score: 0
Accepted
time: 2658ms
memory: 7408kb

input:

4000 20000 400
35 33 0 18435679328748604368 55 1 10851974578636476759 1 0 11332084644969697080 13 0 4243547822701774011 19 0 18197854269436975495 32 0 10133703694198056054 6 0 12655387670867301210 36 0 1246525872821095171 51 1 812047498663608637 4 0 9797423115860097390 7 1 12105773148377740641 17 0 ...

output:

11875257514484243925
3443357416933857062
16160011677622853538
1582145987019406393
15019762274690743371
3128972641411454448
10632018957963074870
2420532366876270818
16130728863118353230
15834956073901517645
18404809296474853851
10982435108266120760
16463778300806795274
11990886156320593058
1145171640...

result:

ok 19600 tokens

Test #6:

score: 0
Accepted
time: 3631ms
memory: 36700kb

input:

20000 20000 0
34 47 1 3147866938814566873 50 0 8051884074279018250 4 0 11476150812073861567 54 0 3931985566612211642 60 1 9226417006726638292 49 0 2435425653073267226 33 1 5976119177961927073 40 1 3169532703977184656 2 1 17206894689684881943 37 0 2316971949450684490 7 1 7087775905790436416 18 1 7557...

output:

8031710763259664674
10015579400510819759
9509776159199873854
252965904282343862
17471441301398284397
6167329408972068582
11581702001320217920
13373488743211628824
2094753313448112669
15503010008451014749
384500896248723935
10501371892025480221
8907735695899875922
14479597201387282763
164403466075406...

result:

ok 20000 tokens

Test #7:

score: 0
Accepted
time: 3647ms
memory: 36756kb

input:

20000 20000 20
28 31 1 17220760822712602145 12 1 10079395927654210001 40 0 10440736241216457314 20 1 14759495678166748212 55 1 8734257463550073646 60 0 543206106562221008 29 1 5402811237936853387 52 1 3884345269948184760 22 0 7873959847686200341 15 1 18396630536251250330 25 0 18230407003294263406 14...

output:

6531775129959975384
6212576544894999781
4191848452578359691
2769536540387251859
15526337103142577854
14948743844803225542
15235110724610778185
9004056994453026335
1028305510694260706
13496210650896843548
13961471020487846633
1864980030930734934
15243868808579626755
10451839696548403150
1178402342726...

result:

ok 19980 tokens

Test #8:

score: 0
Accepted
time: 3659ms
memory: 36628kb

input:

20000 20000 400
41 15 1 10590708978689078436 33 0 17448869030270552656 37 1 16782453056389226553 2 1 18313039076194285622 53 1 7894371271572806769 60 1 14563226108042670650 56 0 12694119759311053234 12 1 969626878679760122 28 1 8906626075909573228 20 1 11632670066953088447 50 0 13097960756795495550 ...

output:

7425391644666486729
17533666397961516801
16986235811843827275
1784742314571007240
13192305384063626572
12739810377012216000
1179361465141596122
7698346401428161235
6903188112913915716
5380404381348976227
16126105607866972637
12798978320947566556
11234201442491665890
16073897288956866956
151328474491...

result:

ok 19600 tokens

Test #9:

score: 0
Accepted
time: 3647ms
memory: 36636kb

input:

20000 20000 400
33 39 1 17067623245236507261 27 1 7041428814521205530 50 1 10823426118594256003 28 1 7163716190894912799 12 1 4080987667516350158 63 0 17082717673883070565 17 0 11310350135715835231 51 1 12855244004029414317 38 0 9814237273168847221 57 1 3708701962235763971 37 0 10158992933772396697 ...

output:

6864973236048047224
18318008901523164537
13500746067907696382
13161681605750995854
3452654261090196316
14847903013724109682
7301818645657195470
15784097910646013208
6555334273152043996
6337001136120562705
7065460407919669838
17502323856909932125
12099828260978288865
17244785354672463736
159661862214...

result:

ok 19600 tokens

Test #10:

score: 0
Accepted
time: 436ms
memory: 36628kb

input:

20000 20000 0
37 46 0 4806156443854081866 29 0 6910842714881233745 61 0 9379366064412681113 32 1 718568893402460472 45 0 1234243654449881049 16 0 9791590151480029686 24 1 801156398497308107 20 1 1638149966892153162 3 1 483739892768149714 56 1 3070030763953269690 38 1 11944075913457601606 6 1 8068547...

output:

17693343388614420171
11014279187501816246
7111154205373939902
5948421254644613369
5776121468606637836
16944170640450069348
8394185836099893155
11947149219582604015
4508739183749291929
11471060687727420580
3924131475517252887
1743542114579130111
14487529569441993654
8062193838630657668
18359613799309...

result:

ok 20000 tokens

Test #11:

score: 0
Accepted
time: 519ms
memory: 36708kb

input:

20000 20000 400
31 63 1 14360706182574306953 17 0 4643864577315796645 48 0 11264878137122897405 18 1 14150130986659920202 25 1 15979000250901513596 49 0 16241841209566112679 37 1 16762565151400121253 14 1 7376170230332808198 26 1 10868082441744868454 27 1 6949308347230687639 44 1 4116452321258930556...

output:

4493451016206578040
14208826853413050113
15020158700931574670
16337826900074673926
5403566933376608394
8871156492968482557
8911109963819675601
6213157285507240354
17190717170193641517
15578273901773478953
1369444627312020075
11786462107951385516
17634527799358234224
18347358352139830828
145863906383...

result:

ok 19600 tokens

Test #12:

score: 0
Accepted
time: 4673ms
memory: 36732kb

input:

20000 20000 0
25 16 0 2668205375195949736 34 0 2748287585311204102 37 1 4531486636255948251 24 0 14410309392802368907 52 1 851885811168352867 47 1 15887239727531457455 42 0 8819527325570258215 44 0 16146066124743535517 46 1 1041563265194349313 11 1 13140073107604291185 0 1 16670532562293262804 56 1 ...

output:

5924012028700061898
4718073419648080016
13993322115865028469
82790239609178342
887419913876033685
15321668567642867070
8962935781265467660
1552533755174937777
16683793257623944188
6900756788022393102
10981237528745871227
5789630421744738481
9056874037200094100
15328577526113324947
627381852022728881...

result:

ok 20000 tokens

Test #13:

score: 0
Accepted
time: 4673ms
memory: 36544kb

input:

20000 20000 400
29 26 0 4544814232153615705 62 0 13471881549916225637 53 0 595040484360290534 17 1 11949377632182068615 20 0 9311349995021422035 60 0 816595034603135343 48 0 10654197142859256352 24 0 4772788762907504538 54 0 15584542718632709463 19 1 2151387765439259665 41 1 15099291996319444694 40 ...

output:

1423325416659742802
17371677980372930727
3681232738426467215
13266462173687709877
12639633063779823269
1946619485256865431
12989302207328517036
14138867084917472527
18218337902938347758
3372796243270362661
673871038008779791
9077527952253879051
7326631285358366273
2710349874806590369
172928358344422...

result:

ok 19600 tokens

Test #14:

score: 0
Accepted
time: 4682ms
memory: 36620kb

input:

20000 20000 400
24 38 1 3460586314685566112 26 0 4188084273268315686 61 0 1227557406397452582 25 1 5747999803901747386 41 1 1907261769878407698 27 0 16752772615002344376 34 0 17112817990633067537 60 0 9291256903378353577 45 0 7510343555807629464 13 0 18007693761515887577 9 1 17317953029923040761 4 0...

output:

13100999329968562920
15516017614708332089
5382331705592343945
357522576585990254
16311520569626827168
6758986479859611544
12732461424037837989
8966988217248420501
10391550114259677068
4660694210255306341
7237506373169380284
13657244350225493605
6916780657676036471
10881113620462446827
16277857127600...

result:

ok 19600 tokens

Test #15:

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

input:

20000 20000 400
60 25 1 2719522369398288789 40 1 9400902170286318935 6 1 9521944178235051324 43 0 11768204916287391421 22 0 12726538799306592512 47 1 15759776307217345226 17 1 15438840904724459733 13 0 17863856648581711698 29 1 4032777103500438360 10 0 683992519125165540 26 1 15461667428831774672 14...

output:

412280358023687627
14769812881817125733
18318455003071307239
6658808483284331159
6130439376668456888
1492308137069243960
5853920885317257980
12553163529022332915
7520793755811132601
13993258994649409340
13568418050081351467
12309096149487021368
17899306611786296579
2598853739059100346
14630776750608...

result:

ok 19600 tokens

Test #16:

score: 0
Accepted
time: 3866ms
memory: 36756kb

input:

20000 20000 400
58 17 0 7751036624596546188 29 0 17432650278695392920 63 0 4389503693497138241 24 0 11063030485327807810 45 1 18240337466752243882 59 1 17804018980843534887 60 1 5872699360277748939 21 1 10429471649278268372 27 0 16762274761588446397 54 0 6030940442592696599 19 1 13270942932118095691...

output:

17867517807501868664
7775943633465469655
1824462793515136478
12630456144448858727
16944355600951673184
14837233611662521712
13878709289450326681
13750017221938869139
11379793111096427897
15527971528797740116
5872004578520784281
11280146030218952435
5218412287620909707
15541801824852151484
5650476389...

result:

ok 19600 tokens

Test #17:

score: 0
Accepted
time: 3880ms
memory: 36628kb

input:

20000 20000 400
60 22 0 12707603241789460389 46 0 15086313545825117890 33 0 909121147706895901 59 1 6114670732197551336 41 0 3090389396605293219 63 0 6608018621123394175 38 1 11836608073091750746 14 1 4878457553941336535 5 0 6024711164477768229 25 1 67199414342206654 24 0 1139176812912408779 16 0 12...

output:

11101670153251608253
675780991220106254
15866623643054791619
16323951405331282505
9135544362908319645
7642151295897109981
12351493946367393308
1935066719605622920
7518368202469961257
11600515247827283279
15933103715396571729
13453007077105135208
14727385649041622999
123215011875209372
76221879547507...

result:

ok 19600 tokens

Test #18:

score: 0
Accepted
time: 4902ms
memory: 36700kb

input:

20000 20000 400
57 0 1 16995927798044259033 30 1 4411529108320693455 35 1 14740826024996968953 32 1 14741500464787789772 5 1 13621297821910096766 47 1 1805557230674866983 26 0 1852515218899978614 37 1 14167448543730803554 15 0 8207408801869448845 7 0 2253659179521891807 61 1 1303777112793499927 1 1 ...

output:

14640221015002441272
8108797686286238378
619977752116985977
17860455208859938460
2219391733727955287
17098130710123326231
4643402762732727695
1576822124091279449
2112594951252396904
11012866398108256228
3100264803360198048
1520325785935749501
17234063909328734373
2294517371241459639
6577965043160831...

result:

ok 19600 tokens

Test #19:

score: 0
Accepted
time: 4902ms
memory: 36696kb

input:

20000 20000 400
60 23 1 12967402093469929995 29 0 12482782180176810891 47 1 17290909632526370536 5 0 17372530581982291607 62 1 13987764289696466564 41 1 8421162609706963610 53 0 18089202028338115523 10 0 1312033850971950221 2 0 3337291528457528731 18 1 17751876270582349954 32 0 13359684730271699557 ...

output:

8219634040467306280
7488593258162917054
3429645423088159837
13823280993584110417
4972072459402131521
8504404100763034378
5815021261728531941
5670841473953742448
6721982245071008063
8353993923949852878
4277531481899017404
5173775653727609205
4061296038432070306
11044359884601198871
272114767395246212...

result:

ok 19600 tokens

Test #20:

score: 0
Accepted
time: 4904ms
memory: 36692kb

input:

20000 20000 400
56 3 0 14386867255986651070 17 1 5876678743420202175 24 0 2472800002233203764 40 0 3974575279492546522 5 1 10323896862538344788 31 0 15302550669828857297 10 0 8188514003112427229 28 0 9350793473465284653 34 1 1051624389221640716 56 1 12992224832956122800 0 1 12521917684359350214 33 1...

output:

16023098103166573969
5488057777512126106
2364974952009032490
6867156023979603961
13898097818261510588
3896697852262723116
13075557814956081246
550932186457628322
1501306951093128873
12801415593941350129
12431218450278358855
8287212554931924015
7521994383511852994
7781645210267880075
1658905057583045...

result:

ok 19600 tokens

Extra Test:

score: 0
Extra Test Passed