QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#673645#9487. Vivid Colorshos_lyricAC ✓879ms169108kbC++148.4kb2024-10-25 04:15:192024-10-25 04:15:20

Judging History

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

  • [2024-10-25 04:15:20]
  • 评测
  • 测评结果:AC
  • 用时:879ms
  • 内存:169108kb
  • [2024-10-25 04:15:19]
  • 提交

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 = 998244353;
using Mint = ModInt<MO>;


inline int sig(Int r) { return (r < 0) ? -1 : (r > 0) ? +1 : 0; }
inline Int sq(Int r) { return r * r; }
struct Pt {
  Int x, y;
  Pt() : x(0), y(0) {}
  Pt(Int x_, Int y_) : x(x_), y(y_) {}
  Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y); }
  Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y); }
  Pt operator*(const Pt &a) const { return Pt(x * a.x - y * a.y, x * a.y + y * a.x); }
  Pt operator+() const { return Pt(+x, +y); }
  Pt operator-() const { return Pt(-x, -y); }
  Pt operator*(const Int &k) const { return Pt(x * k, y * k); }
  Pt operator/(const Int &k) const { return Pt(x / k, y / k); }
  friend Pt operator*(const Int &k, const Pt &a) { return Pt(k * a.x, k * a.y); }
  Pt &operator+=(const Pt &a) { x += a.x; y += a.y; return *this; }
  Pt &operator-=(const Pt &a) { x -= a.x; y -= a.y; return *this; }
  Pt &operator*=(const Pt &a) { return *this = *this * a; }
  Pt &operator*=(const Int &k) { x *= k; y *= k; return *this; }
  Pt &operator/=(const Int &k) { x /= k; y /= k; return *this; }
  Int abs2() const { return x * x + y * y; }
  Int dot(const Pt &a) const { return x * a.x + y * a.y; }
  Int det(const Pt &a) const { return x * a.y - y * a.x; }
  bool operator==(const Pt &a) const { return (x == a.x && y == a.y); }
  bool operator!=(const Pt &a) const { return !(x == a.x && y == a.y); }
  bool operator<(const Pt &a) const { return ((x != a.x) ? (x < a.x) : (y < a.y)); }
  friend ostream &operator<<(ostream &os, const Pt &a) { os << "(" << a.x << ", " << a.y << ")"; return os; }
};
inline Int tri(const Pt &a, const Pt &b, const Pt &c) { return (b - a).det(c - a); }

// [0, 2 PI)
int cmpArg(const Pt &a, const Pt &b) {
  const int sa = (a.y > 0) ? 1 : (a.y < 0) ? 3 : (a.x > 0) ? 0 : 2;
  const int sb = (b.y > 0) ? 1 : (b.y < 0) ? 3 : (b.x > 0) ? 0 : 2;
  return (sa < sb) ? -1 : (sa > sb) ? +1 : sig(b.det(a));
}


struct DirSorter {
  // direction -eps: sort lex. by ((x, -y), u)
  vector<int> ini;
  
  // direction arg(dir)-eps ~~> arg(dir)+eps: ps[u]<ps[v] ~~> ps[v]<ps[u]
  struct Event {
    Pt dir;
    Int detU, detV;
    int u, v;
  };
  vector<Event> es;
  
  DirSorter() {}
  DirSorter(const vector<Pt> &ps) {
    const int n = ps.size();
    ini.resize(n);
    for (int u = 0; u < n; ++u) ini[u] = u;
    sort(ini.begin(), ini.end(), [&](int u, int v) -> bool {
      if (ps[u].x != ps[v].x) return (ps[u].x < ps[v].x);
      if (ps[u].y != ps[v].y) return (ps[u].y > ps[v].y);
      return (u < v);
    });
    for (int u = 0; u < n; ++u) for (int v = 0; v < n; ++v) if (ps[u] != ps[v]) {
      // u,v -> v,u
      Pt dir = Pt(0, 1) * (ps[v] - ps[u]);
      const Int g = __gcd(abs(dir.x), abs(dir.y));
      dir /= g;
      es.push_back(Event{dir, dir.det(ps[u]), dir.det(ps[v]), u, v});
    }
    sort(es.begin(), es.end(), [&](const Event &e0, const Event &e1) -> bool {
      const int s = cmpArg(e0.dir, e1.dir);
      if (s) return (s < 0);
      if (e0.detU != e1.detU) return (e0.detU > e1.detU);
      if (e0.detV != e1.detV) return (e0.detV > e1.detV);
      if (e0.u != e1.u) return (e0.u > e1.u);
      return (e0.v < e1.v);
    });
  }
  friend ostream &operator<<(ostream &os, const DirSorter &dirSorter) {
    os << "ini = " << dirSorter.ini << endl;
    for (const auto &e : dirSorter.es) os << "(" << e.dir << "; " << e.detU << ", " << e.detV << "; " << e.u << ", " << e.v << ")" << endl;
    return os;
  }
};


/*
  (variance of (a, b, c))
  = (variance of (0, x:=b-a, y:=c-a))
  = (2/9) (x^2 - x y + y^2)
  = (2/9) ((x - (1/2) y)^2 + (3/4) y^2)
*/
Int calc(const Pt &a) {
  return a.x*a.x - a.x*a.y + a.y*a.y;
}

int N;
vector<Pt> P;

int main() {
  for (; ~scanf("%d", &N); ) {
    P.resize(N);
    for (int u = 0; u < N; ++u) {
      Int a, b, c;
      scanf("%lld%lld%lld", &a, &b, &c);
      P[u] = Pt(b - a, c - a);
    }
    
    const DirSorter ds(P);
// cerr<<"P = "<<P<<endl;
// cerr<<ds<<endl;
    
    auto us = ds.ini;
    vector<int> su(N, -1);
    vector<Pt> pre(N + 1);
    pre[0] = Pt(0, 0);
    for (int i = 0; i < N; ++i) {
      su[us[i]] = i;
      pre[i + 1] = pre[i] + P[us[i]];
    }
    vector<Int> mxs(N + 1);
    for (int i = 0; i <= N; ++i) {
      mxs[i] = calc(pre[i]);
    }
    for (const auto &e : ds.es) {
      const int u = e.u;
      const int v = e.v;
      const int i = su[u];
      const int j = su[v];
      assert(i + 1 == j);
      chmax(mxs[j], calc(pre[j] = pre[j] - P[u] + P[v]));
      swap(su[u], su[v]);
      swap(us[i], us[j]);
    }
    
    for (int k = 1; k <= N; ++k) {
      Mint ans = mxs[k];
      ans *= 2;
      ans /= 9;
      ans /= Mint(k) * Mint(k);
      printf("%u\n", ans.x);
    }
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
180 0 0
0 180 180
0 0 180

output:

7200
5400
800

result:

ok 3 tokens

Test #2:

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

input:

6
30594 32322 46262
63608 59020 98436
90150 32740 67209
82886 4627 54813
3112 67989 74995
60872 9967 9051

output:

715162883
838096208
930330061
405079896
880764907
526006962

result:

ok 6 tokens

Test #3:

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

input:

144
41472 41434 41317
16965 16900 17440
65702 65688 65497
15829 15900 15359
186620 186555 186425
22130 22030 22145
22995 23022 23320
54430 54525 54770
145816 145739 146046
106008 106083 106073
84481 84531 84306
162468 162563 162313
144375 144342 144210
68596 68548 68201
124014 124100 123649
137878 1...

output:

665561664
166436731
579289313
55518246
226327601
523827415
697242492
166428961
72628719
361639205
499632513
554631323
305233223
309029649
197725655
853581515
286740033
873681088
443094922
905119354
107690174
499165266
848371940
176043988
31275150
39747201
676490856
965461580
788056873
59932649
12538...

result:

ok 144 tokens

Test #4:

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

input:

282
94428 97009 94455
188420 188507 188612
93867 96593 93723
39525 41816 39549
192460 192576 192433
3845 1235 4121
11984 12390 12173
130725 130116 130896
87196 88124 87364
44538 45060 44298
166342 166632 166330
82059 84785 81813
27313 29691 27187
34038 35140 33798
54607 52867 54514
133483 131946 133...

output:

889314432
390117563
692023566
98907387
121626305
562561437
943457514
32985591
579638100
443215860
190588508
100335990
245223619
297117655
983188143
829225394
24317883
294014511
13323940
161909823
702330540
380190451
641303019
179896717
251619007
656550638
566922194
280229585
194457893
858751625
3209...

result:

ok 282 tokens

Test #5:

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

input:

271
153127 153535 152737
23323 22899 22765
34658 35090 35102
105004 105460 105508
137353 137025 137455
123997 123645 123883
11813 12333 11387
144072 144184 144198
190834 190866 191008
134203 134619 133837
160912 160400 161494
120883 121563 120775
183341 182637 183593
111598 112254 111034
34566 35078...

output:

322344
554885983
764388094
286496
120066627
542525190
428080325
887579586
216597238
807704248
412727458
450051205
289652425
201676353
851555207
107659595
407794390
845083057
11262308
601363802
380228455
744523302
119075663
10973283
784763125
915078500
635553912
194849886
439358978
606025095
61708067...

result:

ok 271 tokens

Test #6:

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

input:

300
104842 113680 113680
143955 136043 136043
29866 29080 29080
109288 101080 101080
172820 180722 180722
125104 118195 118195
24448 26967 26967
77313 70147 70147
24553 20285 20285
53114 43843 43843
42094 36323 36323
128136 118936 118936
71217 79147 79147
121620 123061 123061
100792 97508 97508
6721...

output:

909461736
22044800
21938688
909191994
381166451
767341949
684892751
794542288
656904216
460707595
108474983
919416671
87517565
286000639
180810310
793966736
508746481
257745719
464727415
117705770
19553070
874340280
950689183
651506248
866529385
679037134
681710885
712583626
879201340
547702999
5130...

result:

ok 300 tokens

Test #7:

score: 0
Accepted
time: 15ms
memory: 8608kb

input:

300
182375 34340 31299
189896 7463 82920
175804 33229 17728
172428 38589 3152
179561 2042 66285
185751 10962 68975
194517 7716 93141
179439 7380 59163
199426 4435 108550
173662 1057 54086
194638 70081 13462
178554 31065 26778
170726 851 47650
182300 49007 12324
185665 62746 2389
188363 25586 56187
1...

output:

723410220
723410220
723410220
768126446
968000807
978289779
686716556
300986523
23685666
100863542
817903116
368292549
966551585
815525412
775319408
530137969
106128595
713413782
14090737
580333162
736583094
17911566
818088391
284054642
161362307
515282086
487513444
432115986
582112009
211599028
776...

result:

ok 300 tokens

Test #8:

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

input:

300
152843 194847 111534
143276 172558 89245
60327 105984 22671
128676 175881 92568
121633 166382 83069
105658 145368 62055
124729 163074 79761
106430 139071 55758
102353 144000 60687
106582 145138 61825
135534 170455 87142
132677 175622 92309
87838 124176 40863
127763 162661 79348
57824 87301 3988
...

output:

199685421
254923155
408725470
573435441
993166600
778057960
402409983
198533293
620160445
757271783
45914347
559925318
333601004
636739495
779637954
910451416
197133729
719355632
138699036
711225505
662430730
816748658
118604432
106049642
217966163
21164675
626881354
798024734
61816036
866368325
961...

result:

ok 300 tokens

Test #9:

score: 0
Accepted
time: 808ms
memory: 167064kb

input:

2000
46852 76871 93555
109329 4592 117118
85100 78035 166719
9336 156179 29277
93649 191864 9597
139268 193640 103865
65176 45936 22032
140243 24791 33044
190522 37917 165916
129355 113010 72009
90540 120070 180615
161806 63989 192069
137247 149177 120171
10653 20063 85613
97726 10036 38469
159738 1...

output:

667500967
561870818
227733218
708027088
503022645
936956883
568087276
65695301
103966866
777260851
400197479
712392592
452503693
262345617
470045142
723034628
398361563
708274989
151258829
5630611
826259002
935693539
63404055
561026681
692615880
774294332
215173128
420114593
376847155
640103994
5242...

result:

ok 2000 tokens

Test #10:

score: 0
Accepted
time: 826ms
memory: 167736kb

input:

2000
170443 63953 136369
36312 172296 147102
198446 4587 74632
805 90356 106816
173954 30881 37344
182227 148443 159909
113809 89480 7848
143983 38598 106491
154799 94036 142737
177354 38433 113808
173255 69740 24509
144340 100252 150185
99168 90365 106672
165243 19085 56788
3914 147270 126334
11166...

output:

519115744
20818054
931919121
448166710
802187150
689436348
610737054
740967480
769405418
701919817
459762192
432304172
890249278
39760968
141835491
539733077
810070250
739548110
458211345
786753372
812644098
734265883
136199485
708252127
249368949
192021567
285711977
861514987
375908285
781237155
87...

result:

ok 2000 tokens

Test #11:

score: 0
Accepted
time: 819ms
memory: 167704kb

input:

2000
196942 112774 23684
96132 165902 76519
118059 174498 64568
22530 170567 87637
101144 98454 62759
153297 127754 148923
48742 93603 90889
30327 26545 99570
76068 64513 102993
177954 160810 11164
173021 35133 133184
62910 123610 127443
47634 119782 7385
41525 142790 155844
110578 170434 99145
1074...

output:

821579100
641206285
296714257
950855688
393837213
625996113
508099897
946995812
504794481
983069553
266719552
830096464
756046928
282496973
179500990
387833567
375945004
247460194
961546870
486390248
530257362
970875424
517167023
102172769
798700912
315152832
167295601
676740822
124655295
255302607
...

result:

ok 2000 tokens

Test #12:

score: 0
Accepted
time: 834ms
memory: 167300kb

input:

2000
83607 87014 144847
84715 90303 129233
97538 155282 149989
80232 182943 5467
142798 199114 72943
48908 150972 193087
173 109865 158005
112702 148488 167151
12802 180740 78128
94184 40167 136268
159314 142402 112499
3872 98897 17479
190811 12706 101844
86916 110199 120507
63069 61218 118580
19821...

output:

782855787
110218100
809446918
46399567
987431977
587687567
131850149
448361738
892167606
341673483
247030283
67284518
737363184
393422331
344880323
731709131
35570695
32869364
703558419
428702433
912114290
645778415
209818018
615952680
797880149
743607083
707491855
579867883
620473029
777014131
6511...

result:

ok 2000 tokens

Test #13:

score: 0
Accepted
time: 832ms
memory: 168044kb

input:

2000
110222 156207 11992
91886 164550 9223
173234 154982 100089
87574 104925 198900
145962 140588 198879
42024 99665 125470
46162 137364 8984
3153 125610 40916
187311 127998 41049
465 189792 167331
145221 29428 176483
175312 76122 117290
40458 165746 50634
120088 55254 92197
110093 74112 4651
122187...

output:

850421237
165579435
381628722
37256930
936151141
790815877
940851854
556404342
896242125
994825793
934244039
856116956
728097755
381250556
300879456
371172798
962959386
527517555
214758225
935229466
925079984
431884920
399624072
560442420
711431461
39554015
502166206
885547344
583244425
665042385
38...

result:

ok 2000 tokens

Test #14:

score: 0
Accepted
time: 724ms
memory: 168648kb

input:

1910
116449 116505 116653
15080 15080 14831
74284 74252 74419
111807 111583 111684
57104 57412 57290
170401 170209 170539
75454 75566 75208
92202 91986 92097
101155 101399 101440
40361 40505 40553
1268 1320 1115
91224 91108 91275
84071 84183 84014
28490 28126 28538
141584 141672 141542
63790 63954 6...

output:

887410536
499201647
468390712
429877677
439305099
838108486
387149315
315491413
985993266
315073599
763650337
787266365
54543523
782140636
654719978
328483879
234565245
338977770
905830438
20031907
471397020
185690391
732028155
579294045
247452666
543488142
756697861
886261061
834506321
295100625
81...

result:

ok 1910 tokens

Test #15:

score: 0
Accepted
time: 352ms
memory: 86144kb

input:

1382
149836 149822 149806
98176 98079 98276
16369 16408 16430
161298 161291 161323
168221 168155 168266
1607 1524 1683
4524 4475 4520
67387 67315 67441
185186 185274 185133
164468 164410 164560
178259 178176 178191
194509 194435 194541
19595 19579 19505
159548 159504 159459
84559 84637 84654
132785 ...

output:

665502902
887334848
628530539
596179839
168598384
720960177
991459430
13870302
602512632
845185917
620585471
961277942
588713767
164115987
920855090
481796998
796374907
137623442
825884350
859050061
30941075
158587717
353301143
702858600
981567781
747211746
306127332
247868519
34031664
718248055
607...

result:

ok 1382 tokens

Test #16:

score: 0
Accepted
time: 193ms
memory: 45660kb

input:

1000
81054 81128 81002
166650 166516 166697
98097 98253 98128
3315 3335 3267
2645 2737 2557
14753 14677 14784
59851 59769 59760
67967 68147 67963
160563 160631 160464
173452 173536 173398
23214 23098 23283
92147 92037 92171
113694 113838 113760
172232 172144 172169
163544 163370 163512
48588 48588 4...

output:

554595223
221846780
295790698
55472559
940582444
24662362
896396932
856147255
877756905
893997057
142096173
720967784
129962350
682486408
247972063
775558714
102101672
241015510
966917851
867375990
156703401
702633446
623784031
873861223
643147782
650741448
925225281
138374091
823243682
730578820
50...

result:

ok 1000 tokens

Test #17:

score: 0
Accepted
time: 622ms
memory: 168048kb

input:

2000
156741 146881 146881
99950 107879 107879
157059 148825 148825
10891 13215 13215
44539 51026 51026
36388 38203 38203
134774 133471 133471
140086 132182 132182
108884 114833 114833
121242 123564 123564
199398 199322 199322
127241 132177 132177
174168 165099 165099
172465 180872 180872
143392 1438...

output:

244032084
410359524
564382222
243952196
660984976
527365883
488351840
895492012
576589597
261567704
356551855
217590722
168936040
358045305
461110597
506256749
373787423
729096441
820967449
549759711
9454529
82714195
225324035
882852024
64106031
314384486
859067842
315600189
499807660
263604293
5014...

result:

ok 2000 tokens

Test #18:

score: 0
Accepted
time: 790ms
memory: 168068kb

input:

2000
18300 57191 190295
12158 137354 65253
18791 61050 186146
70332 146271 191287
85377 197522 156452
24460 177863 38695
33379 139630 112574
17856 53379 194491
78128 155751 196763
42260 104306 182355
42286 110226 174261
73723 172396 163358
73641 192943 134856
52473 114098 193148
3572 27307 196447
46...

output:

25254561
25254561
25254561
25254561
305218667
299614421
384800604
825014522
355193740
239867203
987498480
359277577
959362450
692178032
279777802
850821223
842347399
348400937
896732248
528022465
771015067
752685674
267120432
713085481
917831744
832099950
982482304
922682018
938878966
78290683
91299...

result:

ok 2000 tokens

Test #19:

score: 0
Accepted
time: 603ms
memory: 169108kb

input:

2000
182291 42889 186548
186766 45842 189501
195575 46743 190402
182587 34032 177691
151093 13138 156797
160998 12286 155945
186735 34378 178037
165416 29135 172794
196044 48771 192430
195004 40885 184544
193554 52895 196554
188824 49596 193255
188146 42460 186119
167338 21863 165522
174506 37071 18...

output:

510472346
122247906
793826833
621205363
669927894
676462071
842744629
589639641
541226869
343164990
595537232
390575931
707897925
950288829
2967920
227863535
985541793
9209505
667651189
840805465
475977947
367072176
273646130
920283667
423648899
758050074
45633855
238051170
752059829
756822578
64486...

result:

ok 2000 tokens

Test #20:

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

input:

10
0 0 200000
100000 0 200000
100000 0 200000
0 0 200000
200000 200000 0
200000 0 0
200000 200000 0
200000 0 200000
0 0 200000
100000 0 200000

output:

459269908
459269908
459269908
596208078
146208078
123595712
374197620
778441137
462607578
979143281

result:

ok 10 tokens

Test #21:

score: 0
Accepted
time: 1ms
memory: 3832kb

input:

30
20202 183160 117360
102695 23158 13538
10110 173068 107268
4817 167775 101975
145646 66109 56489
179930 4341 18909
16151 179109 113309
29146 192104 126304
6699 169657 103857
1361 63430 28854
99909 20372 10752
99791 184495 195232
26741 189699 123899
78083 127382 20214
38599 176716 12280
124280 447...

output:

562531070
562531070
562531070
209688629
111968436
43872512
43872512
43872512
43872512
922560746
137748221
508796019
91639026
117080583
707790124
928629583
231973873
474963192
46412700
284588347
343866886
254578930
581705385
376773694
849470566
402564046
230979911
936492416
789870295
260124876

result:

ok 30 tokens

Test #22:

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

input:

155
146635 186686 2719
60847 35024 186006
56120 116063 167445
192132 32460 181465
157404 197455 13488
27965 2142 153124
58176 118119 169501
150432 190483 6516
37171 97114 148496
35112 95055 146437
19265 197223 146962
50324 110267 161649
76278 136221 187603
2474 180432 130171
156200 196251 12284
1566...

output:

472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
472338710
...

result:

ok 155 tokens

Test #23:

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

input:

1147
200000 200000 0
0 200000 0
0 0 200000
200000 200000 0
200000 200000 0
0 200000 0
0 200000 0
200000 0 200000
200000 0 200000
100000 200000 0
200000 0 200000
200000 0 200000
200000 0 0
0 200000 0
200000 200000 0
200000 0 200000
0 200000 0
200000 0 200000
200000 0 0
100000 0 200000
200000 0 200000...

output:

459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
...

result:

ok 1147 tokens

Test #24:

score: 0
Accepted
time: 587ms
memory: 167712kb

input:

1911
132757 24041 12803
184362 75022 55237
164872 56440 136824
162636 53296 33511
6312 107723 44083
96124 197535 133895
141708 32368 12583
194053 84713 64928
79839 181250 117610
111485 3053 83437
90075 191486 127846
52075 153486 89846
130701 21361 1576
182080 72740 52955
169072 60640 141024
21942 12...

output:

128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
128461641
...

result:

ok 1911 tokens

Test #25:

score: 0
Accepted
time: 246ms
memory: 85636kb

input:

1267
91713 102012 162268
118610 128909 189165
14079 24378 84634
79453 89658 199717
156872 198765 11561
140964 1164 157087
179342 173699 17169
193598 187955 31425
9922 20221 80477
7887 18186 78442
48456 58661 168720
10489 20788 81044
70682 80887 190946
3052 13351 73607
168991 29191 185114
39111 49316...

output:

334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
334689819
...

result:

ok 1267 tokens

Test #26:

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

input:

2
6556 194393 72097
64196 58513 36579

output:

957270292
763048903

result:

ok 2 tokens

Test #27:

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

input:

2
177392 194161 142964
22790 154794 110604

output:

902496445
669436299

result:

ok 2 tokens

Test #28:

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

input:

2
7811 24561 57314
60990 132475 157815

output:

571650880
960238449

result:

ok 2 tokens

Test #29:

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

input:

2
147127 52124 187700
170363 183848 142853

output:

122416470
493274460

result:

ok 2 tokens

Test #30:

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

input:

8
57787 117757 154472
72926 1703 198916
41853 183013 110785
89194 72842 40758
56443 88236 26793
24312 99595 25353
94104 90165 158263
69342 11390 191294

output:

215665636
298537043
824400151
203976991
658402539
828528475
697146074
434476186

result:

ok 8 tokens

Test #31:

score: 0
Accepted
time: 18ms
memory: 8836kb

input:

300
120435 140568 32722
99230 20656 144714
76854 164794 162141
94800 151349 50407
184699 18233 12012
173346 59742 75861
20916 61024 26476
99647 72869 118858
166640 95638 42638
97040 93132 54921
175682 69986 183977
179187 169878 18717
159680 166455 44862
140021 191136 64175
42834 121178 99471
70765 1...

output:

455061855
54017169
80792773
965412473
703712612
301195650
214581923
426837627
717248231
612782084
697726316
900344528
617675349
406377208
636012252
620792667
710055507
365747294
274003937
14054467
972680478
787751165
990653784
504974293
955982495
792506791
280643512
273110753
259071822
892527478
485...

result:

ok 300 tokens

Test #32:

score: 0
Accepted
time: 14ms
memory: 9032kb

input:

300
82719 31340 194741
140473 199803 180922
48535 50211 56723
193620 126929 72482
189945 154556 199283
137530 156445 74186
26352 50886 77659
59633 94602 47039
79237 3708 185602
140020 33182 71909
11931 14293 145059
76581 182823 33103
167213 197339 128680
26892 3215 150487
74537 123049 125492
115466 ...

output:

773153416
963385731
471757267
439658912
622415736
427829911
294380777
247319497
155579862
255655203
249509554
427265335
414266563
680403458
172946130
703156797
823601045
131128483
588711240
337720211
17811755
738790586
810582620
420657526
300906184
575415527
204652699
252628412
926069774
816076589
4...

result:

ok 300 tokens

Test #33:

score: 0
Accepted
time: 15ms
memory: 8840kb

input:

300
195508 89001 58083
87311 44074 20022
133820 165996 29891
139094 133680 50830
91586 92038 190678
169199 38716 61936
26949 38389 67100
51713 45481 157915
40073 199285 199007
171837 19753 46437
164613 129529 121622
197773 147779 199197
151904 117677 178555
147978 168556 166539
163714 84727 164421
8...

output:

76589657
194094839
412539464
455865425
67516399
446296275
662704604
649689078
860683041
688444244
38481783
118381838
293448978
353130006
132568232
622661089
354624751
972917858
495934019
940922394
214918370
669238176
71150842
591377055
303610770
983363191
799070353
774529739
107638346
893771009
7547...

result:

ok 300 tokens

Test #34:

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

input:

141
38715 31363 164126
39131 31779 164542
14005 6653 139416
36931 29579 162342
37870 30518 163281
14232 6880 139643
20485 13133 145896
61524 54172 186935
50644 43292 176055
69270 61918 194681
20530 13178 145941
25370 18018 150781
8031 679 133442
28053 20701 153464
60686 53334 186097
69702 62350 1951...

output:

384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
384517156
...

result:

ok 141 tokens

Test #35:

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

input:

18
63579 95502 35501
138273 170196 110195
126240 158163 98162
128342 160265 100264
145659 177582 117581
127036 158959 98958
126551 158474 98473
49115 81038 21037
62940 94863 34862
119243 151166 91165
59176 91099 31098
74863 106786 46785
131115 163038 103037
166710 198633 138632
61461 93384 33383
864...

output:

157177178
157177178
157177178
157177178
157177178
157177178
157177178
157177178
157177178
157177178
157177178
157177178
157177178
157177178
157177178
157177178
157177178
157177178

result:

ok 18 tokens

Test #36:

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

input:

154
111182 166362 178315
99425 154605 166558
60205 115385 127338
64883 120063 132016
120750 175930 187883
90743 145923 157876
40664 95844 107797
72259 127439 139392
49409 104589 116542
29581 84761 96714
8445 63625 75578
109901 165081 177034
4101 59281 71234
63089 118269 130222
54023 109203 121156
17...

output:

522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
522201471
...

result:

ok 154 tokens

Test #37:

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

input:

1898
97681 191495 62810
59080 152894 24209
102251 196065 67380
42441 136255 7570
36167 129981 1296
59662 153476 24791
50296 144110 15425
94074 187888 59203
101199 195013 66328
66965 160779 32094
85983 179797 51112
68468 162282 33597
67075 160889 32204
45711 139525 10840
90972 184786 56101
99417 1932...

output:

845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
845582195
...

result:

ok 1898 tokens

Test #38:

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

input:

1793
188942 109119 110108
133478 53655 54644
94066 14243 15232
169662 89839 90828
120805 40982 41971
167388 87565 88554
180020 100197 101186
161241 81418 82407
154648 74825 75814
173594 93771 94760
159922 80099 81088
120597 40774 41763
115230 35407 36396
176103 96280 97269
98391 18568 19557
133967 5...

output:

622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
622197615
...

result:

ok 1793 tokens

Test #39:

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

input:

1789
98115 168665 158835
53846 124396 114566
96317 166867 157037
26305 96855 87025
43633 114183 104353
15871 86421 76591
61019 131569 121739
40974 111524 101694
64891 135441 125611
26740 97290 87460
41101 111651 101821
127515 198065 188235
99129 169679 159849
8910 79460 69630
107167 177717 167887
67...

output:

197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
197015481
...

result:

ok 1789 tokens

Test #40:

score: 0
Accepted
time: 1ms
memory: 3784kb

input:

300
200000 200000 0
200000 200000 0
200000 200000 0
200000 200000 0
200000 200000 0
200000 200000 0
200000 200000 0
200000 200000 0
200000 200000 0
200000 200000 0
200000 200000 0
200000 200000 0
200000 200000 0
200000 200000 0
200000 200000 0
200000 200000 0
200000 200000 0
200000 200000 0
200000 2...

output:

459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
...

result:

ok 300 tokens

Test #41:

score: 0
Accepted
time: 1ms
memory: 4044kb

input:

300
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0
200000 0 0...

output:

459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
...

result:

ok 300 tokens

Test #42:

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

input:

2000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 200000
0 0 20000...

output:

459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
459269908
...

result:

ok 2000 tokens

Test #43:

score: 0
Accepted
time: 1ms
memory: 3920kb

input:

300
200000 100000 0
200000 100000 0
200000 100000 0
200000 100000 0
200000 100000 0
200000 100000 0
200000 100000 0
200000 100000 0
200000 100000 0
200000 100000 0
200000 100000 0
200000 100000 0
51516 56203 51516
200000 100000 0
200000 100000 0
200000 100000 0
200000 100000 0
200000 100000 0
200000...

output:

344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
...

result:

ok 300 tokens

Test #44:

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

input:

300
99998 200000 0
100001 200000 0
99998 200000 0
99998 200000 0
100001 200000 0
99998 200000 0
100001 200000 0
100001 200000 0
99998 200000 0
99998 200000 0
99998 200000 0
99998 200000 0
100001 200000 0
100001 200000 0
100001 200000 0
100001 200000 0
100000 0 200000
100001 200000 0
99998 200000 0
1...

output:

899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
...

result:

ok 300 tokens

Test #45:

score: 0
Accepted
time: 1ms
memory: 3908kb

input:

300
0 200000 100000
0 200000 100000
0 200000 100000
0 200000 100000
0 200000 100000
0 200000 100000
0 200000 100000
0 200000 100000
0 200000 100000
0 200000 100000
0 200000 100000
0 200000 100000
0 200000 100000
0 200000 100000
0 200000 100000
0 200000 100000
0 200000 100000
0 200000 100000
0 200000...

output:

344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
...

result:

ok 300 tokens

Test #46:

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

input:

300
0 200000 99999
0 200000 99999
0 200000 99999
0 200000 99999
0 200000 99999
0 200000 99999
71081 71081 75768
0 200000 100002
0 200000 100002
0 200000 99999
0 200000 99999
0 200000 99999
0 200000 99999
0 200000 99999
0 200000 99999
0 200000 99999
0 200000 99999
0 200000 99999
0 200000 99999
0 2000...

output:

899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
...

result:

ok 300 tokens

Test #47:

score: 0
Accepted
time: 1ms
memory: 3900kb

input:

300
0 99935 200000
0 99935 200000
0 99935 200000
0 99935 200000
0 99935 200000
0 99935 200000
0 99935 200000
0 99935 200000
0 99935 200000
0 99935 200000
0 99935 200000
70064 66664 70063
0 99935 200000
0 99935 200000
0 99935 200000
0 99935 200000
0 99935 200000
0 99935 200000
0 99935 200000
0 99935 ...

output:

899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
...

result:

ok 300 tokens

Test #48:

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

input:

300
0 200000 99933
0 200000 99936
0 200000 99936
0 200000 99936
0 200000 99936
0 200000 99936
0 200000 99936
0 200000 99936
0 200000 99936
0 200000 99936
0 200000 99936
0 200000 99936
0 200000 99933
0 200000 99936
0 200000 99933
0 200000 99936
0 200000 99936
0 200000 99933
0 200000 99936
0 200000 99...

output:

566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
...

result:

ok 300 tokens

Test #49:

score: 0
Accepted
time: 1ms
memory: 3888kb

input:

300
99935 200000 0
99935 200000 0
99935 200000 0
99935 200000 0
99935 200000 0
99935 200000 0
99935 200000 0
99935 200000 0
99935 200000 0
99935 200000 0
99935 200000 0
99935 200000 0
99935 200000 0
99935 200000 0
99935 200000 0
99935 200000 0
99935 200000 0
99935 200000 0
99935 200000 0
99935 20000...

output:

899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
899033566
...

result:

ok 300 tokens

Test #50:

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

input:

300
99933 0 200000
99936 0 200000
99933 0 200000
99936 0 200000
99933 0 200000
99936 0 200000
99936 0 200000
99936 0 200000
99936 0 200000
99936 0 200000
99936 0 200000
99936 0 200000
99936 0 200000
99933 0 200000
99936 0 200000
99933 0 200000
99936 0 200000
99936 0 200000
99936 0 200000
99936 0 200...

output:

566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
566285507
...

result:

ok 300 tokens

Test #51:

score: 0
Accepted
time: 16ms
memory: 10616kb

input:

300
101792 74 199943
101769 99 199930
101685 1 199871
101804 31 199971
101668 16 199986
101819 67 199991
101817 100 199943
101694 25 199912
101818 17 199961
101772 44 199924
101786 53 199969
101699 44 199962
101680 7 199983
101733 41 199905
101849 47 199976
101656 15 199816
101731 26 199968
101757 1...

output:

566871977
67745419
369680233
968899448
384891762
591402873
851938145
566698401
614602908
480143891
89062336
709896541
21225384
495300654
922509317
563113115
900466897
704171463
818175158
959170084
34319237
501877843
23651086
400488300
408873809
349540643
704131032
857576721
167188448
425405821
59684...

result:

ok 300 tokens

Test #52:

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

input:

300
199942 119 103043
13 199929 96901
199889 60 102987
199927 57 103054
199932 71 103033
199983 93 103120
63 199977 97045
199963 1 102976
199954 32 103044
199935 20 103046
199999 29 103128
199983 107 103037
199977 10 103099
199979 28 103097
3 199939 97000
199942 10 102959
106 199990 96997
199963 37 ...

output:

901059722
901034850
740808205
221645722
262104134
919447961
296565987
127983526
431233447
925304643
631391580
537318116
915302704
761642038
586822021
335843370
361194712
348266871
297347274
865828492
59953789
389241748
206502957
457431482
884193671
142322469
896110112
299396763
203504040
818564886
4...

result:

ok 300 tokens

Test #53:

score: 0
Accepted
time: 16ms
memory: 10348kb

input:

300
199960 44 102583
199958 5 102624
199984 120 102697
199934 61 102626
199989 34 102544
199997 278 102741
199937 24 102645
199946 39 102606
199928 15 102595
199995 118 102738
199934 145 102656
199999 21 102630
199873 32 102503
199995 23 102556
199963 52 102647
199997 31 102572
199889 50 102589
1998...

output:

346001231
401344911
777188128
442867371
913662503
93100973
19753201
785881257
73146662
347814969
337292480
567321807
262744201
781136694
358171303
525556434
20595385
156959855
531398149
545376394
401479735
528443449
843051580
89711847
404114590
786356012
552486101
774722423
235690347
314052718
17055...

result:

ok 300 tokens

Test #54:

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

input:

300
103179 199985 29
103188 199828 163
103271 199956 147
96920 188 199974
103206 199896 62
103177 199926 15
103077 199775 23
103196 199905 142
103069 199828 32
103186 199980 6
96880 203 199951
103139 199965 90
96767 67 199932
103155 199836 107
96768 18 199974
103149 199974 93
96681 22 199789
96817 3...

output:

346643577
734752195
531097750
734203656
194949157
129949928
798201697
556807490
697174822
405040111
3133268
503633632
68573964
545128855
573464713
491105694
120068172
112417166
350594821
165257636
778183980
727896318
724563071
447376799
108610214
349959994
186070859
896549821
276244928
318218037
267...

result:

ok 300 tokens

Test #55:

score: 0
Accepted
time: 16ms
memory: 9036kb

input:

300
94787 199975 181
94838 199980 94
94618 199895 23
94663 199947 12
94715 199966 46
94752 199977 21
94681 199969 14
94750 199869 96
94789 199950 14
94621 199821 25
94718 199976 25
94696 199928 86
94672 199979 39
94747 199876 137
94757 199920 123
94827 199981 58
94769 199992 93
94753 199871 140
9475...

output:

572264467
572224687
301059971
780123843
92962157
726118401
225698202
291237191
377515245
691715078
878057061
490214624
386751077
962269369
229658259
371580037
204821093
584711219
546178212
5431904
634760420
901597009
79882454
977055634
127992480
167812436
785782218
723311655
140855759
88439952
20700...

result:

ok 300 tokens

Test #56:

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

input:

300
38 199803 96358
30 199931 96313
148083 146621 149643
6 199857 96380
66 199894 96388
221 199985 96508
145 199976 96521
9 199971 96380
38 199910 96438
23 199919 96306
31 199972 96444
199994 13 103587
55 199949 96392
199917 53 103631
35 199956 96329
199985 108 103575
44 199851 96354
85 199913 96454...

output:

236472664
180945475
643024449
693764804
639912537
852327058
371903400
735166709
464682109
788324118
227659685
755010755
684728282
974829385
670019177
713136150
189574536
667605460
979375667
370244706
524164048
157007112
686965430
5752814
310308835
653592966
947056723
745271685
43969925
838661886
486...

result:

ok 300 tokens

Test #57:

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

input:

2000
200000 0 100000
200000 0 100000
200000 0 100000
200000 0 100000
200000 0 100000
200000 0 100000
200000 0 100000
200000 0 100000
200000 0 100000
200000 0 100000
200000 0 100000
200000 0 100000
200000 0 100000
200000 0 100000
200000 0 100000
200000 0 100000
200000 0 100000
200000 0 100000
200000 ...

output:

344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
...

result:

ok 2000 tokens

Test #58:

score: 0
Accepted
time: 202ms
memory: 86552kb

input:

2000
100001 200000 0
100001 200000 0
99998 200000 0
100001 200000 0
99998 200000 0
100001 200000 0
100001 200000 0
100001 200000 0
99998 200000 0
100001 200000 0
100001 200000 0
100001 200000 0
100001 200000 0
100001 200000 0
100001 200000 0
99998 200000 0
99998 200000 0
100001 200000 0
100001 20000...

output:

899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
...

result:

ok 2000 tokens

Test #59:

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

input:

2000
100000 0 200000
100000 0 200000
100000 0 200000
100000 0 200000
100000 0 200000
100000 0 200000
100000 0 200000
100000 0 200000
100000 0 200000
100000 0 200000
100000 0 200000
100000 0 200000
100000 0 200000
100000 0 200000
100000 0 200000
100000 0 200000
100000 0 200000
100000 0 200000
100000 ...

output:

344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
344452431
...

result:

ok 2000 tokens

Test #60:

score: 0
Accepted
time: 261ms
memory: 86584kb

input:

2000
200000 0 99999
200000 0 100002
200000 0 100002
200000 0 99999
200000 0 100002
200000 0 99999
200000 0 100002
200000 0 100002
200000 0 99999
200000 0 100002
200000 0 100002
200000 0 99999
200000 0 99999
200000 0 100002
200000 0 100002
200000 0 99999
200000 0 99999
200000 0 99999
200000 0 99999
2...

output:

899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
899032628
...

result:

ok 2000 tokens

Test #61:

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

input:

2000
0 200000 100025
0 200000 100025
0 200000 100025
0 200000 100025
0 200000 100025
0 200000 100025
0 200000 100025
0 200000 100025
0 200000 100025
0 200000 100025
0 200000 100025
0 200000 100025
0 200000 100025
0 200000 100025
0 200000 100025
0 200000 100025
0 200000 100025
0 200000 100025
0 20000...

output:

899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
...

result:

ok 2000 tokens

Test #62:

score: 0
Accepted
time: 258ms
memory: 87348kb

input:

2000
0 200000 100024
0 200000 100027
0 200000 100024
0 200000 100024
0 200000 100024
0 200000 100027
0 200000 100027
0 200000 100024
0 200000 100024
0 200000 100024
0 200000 100024
0 200000 100024
0 200000 100024
0 200000 100024
0 200000 100027
0 200000 100024
0 200000 100024
0 200000 100024
0 20000...

output:

344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
...

result:

ok 2000 tokens

Test #63:

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

input:

2000
99975 200000 0
99975 200000 0
99975 200000 0
99975 200000 0
99975 200000 0
99975 200000 0
99975 200000 0
99975 200000 0
99975 200000 0
99975 200000 0
99975 200000 0
99975 200000 0
99975 200000 0
99975 200000 0
99975 200000 0
99975 200000 0
99975 200000 0
99975 200000 0
99975 200000 0
99975 2000...

output:

899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
899032766
...

result:

ok 2000 tokens

Test #64:

score: 0
Accepted
time: 199ms
memory: 86580kb

input:

2000
0 100024 200000
0 100024 200000
0 100024 200000
0 100024 200000
0 100024 200000
0 100024 200000
0 100024 200000
80955 89954 80954
0 100027 200000
0 100024 200000
0 100024 200000
0 100027 200000
200000 99975 0
0 100027 200000
0 100024 200000
0 100027 200000
0 100024 200000
0 100024 200000
0 1000...

output:

344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
344452593
...

result:

ok 2000 tokens

Test #65:

score: 0
Accepted
time: 787ms
memory: 168180kb

input:

2000
112451 11 199982
112560 104 199963
112494 27 199964
112542 17 199953
112440 9 199928
112562 16 199964
112427 0 199825
112484 24 199929
112584 96 199993
112526 3 199999
112551 73 199961
112523 40 199997
112542 3 199928
112554 114 199994
112579 0 200000
112551 3 199995
112574 19 199988
112573 44 ...

output:

379631703
379631703
268710072
60723735
494948127
958799484
350124466
535510168
928621806
199821412
975323831
268567960
451668287
156498735
65435744
278923625
879896991
986037410
28845492
914021158
631914737
311100213
707519894
306974514
861723381
680939238
150072818
987412518
951734563
219871788
544...

result:

ok 2000 tokens

Test #66:

score: 0
Accepted
time: 879ms
memory: 167464kb

input:

2000
199890 102053 64
1 97861 199995
199939 102082 2
199986 102200 117
199940 102173 132
19 97837 199965
199938 102006 32
199903 102015 22
199967 102148 26
199978 102209 194
199999 102073 81
199977 102136 164
22 97892 199981
199905 102064 46
199888 102048 1
199954 102098 8
199970 102013 13
199901 10...

output:

900054124
567291763
148263665
719780987
553952902
684334692
675902447
438997219
804132640
485153372
653389665
969286202
93354101
20543750
295079009
777751205
435151251
571960110
381275468
81340372
727106463
886136239
792317633
488557340
853544649
333461531
265237547
483056039
785487441
193906370
623...

result:

ok 2000 tokens

Test #67:

score: 0
Accepted
time: 776ms
memory: 168796kb

input:

2000
99 199997 98340
177 199927 98398
37 199978 98296
127 199853 98318
90 199946 98413
23 199894 98241
11 199928 98226
65 199911 98211
24 199911 98236
223 199961 98349
35 199829 98315
18 199799 98179
48 199712 98173
91 199839 98287
88 199919 98395
62 199883 98326
119 199828 98316
118 199939 98257
6 ...

output:

899600274
733199092
640760025
358839756
340519702
166245427
351717336
618737361
976165786
604433059
723459782
404941591
64600956
899403660
291072626
660206583
177437329
981488864
722333966
857693011
490814350
554122938
188021734
913455493
761828024
615314042
677164855
637686403
483406914
857679234
9...

result:

ok 2000 tokens

Test #68:

score: 0
Accepted
time: 873ms
memory: 168876kb

input:

2000
199885 85 98540
199990 63 98512
199984 36 98466
199926 38 98534
41 199869 101409
199957 39 98626
16 199999 101531
199904 20 98527
68 199949 101542
199934 60 98562
4 199906 101490
199997 46 98491
199933 40 98476
199922 59 98512
45 199938 101495
80 199998 101588
199961 2 98589
199968 121 98622
79...

output:

234043752
344944463
110778292
192416673
225128474
733118094
915331429
473147526
343526798
5488881
386137662
4433291
816765190
701391830
944804754
337068717
966222856
568743615
535652586
694787685
521151550
538712246
548634573
493873205
371977786
516446050
110661634
101477900
734401241
325827715
8199...

result:

ok 2000 tokens

Test #69:

score: 0
Accepted
time: 766ms
memory: 167184kb

input:

2000
96957 53 199991
96868 0 199765
96998 225 199969
96960 36 199986
96993 64 199966
96967 16 199886
96959 101 199985
96878 53 199947
96944 1 199997
96779 9 199723
96877 18 199769
96990 49 199880
96884 91 199812
96933 103 199839
97034 97 199921
96934 88 199892
96890 31 199781
96939 31 199944
96836 4...

output:

568372115
679148016
223102947
179930944
754429021
851510838
955110306
308058568
761077364
206383518
367195054
851373426
493737582
605231409
33988180
820006742
988465751
348035958
335829084
959875936
165359383
337682364
155120755
166827325
852209558
575269644
823625893
380106336
817085814
323909061
5...

result:

ok 2000 tokens

Test #70:

score: 0
Accepted
time: 816ms
memory: 167332kb

input:

2000
2 99319 199888
26 99293 199951
118 99392 199933
22 99322 199868
29 99310 199954
35 99420 199974
4 99289 199980
1 99412 199937
25 99306 199932
34 99464 199989
30 99356 199923
29 99292 199983
15 99385 199935
199997 100705 18
27 99438 200000
84 99374 199944
26 99329 199993
10 99466 199997
199919 1...

output:

899138734
400015180
332232496
774354612
184832971
566381897
484890015
368802885
359596730
426606763
679105684
299845537
249351748
793835991
453946255
913816875
292688870
98701066
924881262
938443669
578892109
812436664
899057410
116864787
54136625
287695436
334724145
779916119
113257444
41525544
865...

result:

ok 2000 tokens

Extra Test:

score: 0
Extra Test Passed