QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#85369#4817. Half PlaneScintillaAC ✓11670ms88192kbC++147.7kb2023-03-07 17:46:572023-03-07 17:46:58

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-07 17:46:58]
  • 评测
  • 测评结果:AC
  • 用时:11670ms
  • 内存:88192kb
  • [2023-03-07 17:46:57]
  • 提交

answer

#pragma GCC optimize("O2")
#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pb emplace_back
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl

using ull = unsigned long long;
using pii = pair <int, int>;

const int INF = 0x3f3f3f3f;

const int P = 1e9 + 7;

const int N = 6e5 + 10;
const int M = 3e4 + 10;

int read() {
  int x = 0, f = 1; char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
  return x * f;
}

int inc(int a, int b) { return (a += b) >= P ? a - P : a; }
int dec(int a, int b) { return (a -= b) < 0 ? a + P : a; }
int mul(int a, int b) { return 1ll * a * b % P; }
int qpow(int a, int b) { int res = 1; for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a); return res; }

mt19937_64 rng(time(0));
int Rand(int l, int r) {
  return l + rng() % (r - l + 1);
}

struct Data {

  int val[3];

  Data() {
    rep(i, 0, 2) val[i] = 0;
  }

  int& operator [] (int i) {
    return val[i];
  }

  void init() {
    rep(i, 0, 2) val[i] = read();
  }

  void add_eq(Data a) {
    rep(i, 0, 2) val[i] = inc(val[i], a[i]);
  }

  void add(Data a, Data b) {
    rep(i, 0, 2) val[i] = inc(a[i], b[i]);
  }

  void clr() {
    *this = Data();
  }

  void print() {
    rep(i, 0, 2) printf("%d%c", val[i], " \n"[i == 2]);
  }

  bool empty() {
    Data e = Data();
    rep(i, 0, 2) {
      if (val[i] != e[i]) return false;
    }
    return true;
  }

} ;

struct Operation {

  int val[3][3];

  Operation() {
    rep(i, 0, 2) rep(j, 0, 2) val[i][j] = i == j;
  }

  int* operator [](int i) {
    return val[i];
  }

  void init() {
    rep(i, 0, 2) rep(j, 0, 2) val[i][j] = read();
  }

  void apply(Data &a) {
    Data res;
    rep(i, 0, 2) rep(j, 0, 2) {
      res[i] = inc(res[i], mul(val[i][j], a[j]));
    }
    a = res;
  }

  void apply(Operation &a) {
    Operation res;
    rep(i, 0, 2) res[i][i] = 0;
    rep(i, 0, 2) rep(j, 0, 2) rep(k, 0, 2) {
      res[i][j] = inc(res[i][j], mul(val[i][k], a[k][j]));
    }
    a = res;
  }

  void clr() {
    *this = Operation();
  }

  bool empty() {
    Operation e = Operation();
    rep(i, 0, 2) rep(j, 0, 2) {
      if (val[i][j] != e[i][j]) return false;
    }
    return true;
  }

  void print() {
    rep(i, 0, 2) rep(j, 0, 2) {
      cout << val[i][j] << " \n"[j == 2];
    }
  }

} ;

struct frac {
  int p, q;
  frac(int _p = 0, int _q = 1) {
    p = _p, q = _q;
    if (q < 0) p = -p, q = -q;
  }
  friend bool operator < (frac a, frac b) {
    return 1ll * a.p * b.q < 1ll * b.p * a.q;
  }
  friend bool operator == (frac a, frac b) {
    return 1ll * a.p * b.q == 1ll * b.p * a.q;
  }
  void print() {
    printf("%d/%d\n", p, q);
  }
} ;

struct vec {
  int x, y;
  void init() {
    x = read(), y = read();
  }
  friend bool operator < (vec a, vec b) {
    return a.x == b.x ? a.y < b.y : a.x < b.x;
  }
  void print() {
    printf("(%d, %d)\n", x, y);
  }
} ;

struct line {
  int a, b, c;
  frac k;
  void init() {
    a = read(), b = read(), c = -read();
    k = frac(-a, b);
  }
  bool chk(vec p) {
    return a * p.x + b * p.y + c < 0;
  }
  bool above(vec p) {
    if (b > 0) return a * p.x + b * p.y + c < 0;
    else return a * p.x + b * p.y + c > 0;
  }
  friend bool operator < (line l1, line l2) {
    if (l1.k == l2.k) return frac(-l1.c, l1.b) < frac(-l2.c, l2.b);
    else return l2.k < l1.k;
  }
} ;

frac inter(line l1, line l2) {
  return frac(l2.c * l1.b - l1.c * l2.b, l1.a * l2.b - l2.a * l1.b);
}

#define ls lson[u]
#define rs rson[u]

int tot, lson[N], rson[N];
vec p[N];
Data dat[N];
Operation laz[N];

void down(int u, Operation o) {
  o.apply(dat[u]);
  o.apply(laz[u]);
}

void pushdown(int u) {
  down(ls, laz[u]);
  down(rs, laz[u]);
  laz[u].clr();
}

void maintain(int u) {
  p[u] = p[ls];
  dat[u].add(dat[ls], dat[rs]);
}

int newnode() {
  return ++ tot;
}

void undo() {
  pushdown(tot);
  lson[tot] = rson[tot] = 0;
  p[tot] = vec();
  dat[tot].clr();
  -- tot;
}

struct O {
  int id;
  line l;
  Operation o;
} op[N];

int n, m, B, rk[N];
ull pre[N], suf[N], h[N], key[N];

void solve(int l, int r, vector <int> c) {
  int len = r - l + 1, cur = tot;
  auto work = [&]() {
    for (auto it : c) h[it] = 0;
    vector <int> ord;
    rep(i, l, r) ord.pb(i);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
      return op[i].l < op[j].l;
    });
    rep(i, 0, len - 1) {
      key[ord[i]] = rng() % (1ll << 60);
      pre[ord[i]] = i ? pre[ord[i - 1]] : 0;
      if (op[ord[i]].l.b < 0) pre[ord[i]] ^= key[ord[i]];
      rk[ord[i]] = i;
    }
    drep(i, len - 1, 0) {
      suf[ord[i]] = i < len - 1 ? suf[ord[i + 1]] : 0;
      if (op[ord[i]].l.b > 0) suf[ord[i]] ^= key[ord[i]];
    }
    sort(c.begin(), c.end(), [&](int i, int j) {
      return p[i] < p[j];
    });
    vector <pair <frac, pii> > px;
    rep(i, 0, len - 1) rep(j, i + 1, len - 1) if (op[ord[j]].l.k < op[ord[i]].l.k) {
      px.pb(mp(inter(op[ord[i]].l, op[ord[j]].l), mp(ord[i], ord[j])));
    }
    px.pb(mp(frac(INF, 1), mp(0, 0)));
    sort(px.begin(), px.end(), [&](pair <frac, pii> a, pair <frac, pii> b) {
      if (a.first == b.first) {
        if (rk[a.second.first] == rk[b.second.first]) {
          return rk[a.second.second] < rk[b.second.second];
        }
        else return rk[a.second.first] < rk[b.second.first];
      }
      else return a.first < b.first;
    });
    for (int i = 0, j = 0; i < px.size(); ++ i) {
      for (; j < c.size() && p[c[j]].x < px[i].first; ++ j) {
        auto it = partition_point(ord.begin(), ord.end(), [&](int k) {
          return !op[k].l.above(p[c[j]]);
        });
        if (it != ord.end()) h[c[j]] ^= suf[*it];
        if (it != ord.begin()) h[c[j]] ^= pre[*(-- it)];
      }
      int u = px[i].second.first, v = px[i].second.second;
      if (!u && !v) continue;
      assert(rk[u] + 1 == rk[v]);
      swap(ord[rk[u]], ord[rk[v]]);
      swap(rk[u], rk[v]);
      if (op[u].l.b < 0) pre[v] ^= key[u];
      else suf[v] ^= key[u];
      if (op[v].l.b < 0) pre[u] ^= key[v];
      else suf[u] ^= key[v];
    }
    sort(c.begin(), c.end(), [&](int i, int j) {
      return h[i] < h[j];
    });
    vector <int> nc;
    for (int i = 0, j; i < c.size(); i = j + 1) {
      for (j = i; j + 1 < c.size() && h[c[j + 1]] == h[c[i]]; ++ j) ;
      if (i < j) {
        rep(k, i + 1, j) {
          int u = newnode();
          ls = k == i + 1 ? c[i] : u - 1, rs = c[k];
          maintain(u);
        }
        nc.pb(tot);
      }
      else nc.pb(c[i]);
    }
    c = nc;
  } ;
  work();
  if (l == r) {
    bool flag = false;
    for (auto it : c) {
      if (op[l].l.chk(p[it])) {
        dat[it].print();
        down(it, op[l].o);
        flag = true;
        break;
      }
    }
    if (!flag) printf("0 0 0\n");
    while (tot > cur) undo();
    return;
  }
  int mid = (l + r) >> 1;
  solve(l, mid, c);
  solve(mid + 1, r, c);
  while (tot > cur) undo();
}

#undef ls
#undef rs

int main() {
  n = read(), tot = n;
  rep(i, 1, n) p[i].init(), dat[i].init();
  m = read(), B = sqrt(n);
  rep(i, 1, m) op[i].l.init(), op[i].o.init(), op[i].id = i;
  for (int l = 1, r; l <= m; l = r + 1) {
    r = min(l + B - 1, m);
    vector <int> all;
    rep(i, 1, n) all.pb(i);
    solve(l, r, all);
  }
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 7ms
memory: 67012kb

input:

5
1 1 2 3 4
12 12 4 6 1
1 12 5 1 2
12 1 1 5 5
6 6 2 0 3
3
1 1 4 1 1 2 3 4 5 2 3 4
1 1 400 1 3 4 2 1 2 3 4 5
-1 -1 -10 3 2 1 4 6 5 4 3 2

output:

2 3 4
25 50 40
92 58 139

result:

ok 3 lines

Test #2:

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

input:

8
-509 1134 869419079 764178960 818736647
-2836 296 965929020 482991943 829626659
1594 -1045 289612318 572608619 474362463
-2946 -165 85255903 285022572 770151631
-74 -131 732523347 283776652 211209006
-627 -604 539714672 763810142 817996815
-1187 -1219 734874008 764773559 261445054
-18 226 31476550...

output:

242481509 621755738 615459217
984440526 242571329 417013116
122667367 215125161 518083968
594780462 21825000 214574293

result:

ok 4 lines

Test #3:

score: 0
Accepted
time: 185ms
memory: 68644kb

input:

30000
676 -1234 836467424 502287177 140023561
-2003 -54 939673593 585085650 422504901
14185 -49892 469301115 424738168 942143157
-6019 4933 573698653 956514739 385606216
-1097 -1767 918532462 279450765 873950517
-2732 5210 428418604 607751438 2805137
-2791 1240 250817926 463999452 951276698
-3460 -5...

output:

538200103 176562537 786040129
282120049 585253989 126746038
442585365 946639191 152848161
309217862 352168103 288017696
798331649 483116583 428411187
396357116 876189623 301235280
832917758 314259493 851554086
129794051 40695662 730810045
922712284 511389451 59925242
580263289 336968685 459480891
17...

result:

ok 1000 lines

Test #4:

score: 0
Accepted
time: 175ms
memory: 68632kb

input:

30000
-861 514 579191255 606538526 388715812
-2743 143 33760465 13211059 128903675
105 -1848 31959805 331710130 184775255
19 -1110 445507093 115980536 539879344
-1041 41 507163898 642632299 488129195
1471 81 294281682 547102977 542058890
804 -843 987425295 849386341 831783549
-1793 -2178 444562260 3...

output:

545178258 677491591 34959177
426445915 979131304 126183119
215187507 759685069 499663658
200968299 790214661 15389717
839830981 763311704 525155406
857030222 464548447 842171760
658456271 313959441 663157301
771261247 935340775 339842291
94545060 716008509 891433021
347612571 574108893 940930350
363...

result:

ok 1000 lines

Test #5:

score: 0
Accepted
time: 184ms
memory: 68596kb

input:

30000
10549 19178 551387003 459346332 265437020
-4440 -801 346488842 634142290 954669423
-1758 964 418335341 620928953 575285343
-4434 4081 109829333 799485017 24011325
-4527 -24166 664063304 756571635 986936785
-2020 -826 968644308 698506784 869326786
-2700 -7894 94755543 255350611 433336916
-6626 ...

output:

93567974 334118538 550727969
788441432 886909715 475552713
526828502 419035304 422234431
226030179 753442982 68364174
453395418 329482885 434105443
15411089 926245366 274889354
829805395 617738666 67824539
591388868 172923133 108968027
491445793 193764448 630342293
185049502 34074677 601638041
68749...

result:

ok 1000 lines

Test #6:

score: 0
Accepted
time: 160ms
memory: 68688kb

input:

30000
729570 -682315 124492027 232374133 480672372
-89810 -111355 986358898 821368981 395456251
167275 -156587 366703017 453206326 674212301
362570 -471220 637350218 819423356 510777066
-256566 369328 923342730 723162512 203219131
-85619 132807 403845003 932528656 550721085
58246 68727 988188769 670...

output:

177234170 706893826 321822432
51918258 607410764 301981413
520332556 577378859 923040905
748810147 59692955 792648057
715348611 655896889 617831176
601836304 718124476 848465506
797797405 409159165 810850490
467212419 781133102 681159662
508324225 694481060 155771698
74229267 592178614 439534413
690...

result:

ok 1000 lines

Test #7:

score: 0
Accepted
time: 138ms
memory: 68580kb

input:

30000
215276 568757 143058747 670589199 352546244
675349 276797 890016278 179562506 916859284
485993 366119 538889148 285689789 926460934
-184492 100853 168179724 850340050 328350589
542050 68798 786636421 318440051 561731640
226406 81944 652753350 969237706 547819021
-143180 485953 369758464 939858...

output:

365510556 899423656 472212247
119697678 211030227 547616991
943724197 8064634 987392937
751180665 973505281 385971334
146010557 420227720 902462073
950046809 985538196 710838208
550105062 384450812 364915306
671184632 124125952 829362702
960089545 335852503 982532966
451317766 825994835 31863551
648...

result:

ok 1000 lines

Test #8:

score: 0
Accepted
time: 152ms
memory: 68644kb

input:

30000
11963 26612 563932814 736535581 744632517
-2996 -641 649230390 398487502 776589770
1657 10623 794968118 747797397 59585526
-1289 4706 836020237 90456178 741776740
10179 -7004 847704879 346040819 168119367
21602 16579 515124205 829841195 234479530
-9495 4238 514818687 716733774 820045998
11361 ...

output:

847073709 381148374 516974732
325834948 765765564 453516874
352025353 10436598 371323304
519640707 574307750 444125010
964483737 141341740 498601658
122304331 399174936 431259077
742526585 700279913 545695293
236747120 378183966 111872419
373973546 315782774 219011044
653194034 928721309 678537800
1...

result:

ok 1000 lines

Test #9:

score: 0
Accepted
time: 168ms
memory: 68688kb

input:

30000
2313 20 151184035 531728233 996237244
515 -436 420930337 404861517 994681405
2926 -1322 689432222 234158944 272476457
52 530 390434030 44056866 776993283
-120 125 513404791 337625507 139274204
-1510 -588 855754494 303354450 351544403
291 419 471802575 810180275 84881798
-926 203 191026997 8895...

output:

935216674 480722085 384576623
621069889 322955919 600300871
538133841 334312373 608592766
399447778 295652105 484049427
606144001 591324118 339546480
453328653 101855275 823859765
818910344 986178644 528468199
516357332 825796558 402562947
380183389 14261509 250494299
809568025 37546310 730423078
16...

result:

ok 1000 lines

Test #10:

score: 0
Accepted
time: 109ms
memory: 68700kb

input:

30000
-3 0 18053028 724837864 201780269
4 -1 369642866 720614816 646577044
-2 3 992365366 938793416 407081706
1 -4 738991115 509688102 673930606
-5 -3 948082291 588327493 257752862
158959 -317919 21154757 755166158 63273074
-231604 463212 308429264 964756648 833312195
-274206 137101 54048637 8096471...

output:

862026374 343842668 392567836
26146542 777447884 265002500
519892143 987619881 426932515
307747538 901692231 98873625
299878208 896834820 396084450
518123452 367206424 423709655
492309974 426180612 43588029
93883631 234933962 816430356
941272925 469347297 418005544
712877801 820259786 207116902
6203...

result:

ok 1000 lines

Test #11:

score: 0
Accepted
time: 131ms
memory: 68684kb

input:

30000
-628784 -314394 968049914 611010155 822556658
-3 0 838684476 988751102 498207269
6 -1 158444020 203447175 827072499
-2 2 841964319 627180884 755281158
0 1 413763717 628446147 347356885
-284050 284052 94365801 261989175 608758104
-581295 -290648 374291550 717086259 564713688
73891 -55417 174966...

output:

957939759 686088484 588606155
357666270 89551368 871461447
304416932 448365469 240287435
189543262 819930261 29529388
991099953 449913997 43461210
477390988 422207149 985823068
562575922 578008854 565415569
204689372 295956274 353515327
903410183 296376364 476833877
243697219 390369978 573897742
136...

result:

ok 1000 lines

Test #12:

score: 0
Accepted
time: 84ms
memory: 68464kb

input:

30000
-999828 -999830 173576982 203686018 994555951
-998603 -998590 115320595 714379127 71972197
-998454 -998461 582494909 402300032 56908643
-999936 -999947 309327006 413646683 29938844
-998533 -998540 405243148 585079102 398415243
-999121 -999124 461176875 806714912 415591127
-999368 -999360 81873...

output:

706781663 971336842 722570837
901431625 707596220 681677130
732352331 871961411 695587377
408559767 167863511 861911926
896487900 934792684 147141981
493733093 18703611 340196993
985805162 566839384 988513262
491465851 966179587 213337874
679343318 939892014 685452506
271297173 725622566 526378994
4...

result:

ok 1000 lines

Test #13:

score: 0
Accepted
time: 78ms
memory: 68504kb

input:

30000
-998172 -998163 303367951 336827340 741891676
-998613 -998627 978906198 787402624 411749183
-999756 -999760 209847555 827753782 828064940
-998721 -998722 57298138 24146456 133315754
-999055 -999049 485766055 400319901 927614503
-999515 -999512 819375843 657191016 397525265
-998927 -998917 5628...

output:

344833859 511256074 589227250
160649192 831110888 812776997
364036365 231766374 134127815
561228840 82616806 21344553
492460416 411409491 673466870
81178955 7782751 53224357
668188185 936366293 846510789
447219778 260304026 996347527
195850491 714970045 82351025
519868498 352974360 74737778
46063511...

result:

ok 1000 lines

Test #14:

score: 0
Accepted
time: 11038ms
memory: 88116kb

input:

300000
6021 230 81186458 630223908 123502523
2206 -531 689274343 832968795 677935
-341 -5215 716916582 683843861 647948947
2201 -1132 238585560 881522585 759965041
-177 -1074 8264009 559321916 639075365
6108 6279 962302528 744228952 68956569
-4693 -2455 441948155 503678773 745829679
-420 -13854 4728...

output:

82983903 179991622 106488484
681002891 958372672 310322005
363534694 53035454 56365650
7875167 569276234 649871689
308858221 563321281 619554189
592339933 652542820 630728333
751354771 257358842 153279350
641615783 461178965 609603439
461431233 661609045 84919622
531356919 122787693 685566390
370288...

result:

ok 15000 lines

Test #15:

score: 0
Accepted
time: 11544ms
memory: 88120kb

input:

300000
-1541 2074 483711051 775771378 933380329
-1202 937 14941100 95502583 406917332
-397 933 119936225 788956255 184399251
-2102 3773 467131826 239645751 2290676
2072 -263 932141083 104521580 379780700
1158 -1549 370331747 922535291 448464108
-229 -2937 703381418 812044117 231275901
6736 6078 1912...

output:

151554358 46645906 509711997
957929736 124465982 921338614
780537979 152135527 222940084
898910633 706590019 155412491
666177849 668780531 141518722
120573053 841195759 693067816
673859081 914870171 539596578
797525561 762342396 893229210
666026033 522635102 678158674
324491661 430885376 143810029
2...

result:

ok 15000 lines

Test #16:

score: 0
Accepted
time: 11097ms
memory: 88192kb

input:

300000
-1429 3885 869722740 460347054 807234428
3210 -4073 740106320 769063122 1794249
-5330 999 825552652 687199472 471974260
3992 -13122 563236 12365054 26764156
5815 12317 619466573 742538443 90994367
3260 -11043 547395011 86980825 479243959
-4918 -5000 463639498 694648153 191692996
-8213 704 355...

output:

70369296 802723337 485242181
778408067 101136699 578430827
59236084 859831660 652901410
487792116 558581293 540295156
397927035 696155263 604985519
532561270 256798053 163000549
660547771 964952980 130194673
795610991 542049320 508344297
837462486 8411881 118887485
624170576 492134445 605006279
1220...

result:

ok 15000 lines

Test #17:

score: 0
Accepted
time: 10499ms
memory: 87884kb

input:

300000
-48956 176288 294568837 681990844 108484875
465540 30060 594194061 432722326 975809276
322853 86233 624880701 636519647 123533058
39572 123790 52446149 837375344 874805784
242075 16355 814153380 808465176 310264045
724220 141800 250042243 452069985 785962576
-15397 -302885 721918671 849665682...

output:

217164511 890555989 468580431
873672440 10416005 335152754
168260096 296116507 515183079
643587763 110241008 532159647
292054849 298856232 32579311
817235669 740795802 947667483
811580830 305170089 60911106
943907963 645552165 485781477
775206500 940421299 273866375
614646408 207555416 197985210
962...

result:

ok 15000 lines

Test #18:

score: 0
Accepted
time: 8830ms
memory: 84832kb

input:

300000
548861 388115 822669343 873492273 64551335
142114 483309 73323733 377207989 401490383
409937 433860 468438030 733460962 86587324
-95314 -724737 220585189 596749522 236182178
-232292 101582 962016830 94900027 376733896
-471250 -383514 546101196 384906647 735431088
-613815 -28324 935120004 2278...

output:

840102999 395990206 325451803
635747567 312896695 686169301
32392523 67192111 801889682
905088946 148676049 290362045
845729578 970554643 850798992
755069476 398969651 75952502
393532004 199951181 778505295
554172772 657233299 368574943
475330407 790333939 809810988
488164236 296809553 245848217
302...

result:

ok 15000 lines

Test #19:

score: 0
Accepted
time: 10867ms
memory: 88104kb

input:

300000
5682 9377 949323658 553347341 444480700
-558 12821 479233963 838560675 503993160
-90072 99174 64550749 372042921 157455703
33629 -18539 910752028 675178989 6183338
4094 -9068 571409045 855828101 666318228
7362 -3223 994148664 59458754 429764351
18143 15935 497100086 130510740 101003327
19627 ...

output:

134876512 996773578 290017641
12972555 545073419 36920150
163613612 148286639 953392953
549979315 813956825 439846140
461903687 393685137 111966526
384221517 205800294 614191703
398427965 265931649 896187620
398769200 244677051 117091887
858689143 583789209 164596528
320325883 648990746 692320533
91...

result:

ok 15000 lines

Test #20:

score: 0
Accepted
time: 10950ms
memory: 87828kb

input:

300000
547 690 346545624 337977798 795059761
45 -551 949642049 482808092 690979844
3219 -718 283653294 808205832 301230355
-642 434 137063134 719417339 556377894
1348 -877 935715166 762762998 429929218
-580 1119 98934045 111915923 121943244
-160 1552 415902936 660527333 715593097
562 267 940796772 8...

output:

676314820 153422372 531726977
957088456 516181215 376785017
411232593 251615075 698932972
872121538 638474993 392125420
184376465 170196693 682538955
162640120 365396981 315291403
899719122 784781991 193165169
900756271 249147967 727724517
558035587 964383737 923478314
673082882 410404532 216144252
...

result:

ok 15000 lines

Test #21:

score: 0
Accepted
time: 6195ms
memory: 85052kb

input:

300000
-160874 -321740 650679894 682085901 118564431
1 3 829284607 674413386 589242129
-1 -5 128251902 861925529 227295077
2 0 483335001 136506986 627827042
373064 -186531 980063766 887583003 124536602
-556935 278464 203163296 576564387 284484406
0 -8 370263598 946662142 724897316
-322063 -161035 16...

output:

270929648 657292934 1072391
355748333 538055525 893060481
923071675 138126180 897616241
368606556 247572560 663225792
935528969 985474533 765493326
906004891 660594616 73269130
270889963 986581893 508328370
548082638 466247003 942212565
541968798 644553201 603406730
130543301 125334160 698875079
901...

result:

ok 15000 lines

Test #22:

score: 0
Accepted
time: 8100ms
memory: 85188kb

input:

300000
65295 -195880 385584455 694104346 148795395
-13 -17 488197125 209315462 279490886
-265924 66482 956139323 150523857 807174592
-10 -1 489624340 294113836 105155469
301777 -452671 177016278 761145479 618009928
-483086 483087 707376469 281943593 287178442
2 0 204033761 106059218 639213997
-61180...

output:

78838465 117908463 834181295
567509055 243808330 913222361
244968863 163827552 29820256
154896700 770138099 728655661
315086555 153737882 840149247
724261403 931639840 627022483
657782150 581792098 520940815
16423833 44322662 944662939
598320637 918035850 598728337
956869149 20662870 706170737
92870...

result:

ok 15000 lines

Test #23:

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

input:

300000
-999985 -999984 771104286 637539159 323203410
-999930 -999940 788941295 790543578 678521431
-999997 -1000000 570602998 259724723 505592327
-999928 -999926 186482400 667942892 390211978
-999945 -999954 958616669 706098243 622246987
-999968 -999960 483002356 756786785 778047664
-999927 -999932 ...

output:

591071517 442832578 964585697
131194468 225150960 545438630
128272459 154095760 478240411
320650232 79107616 719175041
486515135 177636535 839480941
651280717 776056591 819483361
321866025 378471124 83934758
673281094 275690569 340822554
643704765 951851307 349176407
230158685 745653379 178123286
10...

result:

ok 15000 lines

Test #24:

score: 0
Accepted
time: 3287ms
memory: 83068kb

input:

300000
-999676 -999679 299330476 945554727 657777676
-999904 -999916 20053996 611803916 395817665
-999670 -999670 612731766 864724128 359400642
-999937 -999940 489607311 867858727 277218512
-999649 -999655 935906592 757715137 78332801
-999895 -999899 135123021 969130132 219960695
-999655 -999649 169...

output:

709554873 609165180 555956807
531357241 714224166 923404132
127543156 497814595 947821210
301695249 357344553 804158600
210468246 92645771 652991804
316278431 884960110 415712621
164978596 222153968 988524136
106053390 369509942 622807089
873613124 255812459 616511678
409751051 73665693 141378215
67...

result:

ok 15000 lines

Test #25:

score: 0
Accepted
time: 1659ms
memory: 71052kb

input:

65536
-128 -128 708578711 499407572 642979214
-128 -127 5380635 850194636 966346205
-128 -126 442014492 142528482 610486620
-128 -125 828136096 678175179 22530505
-128 -124 857359786 624737028 825258522
-128 -123 757405373 240905621 152449995
-128 -122 203888775 621532595 680687473
-128 -121 5865051...

output:

944158242 470610728 324244920
947225065 20496025 91607361
813293281 208911888 569449785
428221964 621131992 628199758
31116565 179087985 695555347
158594615 97325092 68183428
408860838 264156737 165049069
599382005 7206793 468343080
488058929 761025356 661014958
123067024 941391330 400777058
4817810...

result:

ok 10000 lines

Test #26:

score: 0
Accepted
time: 1732ms
memory: 70976kb

input:

65536
-128 -128 818210398 350781835 808267841
-128 -127 598893503 929012653 956329690
-128 -126 87366628 643195410 600522273
-128 -125 796246237 758640967 930653623
-128 -124 642577701 229239488 736734352
-128 -123 707428687 112318005 145500329
-128 -122 918542168 917677101 820610552
-128 -121 90255...

output:

855682198 211910937 39504531
682339758 422219265 456212785
21608811 299210296 409888641
186999437 896166393 317172847
877820550 219410090 708309892
328654979 945865162 607723625
399336057 110910736 627799030
63908341 751868626 60091881
502622849 875513884 466344371
608605021 283506714 277953532
6707...

result:

ok 10000 lines

Test #27:

score: 0
Accepted
time: 845ms
memory: 70824kb

input:

65536
-128 -128 321669782 130247468 561206790
-128 -127 586338406 194856392 107744466
-128 -126 131308995 725738615 9547769
-128 -125 468414571 779122301 704741042
-128 -124 589970087 691554526 435763847
-128 -123 765019622 297637752 766277236
-128 -122 768772892 351956378 376748837
-128 -121 217385...

output:

452238362 220635836 746985503
633072170 440058234 542058223
907080515 242487087 910036035
685519110 129478062 394899270
55462417 689975056 149618496
240204643 811436389 936545164
490369905 866444411 284153567
227518462 755988386 713973494
920668178 938766338 281737723
238078066 685725788 490649730
4...

result:

ok 10000 lines

Test #28:

score: 0
Accepted
time: 864ms
memory: 70808kb

input:

65536
-128 -128 431301469 276588999 17667414
-128 -127 179851266 568641678 806555954
-128 -126 67833135 935233540 704616161
-128 -125 731491980 859588089 202798683
-128 -124 375188003 587228991 933378949
-128 -123 420075667 464017404 349262100
-128 -122 483426279 353133617 516671916
-128 -121 537226...

output:

211966235 578279482 781544846
429714636 652539297 4320996
989365990 954279125 553787357
212146530 285860296 862484974
96926573 74014623 511632690
96404576 632735159 69659452
783703164 828444528 6879499
686760001 63051304 738376033
554907616 566374092 504484087
165864008 133776084 107140753
485715573...

result:

ok 10000 lines

Test #29:

score: 0
Accepted
time: 1855ms
memory: 81940kb

input:

300000
0 0 596981855 579443258 477525092
0 2 815869175 972934050 743291979
0 4 978860748 76319153 632768702
0 6 306834906 942121618 858912401
0 8 387540510 114700412 508251746
0 10 36256602 331228420 185902564
0 12 803824169 340723119 139573240
0 14 353565972 761261492 146228475
0 16 466786733 59456...

output:

608475874 971471451 630382617
211136806 81336083 766490611
995262791 87160153 28671548
293997269 612426055 584834410
394350234 917367029 864933496
54824456 240344520 675951953
849790890 437774062 942745218
649919302 238190182 155165269
255943586 501943472 375110461
635898015 716335644 547105804
2803...

result:

ok 15000 lines

Test #30:

score: 0
Accepted
time: 1795ms
memory: 81940kb

input:

300000
0 0 706613542 139645516 642813719
0 2 114414767 346719329 28242725
0 4 620417621 576986082 331632351
0 6 569912316 731415402 767035512
0 8 758897697 420440347 714694844
0 10 691312655 497608072 473920167
0 12 227305551 636867625 279496319
0 14 673407122 85726981 562738249
0 16 516647826 53255...

output:

478522684 850704721 42775037
972197898 133836878 153764286
547192203 361586578 506493931
729784777 872900800 783163091
366710007 227964936 792316751
394329763 198812111 10245245
147751517 779562109 562662671
701585197 281466482 921143289
595798079 189408529 756717355
236338796 73081228 70561406
1710...

result:

ok 15000 lines

Test #31:

score: 0
Accepted
time: 11257ms
memory: 88120kb

input:

300000
-2350 -3013 245675462 911378048 677362975
-358 -1385 585223865 818408768 422435834
1404 -1016 97087157 33014793 865923491
3214 -4102 973788862 635238160 214679469
-14075 4240 478390393 651257077 954350005
1670 -1280 899638249 497851197 445742566
720 -4482 434549131 651313696 854472472
1306 45...

output:

965858405 257261426 109123560
364237663 642045031 470762934
214912455 452993922 187120151
144207494 199137546 213132841
881082698 295259830 56824314
110294644 886267221 289200595
439326763 839800084 258705172
755433994 386134006 34508765
988958105 879862458 839908536
506235645 314709525 745914401
66...

result:

ok 15000 lines

Test #32:

score: 0
Accepted
time: 11670ms
memory: 88096kb

input:

300000
-2302 190 714995886 991088608 771990293
1014 85 231347730 542747622 134541710
-3310 1707 255951607 873272465 393426788
1018 -1244 982323740 223584309 355203619
638 996 117472513 670442187 316109785
1398 -1069 434150242 100290322 311294015
-976 582 926092587 539041159 311253467
1401 998 977699...

output:

458051332 222894922 632542639
996576604 436332126 677096767
533004139 206805363 141675540
448476031 883747960 242014768
760491187 322749269 964267014
639208139 961743089 13828085
989519473 946779167 568162719
793658482 68745626 385154053
77255667 797485920 330146602
809574245 860315828 475452623
373...

result:

ok 15000 lines

Test #33:

score: 0
Accepted
time: 11462ms
memory: 88112kb

input:

300000
6772 -15300 235980676 58877798 146257108
4095 7455 719702624 104531778 692144934
-36695 -13242 168908060 753219166 968936472
-2218 -1192 291504199 659962689 621579638
-1285 2233 544667828 492538481 481849967
-655 -1430 533437760 928093108 116284051
1479 -1437 365663907 764811847 93914417
7157...

output:

547154138 732249021 673486000
888884289 549656006 773460681
73834513 601743541 830036604
417673799 902083474 765199341
519486404 408403165 174211855
45670451 313653429 950733578
21340257 892976645 769723492
913680579 691513312 339583552
485678663 726031463 84403032
313999626 318902519 923903402
4969...

result:

ok 15000 lines

Test #34:

score: 0
Accepted
time: 10607ms
memory: 87756kb

input:

300000
115220 86640 609193479 302434012 22394158
-391 -70503 803048016 760371293 37973011
-67392 343436 244886174 583899088 882242632
560714 114828 518615698 715313998 94399409
-21830 181310 997166576 248502368 694763319
40150 -121754 62637961 224486026 745558881
67221 110717 693447109 9798016 45882...

output:

201600093 183607204 771639571
129652125 545101303 969375610
788167477 725027865 229184956
81233333 494233469 66621115
273959673 101167775 585290416
827958699 757666522 242277767
473919790 680542798 261772569
795797996 203721372 904611160
462186915 305058046 185446570
166114066 498521271 554538946
56...

result:

ok 15000 lines

Test #35:

score: 0
Accepted
time: 8716ms
memory: 84760kb

input:

300000
111350 443017 158808827 376761115 614329510
-97653 -699073 481682438 776135393 563312585
334069 325834 503974582 419117286 410048070
-91661 101509 881047510 53170370 739892500
-150820 -752747 433037934 945672768 306740646
-524852 278705 392150199 319206779 496205813
-178130 -28629 172189389 9...

output:

581294923 242817632 936401012
431037860 811658812 65127210
601945043 639422138 842848405
314564112 886535959 812556910
548115791 187390985 898843145
539509472 486057492 141733143
445896480 112949679 306559814
317129459 808857111 570035
83302897 129014172 990702370
204692059 809946524 795322018
96768...

result:

ok 15000 lines

Test #36:

score: 0
Accepted
time: 10891ms
memory: 88112kb

input:

300000
17576 -24307 581185987 901924920 267036504
5403 -8414 486177640 341809894 238657082
12228 1834 418950426 19746557 840661286
-7367 -37147 848084279 101445151 419510948
-1476 -10966 248160616 736116458 821164473
-5039 5722 643671042 11737615 22364656
-6927 6171 60700185 625685920 115812243
-839...

output:

93157683 129666402 165032323
275075573 399960799 621922143
327896783 583180727 549111133
613556504 695615462 434639292
109604816 194075542 321249522
610001749 292355842 848229107
330290018 46784925 750220800
903214311 794738940 625152817
785215182 140437065 909450955
584743914 896505574 821267297
89...

result:

ok 15000 lines

Test #37:

score: 0
Accepted
time: 11000ms
memory: 87820kb

input:

300000
821 -1089 397376108 866417645 124937321
-25 -104 201522775 629372122 21412667
2222 4683 242926747 757056677 71274423
-606 111 858008622 499358170 838682503
-1293 -814 887009168 7325898 834353710
-3629 -776 514576571 968228660 740151058
-837 112 209013563 292613247 500136458
107 82 558575219 9...

output:

615499773 436152353 401998327
35446237 739885469 948659097
62967612 735829517 504099057
982124397 234247445 787888837
842711401 585655887 703181052
92853025 290147258 776887418
867121044 136363853 95209801
125722478 363541636 509424481
657610365 362873327 591312176
432776125 905215709 598033075
2833...

result:

ok 15000 lines

Test #38:

score: 0
Accepted
time: 6271ms
memory: 85088kb

input:

300000
-40738 81487 331967802 82741171 966286568
1 -5 358342798 698097228 174193661
3 -1 362193443 704588389 595478314
0 -1 824624354 678819820 778453632
4 1 146518698 674014883 878467586
-222855 -111429 100825625 911901998 41788699
-64386 -32198 901183368 850328975 927107528
2 1 713432882 452725941...

output:

423403983 977193767 921040649
829919188 609962346 699555649
937712585 62912960 655712614
435815771 86221253 890566162
858426142 422549036 89966335
160814039 12854330 680380157
737662080 330073975 684678436
814817703 172583247 763569718
782191585 813624698 170080499
600355438 30697312 512021353
83977...

result:

ok 15000 lines

Test #39:

score: 0
Accepted
time: 7768ms
memory: 85260kb

input:

300000
-114533 114532 924415007 388541673 449773062
16 -8 644104868 551472959 795024387
-3 4 712060441 421873472 662640215
-1 0 430080686 690558550 136656034
6976 5230 402878063 85846043 415643291
0 2 895388418 512282055 979104476
0 1 727779542 227423436 895159386
9867 14805 385627768 982944714 8332...

output:

466101494 903569366 334769328
271638391 915938966 464423618
541933334 699263706 301444831
167553367 761528617 563945605
105256150 465824006 732836738
764512484 222790413 701757593
989080064 937828617 230564512
461752681 455817555 120237947
146668365 635098820 465104829
38548516 85635309 679852295
16...

result:

ok 15000 lines

Test #40:

score: 0
Accepted
time: 3274ms
memory: 83044kb

input:

300000
-999959 -999960 887172069 715590592 910705137
-999921 -999930 778196637 886301768 85219705
-999929 -999931 236033502 895271481 254172430
-999936 -999931 774652077 459165007 482096470
-999943 -999946 259807100 505990673 92757934
-999980 -999975 17951511 279571703 51055321
-999976 -999975 41581...

output:

970191661 521585630 565008771
182514132 850585301 95065808
393160936 539045163 742688747
533052596 951713993 312181914
378871730 621694012 682710054
762234342 105821044 842614998
715231584 90033696 788426771
402638334 546752099 85739839
379736023 59460506 893522473
938228203 114437634 894336152
7530...

result:

ok 15000 lines

Test #41:

score: 0
Accepted
time: 3279ms
memory: 82872kb

input:

300000
-999687 -999682 150011522 945777683 814170751
-999969 -999962 467924468 25246178 131509199
-999792 -999801 767864038 4561657 320011913
-999785 -999775 542135863 447736948 207208614
-999837 -999827 307902769 866598398 371705330
-999697 -999703 889709104 404635934 937321575
-999798 -999787 1550...

output:

259097185 892424434 324634999
933312298 768931020 113221640
278105398 237976001 232433349
119730417 471250584 145816716
976653796 640400157 313232226
223416848 529505621 898628379
470398626 854360251 983498041
15245902 428886420 635392136
21460781 385378735 100904271
884275064 153920670 783063111
48...

result:

ok 15000 lines

Test #42:

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

input:

1
335611 335626 973830257 495258238 637490447
1
-3 3 46 307267412 943972690 865059306 73069911 513416910 400977391 776349245 417271346 266127937

output:

973830257 495258238 637490447

result:

ok single line: '973830257 495258238 637490447'