QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#234869#7517. Flying Ship StorymaspyAC ✓230ms4000kbC++2015.0kb2023-11-02 00:36:262023-11-02 00:36:26

Judging History

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

  • [2023-11-02 00:36:26]
  • 评测
  • 测评结果:AC
  • 用时:230ms
  • 内存:4000kb
  • [2023-11-02 00:36:26]
  • 提交

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;
using u128 = unsigned __int128;
using f128 = __float128;

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); }
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, 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"

void solve() {
  INT(Q);
  vc<int> X, Y, W;

  auto F = [&]() -> void {
    auto I = argsort(W);
    reverse(all(I));
    vc<int> nX, nY, nW;
    for (auto& i: I) {
      int xy = 0, x = 0, y = 0;
      FOR(j, len(nX)) {
        if (nX[j] == X[i] && nY[j] == Y[i]) xy++;
        if (nX[j] == X[i]) ++x;
        if (nY[j] == Y[i]) ++y;
      }
      if (xy >= 1) continue;
      if (x >= 2) continue;
      if (y >= 2) continue;
      nX.eb(X[i]);
      nY.eb(Y[i]);
      nW.eb(W[i]);
      bool end = 0;
      int k = len(nX) - 1;
      FOR(j, k) FOR(i, j) {
        if (nX[i] != nX[j] && nX[i] != nX[k] && nX[j] != nX[k] && nY[i] != nY[j]
            && nY[i] != nY[k] && nY[j] != nY[k])
          end = 1;
      }
      if (end) break;
    }
    swap(X, nX);
    swap(Y, nY);
    swap(W, nW);
  };

  ll last = 0;
  FOR(Q) {
    INT(t);
    if (t == 1) {
      LL(x, y, w);
      x ^= last, y ^= last, w ^= last;
      X.eb(x), Y.eb(y), W.eb(w);
      F();
    }
    if (t == 2) {
      LL(x, y);
      x ^= last, y ^= last;
      ll ANS = 0;
      FOR(i, len(X)) {
        if (X[i] != x && Y[i] != y) { chmax(ANS, W[i]); }
      }
      print(ANS);
      last = ANS;
    }
  }
}

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

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

詳細信息

Test #1:

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

input:

5
1 2 3 1
1 4 5 2
2 2 2
2 3 7
2 3 4

output:

2
1
0

result:

ok 3 lines

Test #2:

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

input:

1000000
2 370943499 431961772
1 1 1 11995570
2 37566858 838793045
1 11995571 11995569 908148975
2 11995571 11995571
1 1 3 716821068
2 67877937 3
1 11995571 11995571 771898489
2 38381714 99749723
1 915818844 915818847 729541681
2 592361351 915818846
1 783627722 783627722 639375021
2 102203700 8636489...

output:

0
11995570
0
11995570
915818845
783627723
915818845
0
0
915818845
0
783627723
0
904468304
904468304
904468304
915818845
904468304
915818845
904468304
915818845
0
904468304
0
915818845
915818845
0
0
915818845
915818845
0
921710773
0
921710773
998138906
921710773
0
921710773
998138906
0
998138906
0
99...

result:

ok 500000 lines

Test #3:

score: 0
Accepted
time: 207ms
memory: 3592kb

input:

1000000
2 648544745 437316088
1 1 1 221075686
2 802693951 691188141
1 221075687 221075684 1036811136
2 771835961 178451319
1 820061031 820061031 560017372
2 829408420 820061028
1 293604539 293604539 699366423
2 293604539 293604539
1 1 2 610044241
2 50747012 885321059
1 942633132 942633132 603537610
...

output:

0
221075686
820061030
293604538
0
942633133
942633133
27478144
820061030
820061030
900696946
27478144
942633133
942633133
0
772167494
27478144
891145650
900696946
772167494
891145650
918281274
772167494
772167494
772167494
772167494
772167494
942633133
918281274
891145650
918281274
891145650
8911456...

result:

ok 500000 lines

Test #4:

score: 0
Accepted
time: 222ms
memory: 3716kb

input:

1000000
2 488777832 43440411
1 441939805 62137297 1349
2 198318033 382339804
1 441938456 72190649 815
2 458351680 72190649
1 441938456 287971850 290
2 161496970 653240491
1 933968337 49827233 1142
2 441938231 49827233
1 623590902 306969890 440
2 441939805 144230480
1 441939265 480404387 11460
2 4419...

output:

0
1349
1349
1642
0
540
440
440
440
11992
4593
4228
9603
4228
12488
7139
4593
14051
14051
14051
16301
4593
20640
14051
34628
20640
34628
35421
34628
34628
49987
11225
17743
11225
17743
35421
17743
35421
17743
49987
56227
56227
11225
11225
56227
56227
56227
56227
56227
37643
37643
49987
37643
37643
21...

result:

ok 500000 lines

Test #5:

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

input:

1000000
2 300988902 687022441
1 363810072 24403398 289
2 441308798 688376935
1 628472989 502933923 685
2 628472989 24403175
1 405185660 444382475 5415
2 405185660 502933634
1 628472989 220347248 2326
2 405185885 151256307
1 38349408 55729241 318
2 996330001 736739645
1 628467867 508628958 4399
2 567...

output:

0
289
0
289
2103
5415
5415
2103
8914
10615
3349
3349
8956
3349
10129
10129
6943
15708
10615
15708
10615
15708
10615
16924
13341
13341
16924
16924
16924
40745
16924
21956
40745
12104
40745
20471
40745
40745
20471
40745
40745
63618
40745
63618
63618
18063
63618
63618
63618
79351
79351
79351
79351
6361...

result:

ok 500000 lines

Test #6:

score: 0
Accepted
time: 230ms
memory: 3712kb

input:

1000000
2 111806459 80284370
1 796602332 100051686 438
2 286632803 842428594
1 34142446 621400092 731
2 53723669 621400092
1 449442772 930459341 4955
2 443764325 137040488
1 748083857 223767926 8188
2 969939167 515353275
1 989422739 346378721 4227
2 748083857 930463126
1 103490800 749046598 2463
2 3...

output:

0
438
438
4845
4845
877
4845
3345
3345
3345
3345
6408
6416
7738
3656
3656
11278
3656
13839
11278
33567
33567
5723
33567
28274
28274
8997
11278
48613
33567
8997
11278
8997
8997
13336
26477
48613
13336
48613
13336
13336
48613
26477
26766
13336
73778
73778
58976
42110
42110
22285
73778
73778
73778
7377...

result:

ok 500000 lines

Test #7:

score: 0
Accepted
time: 221ms
memory: 3928kb

input:

1000000
2 718033726 616016120
1 665760898 359791620 366
2 665760898 204722547
1 452321281 333162973 3799
2 60737187 883719093
1 452325078 2420293 2737
2 464822496 333162250
1 897358098 996437487 472
2 795171894 333163963
1 455003715 996437047 3228
2 787981736 996272822
1 882324943 996435806 3458
2 4...

output:

0
0
3799
1126
1470
3799
1470
1470
705
7238
3252
2338
3252
10340
10340
8986
5114
5114
5114
13813
17199
10340
18118
18118
21931
21931
5114
21931
21931
21931
29195
29195
15488
35715
31726
57783
15488
33759
33759
57783
15488
15488
68258
68258
15488
68258
33759
87915
33759
15488
15488
33759
33759
68258
1...

result:

ok 500000 lines

Test #8:

score: 0
Accepted
time: 219ms
memory: 3712kb

input:

1000000
2 78038813 250486402
1 695391094 534886695 519
2 304811423 718140553
1 158043817 277922962 304
2 803420509 772623626
1 856526470 455200407 6075
2 856526470 211646382
1 589013496 642317455 2046
2 856526470 781887716
1 3773409 455199081 7129
2 489372518 198447772
1 695389286 769439586 7294
2 4...

output:

0
519
823
823
1225
7952
1225
7952
5260
3036
7952
7952
5260
7952
7952
15312
15312
7952
15312
15312
16011
16011
16011
10390
15174
15312
16011
16011
16011
21629
37469
44676
21629
11376
21629
44676
44676
11376
21629
63531
14384
21629
14384
62379
62379
17290
62379
62379
63531
17290
62379
63531
63531
6353...

result:

ok 500000 lines

Test #9:

score: 0
Accepted
time: 223ms
memory: 3928kb

input:

1000000
2 448731011 335554536
1 457642829 423410972 124853177
2 528804845 610815786
1 670970781 30756690 76799653
2 473303284 30756690
1 738493740 200328550 305876016
2 831084154 333999700
1 216806 432769366 522523742
2 886066341 327404401
1 159145853 823055029 119343195
2 1044367644 823055029
1 374...

output:

0
124853177
0
305876016
305876016
220092526
354829419
65193244
385224642
494032668
494032668
494032668
89190365
884278417
804675940
129416032
804675940
494032668
494032668
884278417
804675940
884278417
494032668
884278417
884278417
884278417
494032668
192215999
494032668
494032668
494032668
49403266...

result:

ok 500000 lines

Test #10:

score: 0
Accepted
time: 218ms
memory: 3708kb

input:

1000000
2 153972288 431605536
1 730858411 118081523 61101718
2 597918421 118081523
1 302485264 707599297 51792879
2 666912261 118081523
1 553921748 222588592 19087596
2 679888964 691753006
1 539454520 901424574 281552883
2 780874631 872495545
1 820988875 320547849 114233419
2 245557822 320547849
1 7...

output:

0
0
51792879
37030659
318582000
318582000
338836667
224502837
61101718
481847491
481847491
481847491
814391513
208713218
814391513
695505776
246189170
814391513
695505776
695505776
814391513
814391513
246189170
481847491
481847491
481847491
481847491
695505776
481847491
814391513
481847491
814391513...

result:

ok 500000 lines

Test #11:

score: 0
Accepted
time: 229ms
memory: 3932kb

input:

1000000
2 1756180 842292352
1 749493858 260143625 424
2 985509420 740477290
1 636015984 920180987 292
2 699490704 38801725
1 466966973 773251960 814
2 373096904 461012336
1 199555803 702448186 586
2 466967187 942269722
1 43386889 661927555 758
2 368307964 767725271
1 466967371 652656431 1610
2 46696...

output:

0
424
424
646
424
862
424
3755
1300
3755
12705
1926
1926
3755
2616
3755
3755
24100
3755
2616
5891
2616
5891
4151
5891
5891
41248
10033
5891
41248
41248
41248
16593
15320
5680
16593
8111
8111
41248
8111
15320
41248
8111
31591
9024
15320
15320
15320
9024
74059
74059
24087
24087
31591
31591
74059
74059...

result:

ok 500000 lines

Test #12:

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

input:

1000000
2 418305042 944656569
1 360849688 469845427 1126
2 347770605 7106815
1 264338323 253721049 1533
2 940700400 34983084
1 360850814 469844437 2067
2 360850814 443687475
1 111887484 469845032 238
2 303710556 850291600
1 579127458 578143118 3253
2 560575977 302928526
1 264336256 211480818 1794
2 ...

output:

0
1126
1126
411
3189
3189
3189
2935
7725
7725
192
1775
3421
3189
3189
3189
1775
6608
6608
7725
7725
37311
6608
37311
6608
5714
5714
6608
5714
7725
6608
37311
14524
15851
15851
37311
21334
5714
5714
5714
37311
7210
7210
21334
21334
7210
21334
21334
19271
37311
19271
7210
7210
19271
19271
19271
13320
...

result:

ok 500000 lines

Test #13:

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

input:

1000000
2 804115895 2661276
1 180734654 156813060 300
2 253741442 156813060
1 472942411 314635336 231
2 87507808 156813060
1 349452733 767165 1911
2 349452733 156813283
1 472942508 217877748 416
2 349452733 96729439
1 472942092 59977469 119
2 472942092 767261
1 945007344 767350 1508
2 274364371 3192...

output:

0
0
231
231
327
300
1936
2204
2204
1936
3744
3744
3744
2867
2867
1759
6346
6346
6346
6346
1759
6346
6346
4476
6346
4476
4476
16555
4476
4476
6022
10043
10043
10043
16555
6022
6022
16555
16555
6022
67548
6022
12030
12030
67548
12030
18086
33442
6022
33442
33442
6022
20211
33442
67548
33442
67548
6754...

result:

ok 500000 lines

Test #14:

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

input:

1000000
2 103013178 687790552
1 247109364 453485616 417
2 247109364 560197
1 301015532 533028723 397
2 61889261 157540231
1 247109461 730927600 167
2 247109461 292968626
1 781831237 475527032 758
2 715010644 138797384
1 301015703 42413404 459
2 67760275 589415471
1 665349790 944974343 285
2 78183185...

output:

0
0
417
397
891
891
688
3230
688
3230
1253
9794
1253
3230
3230
9794
3230
9794
5992
3230
3230
3230
5992
5992
5992
13944
23480
23480
4013
13944
23480
23480
4013
26211
42117
42117
12844
12844
60131
26211
7996
26211
26211
26211
9971
26211
26211
60131
60131
13482
13482
12149
12149
13482
13482
13482
12149...

result:

ok 500000 lines

Test #15:

score: 0
Accepted
time: 216ms
memory: 3764kb

input:

1000000
2 571465209 203365081
1 466753949 726269346 120489823
2 466753949 369486616
1 466753949 601231229 251422109
2 466753949 726269346
1 131434952 337438435 82190750
2 466753949 726269346
1 520104744 284870525 55655366
2 421460934 74147403
1 310575874 450921342 743860879
2 355367936 450921342
1 1...

output:

0
0
0
82190750
251422109
0
581570322
581570322
581570322
150072005
150072005
124030323
581570322
581570322
124030323
251422109
251422109
124030323
169831141
251422109
124030323
882989709
882989709
169831141
169831141
169831141
882989709
169831141
124392464
169831141
124392464
169831141
882989709
882...

result:

ok 500000 lines