QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#723913#9608. 皮鞋的多项式hos_lyric10 1075ms38728kbC++1412.1kb2024-11-08 03:29:432024-11-08 03:29:48

Judging History

This is the latest submission verdict.

  • [2024-11-08 03:29:48]
  • Judged
  • Verdict: 10
  • Time: 1075ms
  • Memory: 38728kb
  • [2024-11-08 03:29:43]
  • Submitted

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
  static constexpr unsigned M = M_;
  unsigned x;
  constexpr ModInt() : x(0U) {}
  constexpr ModInt(unsigned x_) : x(x_ % M) {}
  constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1U); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
constexpr unsigned MO = 998244353U;
constexpr unsigned MO2 = 2U * MO;
constexpr int FFT_MAX = 23;
using Mint = ModInt<MO>;
constexpr Mint FFT_ROOTS[FFT_MAX + 1] = {1U, 998244352U, 911660635U, 372528824U, 929031873U, 452798380U, 922799308U, 781712469U, 476477967U, 166035806U, 258648936U, 584193783U, 63912897U, 350007156U, 666702199U, 968855178U, 629671588U, 24514907U, 996173970U, 363395222U, 565042129U, 733596141U, 267099868U, 15311432U};
constexpr Mint INV_FFT_ROOTS[FFT_MAX + 1] = {1U, 998244352U, 86583718U, 509520358U, 337190230U, 87557064U, 609441965U, 135236158U, 304459705U, 685443576U, 381598368U, 335559352U, 129292727U, 358024708U, 814576206U, 708402881U, 283043518U, 3707709U, 121392023U, 704923114U, 950391366U, 428961804U, 382752275U, 469870224U};
constexpr Mint FFT_RATIOS[FFT_MAX] = {911660635U, 509520358U, 369330050U, 332049552U, 983190778U, 123842337U, 238493703U, 975955924U, 603855026U, 856644456U, 131300601U, 842657263U, 730768835U, 942482514U, 806263778U, 151565301U, 510815449U, 503497456U, 743006876U, 741047443U, 56250497U, 867605899U};
constexpr Mint INV_FFT_RATIOS[FFT_MAX] = {86583718U, 372528824U, 373294451U, 645684063U, 112220581U, 692852209U, 155456985U, 797128860U, 90816748U, 860285882U, 927414960U, 354738543U, 109331171U, 293255632U, 535113200U, 308540755U, 121186627U, 608385704U, 438932459U, 359477183U, 824071951U, 103369235U};

// as[rev(i)] <- \sum_j \zeta^(ij) as[j]
void fft(Mint *as, int n) {
  assert(!(n & (n - 1))); assert(1 <= n); assert(n <= 1 << FFT_MAX);
  int m = n;
  if (m >>= 1) {
    for (int i = 0; i < m; ++i) {
      const unsigned x = as[i + m].x;  // < MO
      as[i + m].x = as[i].x + MO - x;  // < 2 MO
      as[i].x += x;  // < 2 MO
    }
  }
  if (m >>= 1) {
    Mint prod = 1U;
    for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
      for (int i = i0; i < i0 + m; ++i) {
        const unsigned x = (prod * as[i + m]).x;  // < MO
        as[i + m].x = as[i].x + MO - x;  // < 3 MO
        as[i].x += x;  // < 3 MO
      }
      prod *= FFT_RATIOS[__builtin_ctz(++h)];
    }
  }
  for (; m; ) {
    if (m >>= 1) {
      Mint prod = 1U;
      for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
        for (int i = i0; i < i0 + m; ++i) {
          const unsigned x = (prod * as[i + m]).x;  // < MO
          as[i + m].x = as[i].x + MO - x;  // < 4 MO
          as[i].x += x;  // < 4 MO
        }
        prod *= FFT_RATIOS[__builtin_ctz(++h)];
      }
    }
    if (m >>= 1) {
      Mint prod = 1U;
      for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
        for (int i = i0; i < i0 + m; ++i) {
          const unsigned x = (prod * as[i + m]).x;  // < MO
          as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x;  // < 2 MO
          as[i + m].x = as[i].x + MO - x;  // < 3 MO
          as[i].x += x;  // < 3 MO
        }
        prod *= FFT_RATIOS[__builtin_ctz(++h)];
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x;  // < 2 MO
    as[i].x = (as[i].x >= MO) ? (as[i].x - MO) : as[i].x;  // < MO
  }
}

// as[i] <- (1/n) \sum_j \zeta^(-ij) as[rev(j)]
void invFft(Mint *as, int n) {
  assert(!(n & (n - 1))); assert(1 <= n); assert(n <= 1 << FFT_MAX);
  int m = 1;
  if (m < n >> 1) {
    Mint prod = 1U;
    for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
      for (int i = i0; i < i0 + m; ++i) {
        const unsigned long long y = as[i].x + MO - as[i + m].x;  // < 2 MO
        as[i].x += as[i + m].x;  // < 2 MO
        as[i + m].x = (prod.x * y) % MO;  // < MO
      }
      prod *= INV_FFT_RATIOS[__builtin_ctz(++h)];
    }
    m <<= 1;
  }
  for (; m < n >> 1; m <<= 1) {
    Mint prod = 1U;
    for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
      for (int i = i0; i < i0 + (m >> 1); ++i) {
        const unsigned long long y = as[i].x + MO2 - as[i + m].x;  // < 4 MO
        as[i].x += as[i + m].x;  // < 4 MO
        as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x;  // < 2 MO
        as[i + m].x = (prod.x * y) % MO;  // < MO
      }
      for (int i = i0 + (m >> 1); i < i0 + m; ++i) {
        const unsigned long long y = as[i].x + MO - as[i + m].x;  // < 2 MO
        as[i].x += as[i + m].x;  // < 2 MO
        as[i + m].x = (prod.x * y) % MO;  // < MO
      }
      prod *= INV_FFT_RATIOS[__builtin_ctz(++h)];
    }
  }
  if (m < n) {
    for (int i = 0; i < m; ++i) {
      const unsigned y = as[i].x + MO2 - as[i + m].x;  // < 4 MO
      as[i].x += as[i + m].x;  // < 4 MO
      as[i + m].x = y;  // < 4 MO
    }
  }
  const Mint invN = Mint(n).inv();
  for (int i = 0; i < n; ++i) {
    as[i] *= invN;
  }
}

void fft(vector<Mint> &as) {
  fft(as.data(), as.size());
}
void invFft(vector<Mint> &as) {
  invFft(as.data(), as.size());
}

vector<Mint> convolve(vector<Mint> as, vector<Mint> bs) {
  if (as.empty() || bs.empty()) return {};
  const int len = as.size() + bs.size() - 1;
  int n = 1;
  for (; n < len; n <<= 1) {}
  as.resize(n); fft(as);
  bs.resize(n); fft(bs);
  for (int i = 0; i < n; ++i) as[i] *= bs[i];
  invFft(as);
  as.resize(len);
  return as;
}
vector<Mint> square(vector<Mint> as) {
  if (as.empty()) return {};
  const int len = as.size() + as.size() - 1;
  int n = 1;
  for (; n < len; n <<= 1) {}
  as.resize(n); fft(as);
  for (int i = 0; i < n; ++i) as[i] *= as[i];
  invFft(as);
  as.resize(len);
  return as;
}
// m := |as|, n := |bs|
// cs[k] = \sum[i-j=k] as[i] bs[j]  (0 <= k <= m-n)
// transpose of ((multiply by bs): K^[0,m-n] -> K^[0,m-1])
vector<Mint> middle(vector<Mint> as, vector<Mint> bs) {
  const int m = as.size(), n = bs.size();
  assert(m >= n); assert(n >= 1);
  int len = 1;
  for (; len < m; len <<= 1) {}
  as.resize(len, 0);
  fft(as);
  std::reverse(bs.begin(), bs.end());
  bs.resize(len, 0);
  fft(bs);
  for (int i = 0; i < len; ++i) as[i] *= bs[i];
  invFft(as);
  as.resize(m);
  as.erase(as.begin(), as.begin() + (n - 1));
  return as;
}
////////////////////////////////////////////////////////////////////////////////


using Poly = vector<Mint>;

// ~ (N log(N))^(1/2)
#ifdef LOCAL
constexpr int K = 2;
#else
constexpr int K = 1000;
#endif

int N, Q;
vector<Poly> C;
vector<int> A, B;

vector<vector<int>> graph;

/*
  (product below u) = F[u] G[u]
  deg(G[u]) < K
*/
vector<Poly *> F, G;

Poly ID{1};
Poly *mul(Poly *as, Poly *bs) {
  if (as->size() == 1 && *as == ID) return bs;
  if (bs->size() == 1 && *bs == ID) return as;
  auto cs = new Poly;
  *cs = convolve(*as, *bs);
  return cs;
}

void dfs(int u, int p) {
  F[u] = &ID;
  G[u] = &C[u];
  if ((int)G[u]->size() > K) {
    swap(F[u], G[u]);
  }
  for (const int v : graph[u]) if (p != v) {
    dfs(v, u);
    F[u] = mul(F[u], F[v]);
    G[u] = mul(G[u], G[v]);
    if ((int)G[u]->size() > K) {
      F[u] = mul(F[u], G[u]);
      G[u] = &ID;
    }
  }
cerr<<u<<": "<<*F[u]<<" "<<*G[u]<<endl;
}

int main() {
  for (; ~scanf("%d%d", &N, &Q); ) {
    C.resize(N);
    for (int u = 0; u < N; ++u) {
      int deg;
      scanf("%d", &deg);
      C[u].resize(deg + 1);
      for (int k = 0; k <= deg; ++k) {
        scanf("%u", &C[u][k].x);
      }
    }
    A.resize(N - 1);
    B.resize(N - 1);
    for (int i = 0; i < N - 1; ++i) {
      scanf("%d%d", &A[i], &B[i]);
      --A[i];
      --B[i];
    }
    
    graph.assign(N, {});
    for (int i = 0; i < N - 1; ++i) {
      graph[A[i]].push_back(B[i]);
      graph[B[i]].push_back(A[i]);
    }
    F.resize(N);
    G.resize(N);
    dfs(0, -1);
    
    set<Poly *> vis;
    for (int u = 0; u < N; ++u) {
      if (vis.insert(F[u]).second) {
        for (int i = 1; i < (int)F[u]->size(); ++i) {
          (*F[u])[i] += (*F[u])[i - 1];
        }
      }
    }
    
    int lastans = 0;
    for (; Q--; ) {
      int X, L, R;
      scanf("%d%d%d", &X, &L, &R);
      X ^= lastans;
      L ^= lastans;
      R ^= lastans;
// cerr<<COLOR("33")<<X<<" "<<L<<" "<<R<<COLOR()<<endl;
      --X;
assert(0<=X);assert(X<N);assert(L<=R);
      Mint ans = 0;
      for (int i = 0; i < (int)G[X]->size(); ++i) {
        int l = max(L - i, 0);
        int r = min(R - i, (int)F[X]->size() - 1);
        if (l <= r) {
          Mint f = (*F[X])[r];
          if (l) f -= (*F[X])[l - 1];
          ans += f * (*G[X])[i];
        }
      }
      printf("%u\n", ans.x);
      lastans = ans.x;
    }
  }
  return 0;
}

詳細信息

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 64ms
memory: 4756kb

input:

1977 200000
0 883734638
1 497045124 50605999
0 467033353
8 514303373 873913661 21585656 827572829 831599042 669912647 980444584 921677622 90967524
0 111009203
0 980468811
1 965285721 647475291
0 55665482
0 810210109
5 99482052 915734955 536563337 860629716 489661090 127640528
4 452261176 414532348 8...

output:

0
0
0
1462214
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
709010908
0
0
0
0
0
0
0
0
0
0
0
0
0
0
362560754
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
887205253
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
532388854
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 200000 numbers

Test #2:

score: 7
Accepted
time: 75ms
memory: 4824kb

input:

1969 200000
1 928278040 49291189
0 106316044
7 355985609 701602147 528629206 472008316 626845782 871506163 793475066 634852555
0 193911795
1 498772599 387035156
2 244940676 15788848 225049996
8 257966353 171785747 687353797 643745787 25069581 248781417 212047281 295151595 525248876
2 606862291 21936...

output:

0
0
702752596
0
0
0
564436252
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
539882987
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
421207407
0
0
0
0
0
...

result:

ok 200000 numbers

Test #3:

score: 7
Accepted
time: 104ms
memory: 4868kb

input:

2000 200000
0 230695610
4 400302240 129755410 740309716 633048240 594259574
2 261261651 610028309 279096898
0 306295327
1 411519353 880936332
4 458323735 111990362 693959473 50334178 49499787
0 451592459
1 114402580 931927324
4 639243873 254122580 669324541 571247271 275880979
0 440954066
1 43964805...

output:

0
0
801713754
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
807839363
0
845789441
0
0
0
0
0
0
0
0
180971215
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
791867965
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
514100741
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
995968989
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8782...

result:

ok 200000 numbers

Test #4:

score: 7
Accepted
time: 188ms
memory: 7448kb

input:

1978 200000
1 191987956 540466676
1 120742551 206257774
2 744430486 875250521 181042024
0 103091601
0 304724279
0 649017453
0 145685556
0 599144446
0 364188280
0 57833875
3 414338956 791946816 770890256 830048461
0 819249191
0 755199883
1 758814940 693449562
1 280052104 142092003
0 214207528
0 85521...

output:

0
0
0
0
0
0
0
0
0
0
0
0
574798441
0
0
551851346
0
0
0
0
0
0
298923018
0
0
0
0
0
706319639
0
0
932127532
0
0
0
0
506810290
0
0
375480684
0
0
0
0
0
575707276
0
769974190
0
0
0
0
0
0
0
0
0
255132253
234643792
0
436442475
0
0
0
0
0
0
770777820
0
0
0
0
382421721
0
0
10702740
0
0
912641116
0
679541132
0
0...

result:

ok 200000 numbers

Test #5:

score: 7
Accepted
time: 81ms
memory: 4856kb

input:

1997 200000
1 609381747 833571580
1 102342468 526127035
1 880931004 909374728
2 103826707 729151512 34293902
1 273372046 293953096
0 554926428
0 676458000
1 401799287 357803550
1 695810053 794616522
0 748711966
1 967175820 34877055
2 257806263 264285746 818013686
1 576641758 75701100
0 795476926
0 7...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
996352329
0
0
0
0
61024835
0
0
424430639
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
392760029
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
442026045...

result:

ok 200000 numbers

Subtask #2:

score: 3
Accepted

Test #6:

score: 3
Accepted
time: 323ms
memory: 23192kb

input:

98154 200000
0 948053956
0 149079029
0 871940052
0 888807640
0 284687863
0 760258916
0 916765457
0 121680504
0 210430381
0 162441114
0 640680402
0 269559148
0 706423649
0 619089994
0 776236890
0 44769489
0 863235377
0 283984837
0 251593760
0 863377054
0 40488948
0 100272768
0 628132233
0 18841959
0 ...

output:

0
160622568
939846745
221659137
0
312930382
620657950
975124531
0
241389446
233242086
656904774
0
666641212
127400637
0
0
61866892
388266897
17714856
158666308
181172732
0
231863345
0
0
993493871
0
945624744
0
53582097
0
553931157
940627115
0
864491900
0
0
910285591
0
0
0
0
810021023
0
957355731
870...

result:

ok 200000 numbers

Test #7:

score: 3
Accepted
time: 299ms
memory: 23056kb

input:

98566 200000
0 209181684
0 889317979
0 925862494
0 861680823
0 629292192
0 781545895
0 58892045
0 300501945
0 510137985
0 764792857
0 551445762
0 771899874
0 828696971
0 260462870
0 535761660
0 532161459
0 187099
0 691412616
0 891055462
0 283180276
0 446617517
0 928434806
0 974119517
0 895921491
0 8...

output:

0
541915644
0
0
0
344789573
37160095
0
0
378148422
0
27407348
0
510146116
0
0
593724632
308323897
0
208041958
834526238
308130263
413718362
0
0
452600858
215844992
0
0
138748183
0
597752749
0
0
0
131857104
0
0
583969453
644145934
277456647
0
730806159
210434799
329144450
0
271266199
0
0
532721033
33...

result:

ok 200000 numbers

Subtask #3:

score: 0
Time Limit Exceeded

Test #8:

score: 0
Time Limit Exceeded

input:

97330 200000
2 356080749 854511831 888131963
0 533633039
0 260190631
0 217335008
2 998111375 903316988 891866314
0 507509609
0 556810297
1 190927168 988903728
1 270553180 387224380
0 360295480
0 775464651
0 755424805
0 71030175
0 690904984
0 702271750
0 360541906
0 903384679
0 769283169
0 6990072
0 ...

output:


result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #13:

score: 20
Accepted
time: 1075ms
memory: 38728kb

input:

50000 50000
1 610345459 691411093
1 476654936 529767753
1 8856530 640833948
1 961473497 456987897
1 462733802 114971681
1 662244461 415955667
1 717992437 907944693
1 346097988 176526535
1 805826501 182409272
1 33105050 971783530
1 45972429 258997374
1 964103067 796756441
1 958668755 735146502
1 9543...

output:

0
0
0
0
0
0
0
610268301
297428232
729194415
0
0
506964543
0
198345028
778136423
0
89695571
651093422
174709
799469987
0
0
0
0
374762615
64155221
0
644085102
355318236
625240586
0
0
0
0
611217681
0
246858712
0
946363040
766457000
0
0
0
0
0
0
0
885388926
324657374
0
0
608041499
0
0
0
595311003
0
0
790...

result:

ok 50000 numbers

Test #14:

score: 0
Time Limit Exceeded

input:

50000 50000
1 284188823 730123812
1 578529655 782975708
1 682107201 169640319
1 504919829 297067490
1 126340369 681480864
1 702290552 331608873
1 89823300 900339069
1 661791786 696739097
1 146107507 457302386
1 309885170 133384173
1 1601509 445278250
1 82308245 611577805
1 575317 145972663
1 3340187...

output:


result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #21:

score: 20
Accepted
time: 488ms
memory: 18368kb

input:

19854 20000
1 150513542 240180212
0 987796281
0 90054116
1 191708494 438440429
0 192815969
0 867402303
1 531762469 210966860
2 95662022 345368425 199338548
0 269135053
0 816253511
0 66854944
0 319745952
0 202288549
0 492853777
0 410846691
0 824737426
0 821545014
0 72050044
0 534080091
1 542636124 52...

output:

913323334
0
0
0
0
0
0
0
0
0
0
0
901017606
0
0
0
0
0
954099396
0
0
432419999
0
0
0
0
0
0
0
761082946
259729654
0
0
0
0
790235355
933098570
356668385
125624181
0
0
0
0
917034405
0
321407524
0
671256345
39032345
0
0
676929142
0
0
0
0
0
0
0
0
910494481
0
0
0
733125978
0
0
835461650
0
154343024
690428959...

result:

ok 20000 numbers

Test #22:

score: 20
Accepted
time: 424ms
memory: 15988kb

input:

19416 20000
1 813812350 62928444
2 446931520 455152410 865811291
1 483245225 719509880
0 10630578
1 722267364 499990463
0 978295677
0 524126644
2 398577038 701788899 939255653
0 945953310
0 358029034
1 54632159 541649711
0 714215963
0 760637762
1 792667329 540131052
1 336329275 197811762
0 594815129...

output:

0
0
0
0
0
0
0
0
691960524
0
0
0
0
0
0
0
0
0
0
917519575
0
0
0
0
457906160
686627668
0
263875204
0
0
0
860458574
0
0
197732443
0
0
0
0
0
0
0
0
0
0
0
0
0
619069496
0
0
145464796
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
409777622
309523189
862407937
0
0
954411456
0
0
0
0
0
0
304719397
0
548777971
176155...

result:

ok 20000 numbers

Test #23:

score: 20
Accepted
time: 400ms
memory: 16288kb

input:

19645 20000
1 738216072 655062389
0 478261419
28 38522218 205802590 608351714 423733656 368037127 943951223 529243126 691493532 378826276 32699256 849862664 799709335 113704178 671006657 736000878 683394539 338518052 850384023 536423162 225738416 276528868 965415989 455460104 274736758 547583027 423...

output:

0
710035374
349663621
61124181
0
0
0
0
0
0
0
0
0
0
0
0
0
0
694466943
0
0
0
0
103025366
0
0
108158012
0
0
898653012
0
0
0
0
124734988
0
628306562
0
0
0
0
0
829055370
0
942321667
0
0
0
0
100614270
0
666765805
277413825
0
0
0
0
492192785
0
0
0
0
517011159
0
0
0
0
172598073
0
258513717
233404540
8590182...

result:

ok 20000 numbers

Test #24:

score: 20
Accepted
time: 400ms
memory: 15516kb

input:

19847 20000
4 815026590 930615671 256423615 192058090 553677398
0 854407447
3 121205405 14847480 141687199 287623506
2 379798536 291209656 593839232
1 352031200 841240984
0 295186159
0 841042115
0 679392127
0 420742492
2 891756622 260075296 417909411
0 645458804
0 681889229
0 29119165
0 99142741
3 7...

output:

470171472
213398321
0
0
55462715
0
338144412
0
0
0
0
0
0
0
698725184
0
0
0
0
47366191
0
317326831
0
0
0
239746199
214366720
0
0
0
0
0
279091720
0
86836316
0
0
0
35432299
0
308555884
0
319326811
0
0
0
305535605
0
358646410
0
0
131375996
0
0
0
0
0
0
0
0
570823027
0
0
80022023
0
954809219
0
0
0
0
26917...

result:

ok 20000 numbers

Test #25:

score: 20
Accepted
time: 380ms
memory: 16240kb

input:

19990 20000
3 575964327 889968526 762346953 464212918
0 91433877
0 762285092
1 703259059 61874142
2 130773960 696187633 280576635
1 163442506 294293968
0 134582456
0 525908094
2 981613234 494831823 871173319
0 320232487
0 951459253
0 725136632
2 48590419 631199232 992008959
1 860836891 867326137
1 6...

output:

90336621
0
741001438
326700634
0
0
0
0
0
0
925215064
0
0
863889195
0
0
0
0
0
576304546
0
0
0
0
583889751
0
0
0
0
0
0
813389361
0
0
0
0
0
0
0
108311310
0
0
653689603
0
0
0
91295650
0
347062400
0
0
0
0
620038417
846141331
99345412
0
581988923
0
0
0
0
365053652
29464872
917029396
788177507
288943414
0
...

result:

ok 20000 numbers

Test #26:

score: 20
Accepted
time: 448ms
memory: 16200kb

input:

19302 20000
1 140879209 815790450
0 263312184
2 357492390 407721624 927753023
17 329030216 687250506 904721674 66559073 150996400 582272412 140464848 806623151 989399143 916248414 596527559 964780629 802988469 182625819 764316767 594475067 203564894 275476377
0 547777698
0 34169169
0 93303556
0 5807...

output:

0
0
132910965
0
127962650
0
453633700
0
0
451482843
0
0
0
388743057
0
0
293560154
874329518
0
0
0
0
0
0
0
0
0
0
766081674
0
0
234642116
0
0
669563153
0
748448386
0
0
0
0
0
0
0
0
0
670410122
87350607
0
416323263
174794844
0
0
0
0
0
0
196859095
0
0
0
0
644332981
0
0
0
0
0
0
0
0
0
469599960
0
0
0
0
931...

result:

ok 20000 numbers

Test #27:

score: 20
Accepted
time: 456ms
memory: 18764kb

input:

19653 20000
1 906614788 500628713
0 988012762
0 284902421
0 704468047
0 872560811
1 907887753 600402772
0 767950811
0 118754288
0 290736011
0 217729487
1 190172852 683598286
0 723859834
0 220112811
0 448174595
0 39653265
0 770732977
0 458450918
0 438730398
0 183195813
0 191514564
0 2928127
0 3007322...

output:

0
244727120
0
0
132988676
354295625
0
667761790
0
0
0
0
0
822615931
0
0
0
0
0
0
504618092
0
973780962
0
0
0
0
737475269
0
0
0
383245743
0
0
10261578
551768502
0
835642191
0
0
69015099
0
0
773914454
0
0
0
0
0
193232063
0
0
0
0
0
230203189
0
0
0
0
0
0
0
0
120778708
0
949822563
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 20000 numbers

Test #28:

score: 20
Accepted
time: 332ms
memory: 15592kb

input:

19072 20000
0 910136763
1 809343877 577693489
0 805540439
0 728993500
0 234081004
1 891104112 210354669
0 262384318
0 568913493
0 376708574
1 145377149 421745582
0 108964429
0 697119989
0 615671424
0 697025092
0 222804661
0 927317484
1 66775292 771115618
0 405877157
1 977355316 502648356
1 218406564...

output:

0
0
0
558272462
0
0
0
0
0
0
0
328733917
446478844
0
0
0
0
0
0
848724549
0
0
980511070
0
0
597411269
0
127279175
0
0
0
0
0
739852501
0
0
0
0
0
0
568449517
589452941
0
0
0
0
791777304
0
0
0
0
114744131
322763812
613885875
52417149
0
0
0
0
149449664
0
0
644257795
0
725958460
276312482
499158209
8075964...

result:

ok 20000 numbers

Test #29:

score: 0
Time Limit Exceeded

input:

20000 20000
0 614936162
0 182986322
0 40697275
0 824161988
0 240412566
0 287310162
0 63000758
0 958628891
0 139827408
0 971860786
0 325782161
0 726800064
0 392930207
0 911604309
0 904980384
0 508941069
0 641836609
0 759719860
0 732767740
0 94630498
0 390558752
0 764408563
0 40013248
0 414628626
0 87...

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%