QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#76544#5360. Wechatalpha1022100 ✓47ms18836kbC++179.6kb2023-02-10 17:04:242023-02-10 17:04:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-10 17:04:26]
  • 评测
  • 测评结果:100
  • 用时:47ms
  • 内存:18836kb
  • [2023-02-10 17:04:24]
  • 提交

answer

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

#define add(a, b) (a + b >= mod ? a + b - mod : a + b)
#define dec(a, b) (a < b ? a - b + mod : a - b)
using namespace std;
const int N = 2e5;
const int mod = 998244353;
int n;
int ans[N + 5];
inline int fpow(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1) (b & 1) && (ret = (long long)ret * a % mod), a = (long long)a * a % mod;
  return ret;
}
namespace Poly {
  const int LG = 18;
  const int N = 1 << LG + 1;
  const int G = 3;
  int lg2[N + 5];
  int rev[N + 5], fac[N + 5], ifac[N + 5], inv[N + 5];
  int rt[N + 5];
  inline void init() {
    for (int i = 2; i <= N; ++i) lg2[i] = lg2[i >> 1] + 1;
    rt[0] = 1, rt[1 << LG] = fpow(G, (mod - 1) >> LG + 2);
    for (int i = LG; i; --i) rt[1 << i - 1] = (long long)rt[1 << i] * rt[1 << i] % mod;
    for (int i = 1; i < N; ++i) rt[i] = (long long)rt[i & i - 1] * rt[i & -i] % mod;
    fac[0] = 1;
    for (int i = 1; i <= N; ++i) fac[i] = (long long)fac[i - 1] * i % mod;
    ifac[N] = fpow(fac[N], mod - 2);
    for (int i = N; i; --i) ifac[i - 1] = (long long)ifac[i] * i % mod;
    for (int i = 1; i <= N; ++i) inv[i] = (long long)ifac[i] * fac[i - 1] % mod;
  }
  struct poly {
    vector<int> a;
    inline poly(int x = 0) { x && (a.push_back(x), 1); }
    inline poly(const vector<int> &o) { a = o, shrink(); }
    inline poly(const poly &o) { a = o.a, shrink(); }
    inline void shrink() {
      for (; !a.empty() && !a.back(); a.pop_back())
        ;
    }
    inline int size() const { return a.size(); }
    inline void resize(int x) { a.resize(x); }
    inline int operator[](int x) const {
      if (x < 0 || x >= size()) return 0;
      return a[x];
    }
    inline void clear() { vector<int>().swap(a); }
    inline poly rever() const { return poly(vector<int>(a.rbegin(), a.rend())); }
    inline void dif() {
      int n = size();
      for (int i = 0, len = n >> 1; len; ++i, len >>= 1)
        for (int j = 0, *w = rt; j < n; j += len << 1, ++w)
          for (int k = j, R; k < j + len; ++k)
            R = (long long)*w * a[k + len] % mod, a[k + len] = dec(a[k], R), a[k] = add(a[k], R);
    }
    inline void dit() {
      int n = size();
      for (int i = 0, len = 1; len < n; ++i, len <<= 1)
        for (int j = 0, *w = rt; j < n; j += len << 1, ++w)
          for (int k = j, R; k < j + len; ++k)
            R = add(a[k], a[k + len]), a[k + len] = (long long)(a[k] - a[k + len] + mod) * *w % mod, a[k] = R;
      reverse(a.begin() + 1, a.end());
      for (int i = 0; i < n; ++i) a[i] = (long long)a[i] * inv[n] % mod;
    }
    inline void ntt(int type = 1) { type == 1 ? dif() : dit(); }
    friend inline poly operator+(const poly &a, const poly &b) {
      vector<int> ret(max(a.size(), b.size()));
      for (int i = 0; i < ret.size(); ++i) ret[i] = add(a[i], b[i]);
      return poly(ret);
    }
    friend inline poly operator-(const poly &a, const poly &b) {
      vector<int> ret(max(a.size(), b.size()));
      for (int i = 0; i < ret.size(); ++i) ret[i] = dec(a[i], b[i]);
      return poly(ret);
    }
    friend inline poly operator*(poly a, poly b) {
      if (a.a.empty() || b.a.empty()) return poly();
      if (a.size() < 40 || b.size() < 40) {
        if (a.size() > b.size()) swap(a, b);
        poly ret;
        ret.resize(a.size() + b.size() - 1);
        for (int i = 0; i < ret.size(); ++i)
          for (int j = 0; j <= i && j < a.size(); ++j) ret.a[i] = (ret[i] + (long long)a[j] * b[i - j]) % mod;
        ret.shrink();
        return ret;
      }
      int lim = 1, tot = a.size() + b.size() - 1;
      for (; lim < tot; lim <<= 1)
        ;
      a.resize(lim), b.resize(lim);
      a.ntt(), b.ntt();
      for (int i = 0; i < lim; ++i) a.a[i] = (long long)a[i] * b[i] % mod;
      a.ntt(-1), a.shrink();
      return a;
    }
    poly &operator+=(const poly &o) {
      resize(max(size(), o.size()));
      for (int i = 0; i < o.size(); ++i) a[i] = add(a[i], o[i]);
      return *this;
    }
    poly &operator-=(const poly &o) {
      resize(max(size(), o.size()));
      for (int i = 0; i < o.size(); ++i) a[i] = dec(a[i], o[i]);
      return *this;
    }
    poly &operator*=(poly o) { return (*this) = (*this) * o; }
    poly deriv() const {
      if (a.empty()) return poly();
      vector<int> ret(size() - 1);
      for (int i = 0; i < size() - 1; ++i) ret[i] = (long long)(i + 1) * a[i + 1] % mod;
      return poly(ret);
    }
    poly integ() const {
      if (a.empty()) return poly();
      vector<int> ret(size() + 1);
      for (int i = 0; i < size(); ++i) ret[i + 1] = (long long)a[i] * inv[i + 1] % mod;
      return poly(ret);
    }
    inline poly modxn(int n) const {
      if (a.empty()) return poly();
      n = min(n, size());
      return poly(vector<int>(a.begin(), a.begin() + n));
    }
    inline poly inver(int m) const {
      poly ret(fpow(a[0], mod - 2)), f, g;
      for (int k = 1; k < m;) {
        k <<= 1, f.resize(k), g.resize(k);
        for (int i = 0; i < k; ++i) f.a[i] = (*this)[i], g.a[i] = ret[i];
        f.ntt(), g.ntt();
        for (int i = 0; i < k; ++i) f.a[i] = (long long)f[i] * g[i] % mod;
        f.ntt(-1);
        for (int i = 0; i < (k >> 1); ++i) f.a[i] = 0;
        f.ntt();
        for (int i = 0; i < k; ++i) f.a[i] = (long long)f[i] * g[i] % mod;
        f.ntt(-1);
        ret.resize(k);
        for (int i = (k >> 1); i < k; ++i) ret.a[i] = dec(0, f[i]);
      }
      return ret.modxn(m);
    }
    inline pair<poly, poly> div(poly o) const {
      if (size() < o.size()) return make_pair(poly(), *this);
      poly f, g;
      f = (rever().modxn(size() - o.size() + 1) * o.rever().inver(size() - o.size() + 1))
          .modxn(size() - o.size() + 1)
          .rever();
      g = (modxn(o.size() - 1) - o.modxn(o.size() - 1) * f.modxn(o.size() - 1)).modxn(o.size() - 1);
      return make_pair(f, g);
    }
    inline poly log(int m) const { return (deriv() * inver(m)).integ().modxn(m); }
    inline poly exp(int m) const {
      poly ret(1), iv, it, d = deriv(), itd, itd0, t1;
      if (m < 70) {
        ret.resize(m);
        for (int i = 1; i < m; ++i) {
          for (int j = 1; j <= i; ++j)
            ret.a[i] = (ret[i] + (long long)j * operator[](j) % mod * ret[i - j]) % mod;
          ret.a[i] = (long long)ret[i] * inv[i] % mod;
        }
        return ret;
      }
      for (int k = 1; k < m;) {
        k <<= 1;
        it.resize(k >> 1);
        for (int i = 0; i < (k >> 1); ++i) it.a[i] = ret[i];
        itd = it.deriv(), itd.resize(k >> 1);
        iv = ret.inver(k >> 1), iv.resize(k >> 1);
        it.ntt(), itd.ntt(), iv.ntt();
        for (int i = 0; i < (k >> 1); ++i)
          it.a[i] = (long long)it[i] * iv[i] % mod, itd.a[i] = (long long)itd[i] * iv[i] % mod;
        it.ntt(-1), itd.ntt(-1), it.a[0] = dec(it[0], 1);
        for (int i = 0; i < k - 1; ++i) itd.a[i % (k >> 1)] = dec(itd[i % (k >> 1)], d[i]);
        itd0.resize((k >> 1) - 1);
        for (int i = 0; i < (k >> 1) - 1; ++i) itd0.a[i] = d[i];
        itd0 = (itd0 * it).modxn((k >> 1) - 1);
        t1.resize(k - 1);
        for (int i = (k >> 1) - 1; i < k - 1; ++i) t1.a[i] = itd[(i + (k >> 1)) % (k >> 1)];
        for (int i = k >> 1; i < k - 1; ++i) t1.a[i] = dec(t1[i], itd0[i - (k >> 1)]);
        t1 = t1.integ();
        for (int i = 0; i < (k >> 1); ++i) t1.a[i] = t1[i + (k >> 1)];
        for (int i = (k >> 1); i < k; ++i) t1.a[i] = 0;
        t1.resize(k >> 1), t1 = (t1 * ret).modxn(k >> 1), t1.resize(k);
        for (int i = (k >> 1); i < k; ++i) t1.a[i] = t1[i - (k >> 1)];
        for (int i = 0; i < (k >> 1); ++i) t1.a[i] = 0;
        ret -= t1;
      }
      return ret.modxn(m);
    }
    inline poly sqrt(int m) const {
      poly ret(1), f, g;
      for (int k = 1; k < m;) {
        k <<= 1;
        f = ret, f.resize(k >> 1);
        f.ntt();
        for (int i = 0; i < (k >> 1); ++i) f.a[i] = (long long)f[i] * f[i] % mod;
        f.ntt(-1);
        for (int i = 0; i < k; ++i) f.a[i % (k >> 1)] = dec(f[i % (k >> 1)], (*this)[i]);
        g = (2 * ret).inver(k >> 1), f = (f * g).modxn(k >> 1), f.resize(k);
        for (int i = (k >> 1); i < k; ++i) f.a[i] = f[i - (k >> 1)];
        for (int i = 0; i < (k >> 1); ++i) f.a[i] = 0;
        ret -= f;
      }
      return ret.modxn(m);
    }
    inline poly pow(int m, int k1, int k2 = -1) const {
      if (a.empty()) return poly();
      if (k2 == -1) k2 = k1;
      int t = 0;
      for (; t < size() && !a[t]; ++t)
        ;
      if ((long long)t * k1 >= m) return poly();
      poly ret;
      ret.resize(m);
      int u = fpow(a[t], mod - 2), v = fpow(a[t], k2);
      for (int i = 0; i < m - t * k1; ++i) ret.a[i] = (long long)operator[](i + t) * u % mod;
      ret = ret.log(m - t * k1);
      for (int i = 0; i < ret.size(); ++i) ret.a[i] = (long long)ret[i] * k1 % mod;
      ret = ret.exp(m - t * k1), t *= k1, ret.resize(m);
      for (int i = m - 1; i >= t; --i) ret.a[i] = (long long)ret[i - t] * v % mod;
      for (int i = 0; i < t; ++i) ret.a[i] = 0;
      return ret;
    }
  };
}
using Poly::init;
using Poly::poly;
inline int C(int n, int m) {
  return n < m ? 0 : (long long)Poly::fac[n] * Poly::ifac[m] % mod * Poly::ifac[n - m] % mod;
}
poly f, g;
int main() {
  init();
  scanf("%d", &n), f.resize(n + 1), g.resize(n + 1);
  for (int i = 0; i <= n; ++i)
    f.a[i] = (long long)(i & 1 ? mod - 1 : 1) * Poly::ifac[i] % mod * Poly::ifac[n - i] % mod,
    i && (g.a[i] = (fpow(i, n) - fpow(dec(i, 1), n) + mod) % mod);
  f *= g;
  for (int i = 0; i <= n; ++i) ans[i] = f[n - i];
  for (int i = 0; i < n; ++i) printf("%d%c", ans[i], " \n"[i + 1 == n]);
}

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

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 6ms
memory: 14680kb

input:

10

output:

370705776 185074360 753392795 76402225 111791374 111791374 76402225 753392795 185074360 370705776

result:

ok single line: '370705776 185074360 753392795 ...5 753392795 185074360 370705776'

Test #2:

score: 0
Accepted
time: 10ms
memory: 14892kb

input:

2

output:

499122177 499122177

result:

ok single line: '499122177 499122177'

Test #3:

score: 0
Accepted
time: 13ms
memory: 14928kb

input:

5

output:

856826403 316110712 648858830 316110712 856826403

result:

ok single line: '856826403 316110712 648858830 316110712 856826403'

Test #4:

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

input:

7

output:

376916469 308980395 695800082 231339168 695800082 308980395 376916469

result:

ok single line: '376916469 308980395 695800082 ...8 695800082 308980395 376916469'

Test #5:

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

input:

6

output:

641926577 653018181 202421772 202421772 653018181 641926577

result:

ok single line: '641926577 653018181 202421772 202421772 653018181 641926577'

Test #6:

score: 0
Accepted
time: 6ms
memory: 14504kb

input:

9

output:

712324701 215521528 938340889 794958801 667174281 794958801 938340889 215521528 712324701

result:

ok single line: '712324701 215521528 938340889 ...1 938340889 215521528 712324701'

Test #7:

score: 0
Accepted
time: 13ms
memory: 14452kb

input:

8

output:

421456191 282266465 492660327 300983547 300983547 492660327 282266465 421456191

result:

ok single line: '421456191 282266465 492660327 ...7 492660327 282266465 421456191'

Test #8:

score: 0
Accepted
time: 4ms
memory: 15052kb

input:

4

output:

291154603 207967574 207967574 291154603

result:

ok single line: '291154603 207967574 207967574 291154603'

Test #9:

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

input:

1

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 6ms
memory: 15064kb

input:

3

output:

166374059 665496236 166374059

result:

ok single line: '166374059 665496236 166374059'

Test #11:

score: 0
Accepted
time: 8ms
memory: 14792kb

input:

10

output:

370705776 185074360 753392795 76402225 111791374 111791374 76402225 753392795 185074360 370705776

result:

ok single line: '370705776 185074360 753392795 ...5 753392795 185074360 370705776'

Test #12:

score: 0
Accepted
time: 13ms
memory: 14908kb

input:

3

output:

166374059 665496236 166374059

result:

ok single line: '166374059 665496236 166374059'

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #13:

score: 10
Accepted
time: 3ms
memory: 14108kb

input:

11

output:

305948985 7657188 266145752 575704660 8684372 666451146 8684372 575704660 266145752 7657188 305948985

result:

ok single line: '305948985 7657188 266145752 57...660 266145752 7657188 305948985'

Test #14:

score: 0
Accepted
time: 6ms
memory: 14768kb

input:

18

output:

632701444 545689786 710182147 727541362 435434070 313843467 358466078 11785936 756455299 756455299 11785936 358466078 313843467 435434070 727541362 710182147 545689786 632701444

result:

ok single line: '632701444 545689786 710182147 ...2 710182147 545689786 632701444'

Test #15:

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

input:

13

output:

405098354 719575758 811926740 432515302 496842318 548123862 159545804 548123862 496842318 432515302 811926740 719575758 405098354

result:

ok single line: '405098354 719575758 811926740 ...2 811926740 719575758 405098354'

Test #16:

score: 0
Accepted
time: 4ms
memory: 14076kb

input:

17

output:

407938109 944611971 221406723 696733300 614953765 441000871 450981094 654224793 120497926 654224793 450981094 441000871 614953765 696733300 221406723 944611971 407938109

result:

ok single line: '407938109 944611971 221406723 ...0 221406723 944611971 407938109'

Test #17:

score: 0
Accepted
time: 6ms
memory: 14668kb

input:

12

output:

275056837 32168346 72917428 724258985 387421595 5543339 5543339 387421595 724258985 72917428 32168346 275056837

result:

ok single line: '275056837 32168346 72917428 72...985 72917428 32168346 275056837'

Test #18:

score: 0
Accepted
time: 7ms
memory: 13704kb

input:

20

output:

400962745 916930465 951792334 116787831 195281508 54269614 680671584 315338837 810135295 49929376 49929376 810135295 315338837 680671584 54269614 195281508 116787831 951792334 916930465 400962745

result:

ok single line: '400962745 916930465 951792334 ...1 951792334 916930465 400962745'

Test #19:

score: 0
Accepted
time: 12ms
memory: 13796kb

input:

16

output:

945481735 964470050 425265259 973565942 957113446 167145870 832582004 224719636 224719636 832582004 167145870 957113446 973565942 425265259 964470050 945481735

result:

ok single line: '945481735 964470050 425265259 ...2 425265259 964470050 945481735'

Test #20:

score: 0
Accepted
time: 4ms
memory: 14124kb

input:

19

output:

33300076 866999104 810539485 383440491 951658555 630111326 399340630 388979657 837996956 375955324 837996956 388979657 399340630 630111326 951658555 383440491 810539485 866999104 33300076

result:

ok single line: '33300076 866999104 810539485 3...91 810539485 866999104 33300076'

Test #21:

score: 0
Accepted
time: 12ms
memory: 14080kb

input:

15

output:

154042465 71853618 269023909 274764093 406840498 365344309 240273450 428692729 240273450 365344309 406840498 274764093 269023909 71853618 154042465

result:

ok single line: '154042465 71853618 269023909 2...93 269023909 71853618 154042465'

Test #22:

score: 0
Accepted
time: 4ms
memory: 13956kb

input:

14

output:

314148269 336352958 220338178 618911903 58564178 982127868 963411882 963411882 982127868 58564178 618911903 220338178 336352958 314148269

result:

ok single line: '314148269 336352958 220338178 ...3 220338178 336352958 314148269'

Subtask #3:

score: 30
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #23:

score: 30
Accepted
time: 2ms
memory: 15008kb

input:

391

output:

244221084 462367559 854862595 841472721 690246739 83771737 924329255 478345073 729894818 460609665 41606976 699889517 212113631 652522304 975090138 627034027 822474609 254498004 490736459 197092102 576215532 341953753 289088560 891647518 381078724 692847041 288640094 147654923 560158390 390667832 14...

result:

ok single line: '244221084 462367559 854862595 ...1 854862595 462367559 244221084'

Test #24:

score: 0
Accepted
time: 8ms
memory: 14348kb

input:

289

output:

597246155 765887063 323979926 793275057 110080138 450653399 760534726 90902529 303169476 710341256 535369449 386081260 403596932 254735085 97325223 738538044 608483475 806780825 357313153 412136953 978389808 765537443 84037148 778654869 160852006 116039443 500067942 861225613 58057908 333267671 7951...

result:

ok single line: '597246155 765887063 323979926 ...7 323979926 765887063 597246155'

Test #25:

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

input:

301

output:

357822007 588512722 494253000 758101551 183558651 517908055 400338007 834922992 520765024 33667199 561750270 829008342 91752321 701998476 251281440 872499488 138066960 89677725 492475136 350352380 232232761 679149703 340594535 111434472 987156478 129003752 567371003 96539881 33405678 864524074 34284...

result:

ok single line: '357822007 588512722 494253000 ...1 494253000 588512722 357822007'

Test #26:

score: 0
Accepted
time: 10ms
memory: 14460kb

input:

267

output:

870996215 155652031 50398826 920885624 115982762 33554413 353386753 814471092 9914995 335233879 108025683 745377708 234734730 59809661 595630006 692191361 447816595 500047898 242003635 973645203 719351176 886875485 820107403 791177173 812405452 472174491 46939493 173189480 177679433 83412222 1854253...

result:

ok single line: '870996215 155652031 50398826 9...24 50398826 155652031 870996215'

Test #27:

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

input:

284

output:

672803212 133397067 430416913 888121906 432891762 353088797 731691498 840997531 832864531 229297816 305049451 772174672 614460520 503109285 354775797 782240336 374591232 448678870 285985940 601686715 469382569 296097132 208860518 492910851 984839115 64378688 736915790 997628442 416119467 538913704 9...

result:

ok single line: '672803212 133397067 430416913 ...6 430416913 133397067 672803212'

Test #28:

score: 0
Accepted
time: 4ms
memory: 14804kb

input:

347

output:

976432122 274804894 976234305 213429102 621345073 347368113 154427669 580974962 69964977 17788835 205098670 644503624 511671215 236847291 316426669 449437331 409006563 100248382 204090982 864083508 458741281 821569259 16812425 572343702 427654447 634357364 6118575 695159837 192409191 585265033 25312...

result:

ok single line: '976432122 274804894 976234305 ...2 976234305 274804894 976432122'

Test #29:

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

input:

315

output:

829576888 784511769 144814788 379533090 773276409 243904875 458846018 468902905 296635015 726215468 693003696 846915125 6863461 507282967 491644010 204241242 342457099 707413965 100303141 269902278 166370352 462712338 423836430 972905884 342045166 686900246 880507176 671577121 1683845 894754474 4126...

result:

ok single line: '829576888 784511769 144814788 ...0 144814788 784511769 829576888'

Test #30:

score: 0
Accepted
time: 4ms
memory: 14400kb

input:

360

output:

378027545 956527777 194490726 302991027 792415085 221040381 534507595 344179216 107612229 337699229 122296329 135784461 869934582 122137429 62247960 740309068 654282637 98799013 235923932 961984894 507635129 23702761 815364323 294163647 90989276 764980540 451334636 742565849 772922259 68183239 97483...

result:

ok single line: '378027545 956527777 194490726 ...7 194490726 956527777 378027545'

Test #31:

score: 0
Accepted
time: 8ms
memory: 15124kb

input:

344

output:

68480856 318029229 96840163 601072415 252061144 494261172 391088265 812976389 691433761 383425467 328905432 380036509 148209911 57212653 404466005 224922470 507082022 402929981 346633429 861970459 279768677 578393108 13706145 806935510 720061013 167305674 323765018 591208088 619676317 351388218 5624...

result:

ok single line: '68480856 318029229 96840163 60...415 96840163 318029229 68480856'

Test #32:

score: 0
Accepted
time: 6ms
memory: 14220kb

input:

388

output:

769467691 885267646 438119451 413744330 599781950 855012539 483198781 959013653 131926354 494861967 556366104 726788588 443907934 583302691 284664189 978648522 151571744 198714740 275817394 120692462 177804077 439611640 272612346 995012030 981352259 719739329 272578739 203585036 889195169 276949988 ...

result:

ok single line: '769467691 885267646 438119451 ...0 438119451 885267646 769467691'

Subtask #4:

score: 10
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #33:

score: 10
Accepted
time: 4ms
memory: 14176kb

input:

1908

output:

322711429 615857075 639856889 514779266 309256778 6308978 990003447 907175673 637024766 661452682 252747286 4605897 762441479 63091807 819138152 365488865 303025724 546528661 89470964 633326592 22322172 219039376 17006750 832082186 807933199 44145749 351129464 877816910 997343732 860000334 262856049...

result:

ok single line: '322711429 615857075 639856889 ...6 639856889 615857075 322711429'

Test #34:

score: 0
Accepted
time: 12ms
memory: 13920kb

input:

1990

output:

691868170 360337790 904487819 955442888 281704538 80981764 927275803 144446074 215547145 73161319 922186358 477105317 875783900 191094387 109239088 279596801 745608228 162987339 89429142 37347542 865522470 263031870 162665111 195370037 682391802 652520705 668370321 96955963 285259167 994651720 71908...

result:

ok single line: '691868170 360337790 904487819 ...8 904487819 360337790 691868170'

Test #35:

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

input:

1142

output:

788022989 361099195 695551795 336439354 494901776 504329394 81822134 607292999 101462088 652396187 695692068 292097198 918875354 561875792 545695936 318644537 554874221 134341813 796422845 795956842 376077505 831592576 622564505 114700371 141942660 386833321 853030241 34637151 364562582 884428389 95...

result:

ok single line: '788022989 361099195 695551795 ...4 695551795 361099195 788022989'

Test #36:

score: 0
Accepted
time: 6ms
memory: 14128kb

input:

1704

output:

43809447 289819269 991137413 723317105 235209815 308714556 545605479 757296355 509683159 579787661 57389413 403503751 308331044 383094261 742453152 40279846 4013524 237779243 857108768 889007742 893911147 391733723 537850924 53737411 376993828 306559578 77647723 919793196 26071036 596299254 21567828...

result:

ok single line: '43809447 289819269 991137413 7...05 991137413 289819269 43809447'

Test #37:

score: 0
Accepted
time: 8ms
memory: 14728kb

input:

1575

output:

990895836 192935979 328351129 439961507 202034012 910492996 569364242 911366178 64712149 276608550 680794957 452950082 404122046 210834208 779498069 297841321 36375844 32307612 748970992 27752855 516772999 295134273 817308938 591943337 546599772 478963864 743573055 630862550 496268996 412537671 1648...

result:

ok single line: '990895836 192935979 328351129 ...7 328351129 192935979 990895836'

Test #38:

score: 0
Accepted
time: 8ms
memory: 14164kb

input:

1014

output:

633054181 97361414 865999590 631294754 668195149 250955468 179743684 217403290 961769378 979250408 941095660 345220208 438539737 557357338 667522489 736187030 488669580 918660721 618117583 375685997 702499946 449406196 223866104 850085109 130950544 146843358 573970062 648556028 444718561 343018048 2...

result:

ok single line: '633054181 97361414 865999590 6...54 865999590 97361414 633054181'

Test #39:

score: 0
Accepted
time: 13ms
memory: 14508kb

input:

1776

output:

230372150 357650664 578804887 955184938 525047781 557686125 581552414 734746351 815193917 201845030 993354167 275178784 104979965 923406319 180265108 263947983 137104237 82846388 48874605 60029636 712541889 374353166 371818708 303954894 973090012 766791710 744276674 682535121 663984411 534533359 972...

result:

ok single line: '230372150 357650664 578804887 ...8 578804887 357650664 230372150'

Test #40:

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

input:

1818

output:

37280461 81827530 922095166 867025219 193445074 46106337 573235636 750113306 237711028 615702979 405601540 978528788 991139385 441879869 472384751 990312347 230964722 48512550 86228924 58597021 953560180 249138422 154869430 339779879 933627026 405432497 701214457 547969338 770404396 381565531 433873...

result:

ok single line: '37280461 81827530 922095166 86...219 922095166 81827530 37280461'

Test #41:

score: 0
Accepted
time: 12ms
memory: 14124kb

input:

1154

output:

710797282 219052999 771814285 167421729 863744471 604382781 226770414 622270795 348333877 643135079 504585001 856893723 65567896 461183864 525616510 344078133 234255197 139116597 702645948 584225240 214538377 590355388 550145806 97019509 954038151 638225302 565490525 253614551 323758541 902103135 24...

result:

ok single line: '710797282 219052999 771814285 ...9 771814285 219052999 710797282'

Test #42:

score: 0
Accepted
time: 6ms
memory: 14316kb

input:

1213

output:

97066447 611500941 121998917 50828684 527545285 794722818 41498354 107777832 795162305 574520011 651578181 41707037 733691103 199223737 917825189 926033932 948530296 759741600 388184154 822298371 779724498 265080516 694714541 949332733 4072116 926379339 45032767 994688540 971909923 403181453 7743373...

result:

ok single line: '97066447 611500941 121998917 5...84 121998917 611500941 97066447'

Subtask #5:

score: 40
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #43:

score: 40
Accepted
time: 38ms
memory: 17216kb

input:

66461

output:

825716309 948282722 113618800 225616327 32683896 943990534 845176023 249891187 65811660 998173726 14991477 316065199 932693089 751491411 94054743 983557550 157116828 569321146 885799997 167196469 311295683 928843829 232587443 460269424 688373251 643387334 710284425 830788894 967212407 918129474 8360...

result:

ok single line: '825716309 948282722 113618800 ...7 113618800 948282722 825716309'

Test #44:

score: 0
Accepted
time: 32ms
memory: 17012kb

input:

57390

output:

41628873 603450368 64853163 988596721 899091127 403942109 395361880 123358796 381835190 700318485 25341091 106879278 416726920 493496529 564156481 203649376 595532397 212382052 248181594 602729442 690835893 882461884 654417358 619843613 692908768 295382546 349512782 167828617 395152500 78502175 7018...

result:

ok single line: '41628873 603450368 64853163 98...721 64853163 603450368 41628873'

Test #45:

score: 0
Accepted
time: 47ms
memory: 17280kb

input:

86572

output:

682314768 583946368 81234924 83062200 392618097 662535300 929297770 227224492 34927573 430519786 949076022 940148685 22753533 838040061 918847464 713025762 458523234 968358488 121537957 721528214 377419259 814746461 707800698 840151692 514467506 297585550 826110120 518244957 646368780 524717097 4278...

result:

ok single line: '682314768 583946368 81234924 8...00 81234924 583946368 682314768'

Test #46:

score: 0
Accepted
time: 42ms
memory: 18184kb

input:

92842

output:

68105331 746359203 716670426 754877887 383164791 795843601 965547446 252566752 458845738 164348058 592831668 72197228 430641881 302908831 77795693 109130280 822355982 589589531 186436129 427557979 133785916 30033053 472495851 987192994 520917225 944754793 831403857 599567838 454046693 838397110 3748...

result:

ok single line: '68105331 746359203 716670426 7...87 716670426 746359203 68105331'

Test #47:

score: 0
Accepted
time: 45ms
memory: 18836kb

input:

93560

output:

261034369 242378773 784906929 166710524 580207781 613046467 120671106 279568452 553973758 532412319 744027907 912864073 470650563 736746491 960158831 320149940 408937973 889282137 92869549 37932342 115388197 66119982 386380492 130042771 837424296 903822325 427314092 723518783 654083852 708944361 559...

result:

ok single line: '261034369 242378773 784906929 ...4 784906929 242378773 261034369'

Test #48:

score: 0
Accepted
time: 25ms
memory: 17396kb

input:

64270

output:

747959297 922123150 881099986 387716821 731682297 768438298 970199650 802702964 754814029 432875646 188264493 921516620 724687022 667992881 62574674 817146218 464394467 859127796 529317281 876334263 947655536 387246902 955477452 265690513 870808979 141575329 193967942 635592305 273274224 969470215 1...

result:

ok single line: '747959297 922123150 881099986 ...1 881099986 922123150 747959297'

Test #49:

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

input:

78062

output:

545784648 179881450 308969148 99275896 817439451 68443108 645260923 165838774 75934538 27856032 221210238 679268518 936789124 149515015 867306496 601193733 114634740 591725524 948997611 762712359 939913099 92031740 119389440 292224836 501820022 544902268 34584419 612502557 424026351 500306405 806958...

result:

ok single line: '545784648 179881450 308969148 ...6 308969148 179881450 545784648'

Test #50:

score: 0
Accepted
time: 38ms
memory: 18780kb

input:

87278

output:

938299356 669168430 336637201 140370888 17417999 826028211 606358883 984536926 42865092 281462736 722477070 966704762 871179896 507126651 18669445 306991628 611489977 529933820 662263744 691512237 438670338 926495722 873525535 635184019 370731589 547824585 988627010 733541790 860987578 167598636 583...

result:

ok single line: '938299356 669168430 336637201 ...8 336637201 669168430 938299356'

Test #51:

score: 0
Accepted
time: 32ms
memory: 17684kb

input:

65772

output:

284171842 730409051 929306533 354497772 938049078 353124972 967635855 550691085 140580907 137664290 105745563 368769233 636379667 728751147 774061905 771669107 702563258 382714069 763805269 574448646 539074063 559208146 537109162 934948404 775024604 478206918 337843411 119951167 717173540 788935147 ...

result:

ok single line: '284171842 730409051 929306533 ...2 929306533 730409051 284171842'

Test #52:

score: 0
Accepted
time: 22ms
memory: 16528kb

input:

53987

output:

182223061 35770982 34438152 898673115 809139864 315597564 191631632 635475001 140938934 373651960 823157482 259246718 126011358 376710565 437977884 296216283 393915414 82997970 283649444 907840376 74158132 498860929 924117029 758347062 29222941 745200834 73917046 4663794 327714206 542700788 61288024...

result:

ok single line: '182223061 35770982 34438152 89...115 34438152 35770982 182223061'