QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#448455#8525. Mercenaries2745518585WA 943ms895784kbC++205.2kb2024-06-19 17:06:322024-06-19 17:06:35

Judging History

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

  • [2024-06-19 17:06:35]
  • 评测
  • 测评结果:WA
  • 用时:943ms
  • 内存:895784kb
  • [2024-06-19 17:06:32]
  • 提交

answer

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
inline char gc()
{
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
template<typename T> inline void read(T &x)
{
    T u=1,t=0;char c=gc();
    while(c<'0'||c>'9') {if(c=='-') u=-1; c=gc();}
    while(c>='0'&&c<='9') t*=10,t+=c-'0',c=gc();
    x=u*t;return;
}
template<typename T,typename ...O> inline void read(T &x,O &...o) {read(x),read(o...);}
template<typename T> inline void print(T x)
{
    if(x==0) return putchar('0'),void();
    if(x<0) putchar('-'),x=-x;
    int c[129]={0},k=0;
    while(x) c[++k]=x%10,x/=10;
    for(int i=k;i;--i) putchar(c[i]+'0');
}
template<typename T,typename ...O> inline void print(T x,O ...o) {print(x),putchar(' '),print(o...);}
const int N=2000001;
int n,m,c[N],e[N],p[N];
struct pt
{
    ll x,y;
    pt():x(0),y(0) {}
    pt(ll x,ll y):x(x),y(y) {}
    friend pt operator+(const pt &a,const pt &b)
    {
        return pt(a.x+b.x,a.y+b.y);
    }
    friend pt operator-(const pt &a,const pt &b)
    {
        return pt(a.x-b.x,a.y-b.y);
    }
    friend ll operator^(const pt &a,const pt &b)
    {
        return a.x*b.y-a.y*b.x;
    }
    friend bool operator<(const pt &a,const pt &b)
    {
        if(a.x!=b.x) return a.x<b.x;
        return a.y<b.y;
    }
}a[N];
struct str
{
    ll a,b,w;
    ll operator()(const pt &p)
    {
        return a*p.x+b*p.y;
    }
}d[N];
vector<pt> b[N];
vector<pt> solve(const vector<pt> &a)
{
    vector<pt> p;
    for(auto i:a)
    {
        while(p.size()>1&&((p[p.size()-2]-p[p.size()-1])^(p[p.size()-1]-i))>=0) p.pop_back();
        p.push_back(i);
    }
    return p;
}
vector<pt> merge(const vector<pt> &a,const vector<pt> &b)
{
    vector<pt> p;
    p.push_back(pt(0,max(a[0].y,b[0].y)));
    int x1=0,x2=0;
    while(x1+1<a.size()||x2+1<b.size())
    {
        if(x1+1<a.size()&&(x2+1==b.size()||((a[x1]-a[x1+1])^(b[x2]-b[x2+1]))<=0)) ++x1,p.push_back(p.back()+(a[x1]-a[x1-1]));
        else ++x2,p.push_back(p.back()+(b[x2]-b[x2-1]));
    }
    return p;
}
vector<pt> max(const vector<pt> &a,const vector<pt> &b)
{
    vector<pt> p;
    p.push_back(pt(0,max(a[0].y,b[0].y)));
    int x1=0,x2=0;
    while(x1+1<a.size()||x2+1<b.size())
    {
        if(x1+1<a.size()&&(x2+1==b.size()||a[x1+1].x<=b[x2+1].x))
        {
            p.push_back(a[++x1]);
            if(x2+1<b.size()&&p.back().x==b[x2+1].x) p.back().y=std::max(p.back().y,b[++x2].y);
        }
        else p.push_back(b[++x2]);
    }
    return solve(p);
}
bool find(const vector<pt> &p,int &t,str k)
{
    while(t+1<p.size()&&k(p[t])<=k(p[t+1])) ++t;
    return k(p[t])>=k.w;
}
namespace sgt
{
    struct tree
    {
        int l,r,ts,tw;
        vector<pt> s,w;
    }T[N<<2];
    void pushup(int x)
    {
        T[x].w=merge(T[x<<1].w,T[x<<1|1].w);
        T[x].s=max(merge(T[x<<1].s,T[x<<1|1].w),T[x<<1|1].s);
    }
    void build(int x,int l,int r)
    {
        T[x].l=l,T[x].r=r;
        if(l==r)
        {
            T[x].s={pt(0,0),a[l]};
            T[x].w={pt(0,0)};
            for(auto i:b[l]) T[x].w.push_back(i);
            T[x].s=solve(T[x].s);
            T[x].w=solve(T[x].w);
            // printf("%d %d:\n",l,r);
            // for(auto i:T[x].s) printf("(%lld,%lld) ",i.x,i.y);printf("\n");
            // for(auto i:T[x].w) printf("(%lld,%lld) ",i.x,i.y);printf("\n");
            return;
        }
        int z=l+r>>1;
        build(x<<1,l,z);
        build(x<<1|1,z+1,r);
        pushup(x);
        // printf("%d %d:\n",l,r);
        // for(auto i:T[x].s) printf("(%lld,%lld) ",i.x,i.y);printf("\n");
        // for(auto i:T[x].w) printf("(%lld,%lld) ",i.x,i.y);printf("\n");
    }
    int sum(int x,int r,str &k)
    {
        if(T[x].r<=r&&!find(T[x].s,T[x].ts,k))
        {
            find(T[x].w,T[x].tw,k);
            k.w-=k(T[x].w[T[x].tw]);
            return 0;
        }
        if(T[x].l==T[x].r) return T[x].l;
        int z=T[x].l+T[x].r>>1;
        if(r>z)
        {
            int p=sum(x<<1|1,r,k);
            if(p) return p;
        }
        return sum(x<<1,r,k);
    }
}
bool cmp(int x,int y)
{
    if(d[x].a*d[y].b==d[y].a*d[x].b) return d[x].a+d[x].b>d[y].a+d[y].b;
    return d[x].a*d[y].b<d[y].a*d[x].b;
}
int main()
{
    read(n);
    for(int i=1;i<=n;++i)
    {
        if(i>1)
        {
            int k;
            read(k);
            for(int j=1;j<=k;++j)
            {
                ll x,y;
                read(x,y);
                b[i].push_back(pt(x,y));
            }
            sort(b[i].begin(),b[i].end());
        }
        read(a[i].x,a[i].y);
    }
    read(m);
    for(int i=1;i<=m;++i)
    {
        read(c[i],d[i].a,d[i].b,d[i].w);
    }
    if(a[2].y==0) printf("%d %lld %lld %lld",c[1],d[1].a,d[1].b,d[1].w),exit(0);
    for(int i=1;i<=m;++i) p[i]=i;
    sort(p+1,p+m+1,cmp);
    sgt::build(1,1,n);
    for(int i=1;i<=m;++i)
    {
        e[p[i]]=sgt::sum(1,c[p[i]],d[p[i]]);
    }
    for(int i=1;i<=m;++i)
    {
        if(e[i]==0) printf("-1\n");
        else printf("%d\n",e[i]);
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 64ms
memory: 543664kb

input:

3
1 1
2 1 2 1 2
3 2
5 1 5 4 3 3 4 5 1 1 2
4 5
12
1 1 1 1
2 1 1 1
3 1 1 1
3 1 1 9
3 2 2 20
3 1 2 18
3 1 2 19
3 1 2 20
3 0 1 8
2 1 0 4
2 1 0 3
2 1 0 2

output:

1
2
3
3
2
2
1
-1
1
-1
2
2

result:

ok 12 numbers

Test #2:

score: 0
Accepted
time: 62ms
memory: 543408kb

input:

2
47 11
1 98 25
9 90
10
1 32 28 1811
2 17 44 4114
1 36 88 2661
2 79 33 3681
1 53 26 2778
2 59 20 2332
2 63 45 4616
2 72 11 10835
1 13 28 919
2 16 59 4445

output:

1
-1
-1
2
-1
1
2
1
1
2

result:

ok 10 numbers

Test #3:

score: 0
Accepted
time: 60ms
memory: 546036kb

input:

3
87 42
5 69 12 82 79 10 88 45 51 40 3
18 6
5 73 100 58 41 40 88 54 5 40 98
31 63
100
3 32 13 1811
1 51 21 5318
1 32 5 2994
2 77 51 19184
2 78 60 1763
1 10 1 913
1 22 51 4057
1 2 5 385
2 50 15 989
2 65 53 1488
1 49 82 7708
2 33 90 1133
1 23 33 3388
1 92 36 9516
3 39 61 10014
2 43 55 1103
2 48 38 127...

output:

3
1
1
1
2
-1
-1
-1
2
2
-1
2
-1
1
2
2
-1
3
2
2
3
1
1
1
-1
1
1
1
3
1
-1
1
-1
1
2
1
2
1
1
1
1
1
-1
1
-1
-1
1
1
-1
-1
1
1
2
1
1
-1
2
-1
1
1
1
1
3
1
2
3
2
2
1
1
-1
1
1
3
1
1
1
3
2
1
1
2
1
2
1
2
1
-1
-1
-1
1
2
1
1
-1
-1
1
3
2
2

result:

ok 100 numbers

Test #4:

score: 0
Accepted
time: 164ms
memory: 569036kb

input:

2
309248041 338995438
500000 1235 4866 1931 3652 1921 258 545 587 3001 542 3074 1694 4944 206 3217 3135 2388 4791 1890 3281 3840 4614 4491 1339 4660 1708 2225 3199 736 1306 4175 4652 906 3509 2571 1578 50 981 402 4975 2730 2198 4546 3120 40 815 2492 518 2102 2651 1018 3996 1764 808 3934 4312 1981 40...

output:

2
1
-1
2
2
2
1
1
2
-1
2
2
1
1
2
1
2
2
1
2
2
1
-1
-1
1
-1
2
-1
1
2
1
1
1
1
-1
1
-1
-1
-1
1
2
2
1
1
1
2
-1
-1
1
-1
1
2
-1
1
2
1
2
2
-1
2
1
2
2
-1
2
2
-1
2
1
2
1
-1
-1
1
1
-1
2
1
2
2
1
1
1
1
2
2
-1
-1
1
2
2
-1
2
-1
-1
-1
1
2
1
1
2
2
1
-1
-1
2
2
2
1
-1
1
2
2
-1
1
-1
-1
-1
1
2
1
2
1
-1
-1
1
2
2
-1
2
2
2
...

result:

ok 200000 numbers

Test #5:

score: 0
Accepted
time: 403ms
memory: 682544kb

input:

200000
999999511 993051669
2 5000 5000 5000 5000
1000000000 1000000000
3 5000 5000 5000 5000 5000 5000
995868520 999999999
2 5000 5000 5000 5000
660478427 999992996
3 5000 5000 5000 5000 5000 5000
999999979 999999998
2 5000 5000 5000 5000
861450412 989532141
3 5000 5000 5000 5000 5000 5000
949861679...

output:

145800
198491
112658
29436
38091
122582
7727
87686
192036
97288
60184
836
39235
158331
121422
117149
189664
153018
181334
56603
69911
173097
165342
124250
103223
110099
177817
11459
37052
28918
57236
143793
19234
10313
75590
6597
18202
176357
102394
179685
5171
162359
72023
56758
88764
17257
100583
...

result:

ok 200000 numbers

Test #6:

score: 0
Accepted
time: 63ms
memory: 544360kb

input:

20
1538 3628
4 2423 3790 3127 3961 2614 3582 2016 4789
1441 276
3 2518 253 4221 265 3236 2574
1668 3370
4 4489 3533 4501 2177 1067 2337 2765 1480
1179 1926
3 4922 2537 1477 653 325 444
3964 2924
2 3415 4463 822 3257
210 4068
2 1969 167 1978 3712
2067 540
4 1560 2211 4050 4196 442 2279 442 2448
2962 ...

output:

5
14
5
1
2
3
6
-1
8
7
2
11
1
8
8
3
3
13
4
5

result:

ok 20 numbers

Test #7:

score: 0
Accepted
time: 53ms
memory: 546764kb

input:

66
121 3727
2 1379 2036 975 1594
205 708
2 523 2978 176 2924
2528 440
4 3182 2078 1340 2166 1563 447 1076 157
3242 2859
5 2029 4660 2789 1593 4534 4137 921 3966 3440 1964
1503 3975
3 1354 3815 825 4981 1710 2692
858 2524
3 3395 3523 2184 4115 4043 3518
2610 731
3 3735 2799 442 1348 3101 2847
4306 14...

output:

9
12
20
-1
3
18
23
2
4
48
13
-1
8
38
8
28
7
1
8
51
4
9
10
10
3
24
14
5
19
2
33
3
45
5
4
29
5
23
24
36
24
-1
9
4
26
1
2
1
46
37
8
2
20
2
1
27
26
41
5
32
3
37
-1
7
43
2

result:

ok 66 numbers

Test #8:

score: 0
Accepted
time: 56ms
memory: 544060kb

input:

200
2768 3191
1 482 2676
4032 1626
1 1313 472
117 4314
3 1745 3269 1723 1603 1307 2675
2553 172
5 1678 868 246 2764 3746 3346 3650 317 3675 3877
2425 2618
2 1883 4174 4213 1781
3099 3645
1 4652 2962
1910 1338
3 4530 2328 2576 3373 3 1145
1887 1331
4 459 736 139 3184 550 31 740 3134
3488 2965
3 2097 ...

output:

57
85
59
36
24
39
5
4
81
49
23
107
104
39
62
49
3
156
25
64
13
92
16
62
20
104
13
26
66
61
109
56
1
32
7
37
14
9
10
136
20
7
2
129
149
109
29
15
51
18
80
107
6
20
50
27
111
-1
115
16
10
88
21
12
88
1
2
31
72
10
67
68
5
6
1
80
120
73
187
26
17
2
64
125
-1
43
4
10
72
13
129
45
118
54
27
56
100
56
27
3...

result:

ok 200 numbers

Test #9:

score: 0
Accepted
time: 60ms
memory: 543600kb

input:

666
2648 877
2 170 1622 4953 3255
18 2631
2 2355 1545 3734 1505
724 216
1 1944 1090
3733 2918
3 3393 1081 3478 4932 2001 501
3399 1829
3 4189 4125 1957 1754 2904 3622
4643 554
4 229 4356 3777 1315 4848 2584 1232 2718
4096 1924
2 892 1180 3500 2905
1759 1274
4 3950 1096 1779 2159 1617 1856 3182 2679
...

output:

466
198
247
228
66
306
101
147
11
480
35
354
59
225
76
20
314
84
272
2
315
13
6
4
212
430
28
290
339
121
125
4
21
362
254
19
77
456
69
27
62
6
269
100
68
4
396
1
58
377
203
100
94
162
188
151
48
4
377
277
242
274
217
167
45
24
116
291
263
305
112
183
225
5
107
120
210
56
50
140
4
192
165
250
303
77
...

result:

ok 666 numbers

Test #10:

score: 0
Accepted
time: 71ms
memory: 545916kb

input:

2000
2883 1742
3 281 1763 9 3931 3350 1572
1611 462
3 983 1286 1874 1928 4279 857
3773 1341
2 3861 4264 733 4060
1220 1451
3 2753 624 4520 2881 2051 1614
1406 2742
5 2857 2152 4349 495 3552 1319 4118 4269 3286 2235
4028 1138
4 2209 4188 1788 4226 517 2932 4067 3746
3105 2345
2 731 2039 1927 1275
137...

output:

1
210
42
101
386
26
68
202
806
352
362
29
559
52
1334
741
260
565
1041
85
220
67
448
194
1110
179
843
625
453
1055
641
691
79
145
869
10
40
8
60
134
1108
179
560
773
1748
452
469
1165
515
456
602
366
781
15
5
269
459
42
509
1046
339
1064
923
944
84
76
499
-1
1345
1051
44
2
1406
680
1726
326
32
96
85...

result:

ok 2000 numbers

Test #11:

score: 0
Accepted
time: 72ms
memory: 551668kb

input:

6666
2741 2461
3 526 4139 3060 2030 2766 3316
653 3631
1 4366 67
2628 3849
2 2449 2607 1617 68
3001 126
1 4561 4505
3166 3358
3 4322 1581 957 756 865 3540
1442 2226
4 4137 2789 2636 3371 3383 60 620 2488
550 3026
5 1285 3936 4074 4144 3933 3572 825 2255 55 796
4544 1791
3 1459 863 4284 3153 1674 122...

output:

46
1772
1912
2973
15
5358
3822
649
679
4265
1819
3808
783
1759
1426
2865
1820
11
168
209
4207
3606
1234
4049
576
1052
1514
86
191
712
4475
2262
223
1513
3483
3719
5287
4028
200
2063
241
1217
3043
622
955
5463
1806
337
855
2275
2962
164
3955
1673
353
2999
4622
2701
601
1999
933
35
2004
3380
64
776
27...

result:

ok 6666 numbers

Test #12:

score: 0
Accepted
time: 132ms
memory: 577572kb

input:

20000
1186 1182
1 2552 75
370 1750
2 1657 2841 3265 719
3481 2197
2 4047 16 277 1224
593 97
4 358 4602 1995 1679 1888 4757 4297 2320
3187 3062
2 2394 2756 3744 3166
467 261
3 3385 2572 4595 719 3514 1870
178 3985
4 1004 1799 4259 2920 1155 2664 4064 3732
385 2278
2 1784 4561 1022 1281
3907 2706
1 39...

output:

629
10461
7163
711
6127
3895
1990
1492
3117
2779
3930
428
10729
938
1012
541
6697
3517
4567
6669
285
10601
15453
11721
2
633
535
288
13293
15510
13541
1550
6895
6138
5565
6672
93
1621
6958
4345
4669
6546
11999
74
4152
7192
3334
2423
1982
1884
1956
3630
4614
1777
1826
6986
9
2318
8064
303
3082
1287
1...

result:

ok 20000 numbers

Test #13:

score: 0
Accepted
time: 212ms
memory: 605388kb

input:

40000
1322 4123
3 1729 4107 1325 1826 756 1338
2281 2223
4 3251 2045 4210 3298 3405 2626 2449 2539
332 4779
2 4329 2666 4605 253
501 2829
3 2908 2017 3694 4704 3794 3259
2231 3518
3 984 1800 2861 888 1137 4675
16 2796
5 3690 143 3763 3138 663 298 174 2769 3953 1526
1320 1584
2 3472 4857 1781 4871
39...

output:

117
10439
9881
3959
6978
234
11142
6493
28076
4122
9986
11628
20104
10580
20548
21044
2006
7256
14386
17260
7249
2969
18038
3722
1976
1080
19587
1804
108
2722
1370
554
2415
13413
4430
4743
1490
21
15752
14857
31955
1250
10259
10460
1775
996
51
13148
13819
22536
2861
2321
69
10517
4007
10082
13384
65...

result:

ok 40000 numbers

Test #14:

score: 0
Accepted
time: 301ms
memory: 637956kb

input:

66666
3910 403
2 475 1131 939 2976
3588 2717
3 4367 2516 4737 4629 351 2278
879 4121
1 4665 4982
1229 3257
3 4774 412 2628 3043 2537 4632
4102 764
4 365 1999 1340 1043 725 184 1366 464
1632 462
1 3678 1459
1472 3921
2 2218 3124 1193 4188
587 4637
3 663 2801 3365 1486 4024 2027
464 4849
2 3627 726 18...

output:

18005
6802
4402
63081
12216
1997
3852
2251
25870
25581
25907
172
21566
7609
432
11729
6583
7984
5659
8279
2295
27118
11619
4499
18976
2789
64962
7114
17828
4100
9093
2201
164
25433
799
9329
1573
5677
1802
6594
16903
3261
10135
4868
1878
8830
43109
33459
478
18129
21607
24469
102
1169
18060
11070
145...

result:

ok 66666 numbers

Test #15:

score: 0
Accepted
time: 422ms
memory: 711216kb

input:

100000
2766 3928
1 801 4090
1696 1887
2 2478 338 4886 2028
4449 473
2 4009 2510 587 962
3272 2216
2 1422 457 2248 2264
1634 2781
1 463 1296
292 433
4 406 4396 99 4408 64 1583 2977 4428
2628 1270
2 2431 4144 2898 2133
1412 4349
2 2756 3515 1551 3118
2461 1056
1 3027 4519
3257 940
2 1241 1252 4920 465...

output:

71
44948
26956
58728
15513
11202
23070
1708
936
2159
10979
37052
26887
7507
24943
1182
12837
6822
55436
8472
45797
40278
23445
1702
5051
50219
7096
1063
18284
379
52305
25792
17832
12078
11885
53278
8544
1148
6362
10594
13108
66927
44308
65930
74953
13065
1153
3085
443
9498
12671
10554
29519
43697
3...

result:

ok 100000 numbers

Test #16:

score: 0
Accepted
time: 928ms
memory: 894344kb

input:

200000
870 4638
6 4716 1571 845 599 943 4354 4102 2994 4706 3121 1579 4190
4305 2436
2 2767 1501 3629 98
3824 1262
1 2748 2558
1723 166
3 4457 4290 1253 3994 4266 4934
2021 1195
1 2736 2682
2407 484
3 1531 3959 3257 2154 123 1106
2441 674
1 2450 2914
3057 3536
3 1533 1051 1507 2518 3773 2867
3622 15...

output:

157843
25378
57229
10046
64593
20854
163253
59732
56538
978
2512
108129
2903
69944
5488
98723
14617
165726
23353
409
57829
79874
123834
4583
8613
3554
33478
12378
19599
94577
5555
76752
95569
1701
16813
181
12645
2668
50296
58364
79228
918
22141
93190
36225
119304
31816
46997
33449
60084
65843
24284...

result:

ok 200000 numbers

Test #17:

score: 0
Accepted
time: 730ms
memory: 813872kb

input:

131071
139764 478870
4 4782 1547 2947 4953 3336 3508 4282 3928
40955 209792
5 4214 616 86 4104 3099 4024 3994 1365 1027 4531
231530 91516
3 3085 3413 2092 3701 2933 4226
40015 431714
1 4764 4756
327678 328274
2 4882 3819 1767 4068
97093 266868
3 879 2008 2107 2988 4120 2907
261491 97456
2 4192 4053 ...

output:

27274
6408
588
102723
58669
20816
8478
46672
42410
73733
844
107573
39190
30387
45336
33923
41985
27314
20278
39399
46315
35755
42380
5920
113412
109707
74826
19148
18707
73650
11681
74360
66765
4404
3629
19265
14140
35353
18059
32351
696
69704
33963
1410
9113
43952
40178
6935
4132
84180
22997
24766...

result:

ok 200000 numbers

Test #18:

score: 0
Accepted
time: 723ms
memory: 814408kb

input:

131072
6223 460632
6 2483 2393 2842 257 3518 3179 4691 3866 4420 4839 1231 2273
247781 211555
2 276 3122 4545 3262
425398 177601
4 971 679 2764 2174 1464 3566 3098 4846
232356 163195
2 4469 1931 4889 1379
386550 88052
4 3242 4291 3446 1609 4751 2330 2543 2225
452519 156503
4 3790 520 1149 647 1466 3...

output:

6208
13417
58680
29635
28147
58019
9452
11259
55255
52801
18425
23854
60997
23540
70470
72642
43355
4178
64018
35442
8237
7410
22214
40424
63910
47446
19637
53405
83758
6064
10504
26267
80024
8891
26029
19848
23749
22185
9446
97454
57990
50674
3543
9055
37796
38089
54665
14909
20941
51503
59197
9677...

result:

ok 200000 numbers

Test #19:

score: 0
Accepted
time: 749ms
memory: 817752kb

input:

131073
316493 134226
3 780 3985 4704 2047 416 1078
48008 126287
6 4988 1028 3318 3341 3383 4549 4241 275 3964 3949 2420 2420
335453 237601
2 1866 924 3852 35
9423 207118
5 1422 2957 1647 1127 4449 4421 2871 2912 401 538
246824 114850
2 3199 1999 2198 4479
415809 123678
3 2256 360 3457 2925 1796 1026...

output:

53510
29593
17978
8358
34248
40865
43104
90096
6781
55563
71447
6624
33577
41420
9038
103039
38104
73338
114013
53095
66427
36616
77104
46399
83191
56991
24673
19483
17851
6718
15584
7777
277
20657
13937
74652
8870
99630
24045
34743
47382
77338
55563
18271
16144
55236
12782
857
39012
17686
16225
157...

result:

ok 200000 numbers

Test #20:

score: 0
Accepted
time: 943ms
memory: 895784kb

input:

199901
3293 2284
3 1171 2655 3120 2577 2805 4312
3025 3891
3 3723 1531 4540 4479 1421 4008
4210 1811
1 2492 2142
3204 292
4 2776 4278 695 4035 4569 1257 2269 1254
1459 81
2 3560 2675 1780 597
2988 2959
6 1392 4017 10 1770 351 1029 2078 1664 1718 4192 2599 3109
2279 155
4 3643 1851 2643 2128 3610 380...

output:

4230
137033
62455
130749
5941
16398
40711
15337
2635
7212
72282
7921
29478
2813
59569
13644
58578
6631
94895
140488
17258
37640
195731
76075
53058
114476
63415
65345
35469
86745
122531
46090
66377
57034
8757
2011
102224
71022
24914
5094
2984
146398
27257
47641
44643
114
45395
667
45343
55808
85128
7...

result:

ok 199990 numbers

Test #21:

score: 0
Accepted
time: 914ms
memory: 895012kb

input:

200000
2543 2408
1 4912 368
1981 3459
3 910 3485 4574 2614 2736 2196
953 4370
4 1174 483 1103 515 4395 3184 4616 3927
1485 4521
3 1581 3154 3114 2121 4816 162
2234 1377
1 339 289
2921 1761
1 3350 123
848 3567
2 4505 1444 34 194
4038 23
1 543 1618
1274 3140
1 4579 4286
1805 2514
2 27 2089 1985 2267
1...

output:

55056
5065
129558
48887
7737
6893
70544
20543
20065
128053
22138
2594
63038
75004
39979
74728
94906
50369
1269
32896
59693
6927
8387
83890
63662
53547
88114
12797
49267
35553
62420
88476
43383
583
47258
24940
139951
6193
139637
142146
46322
35506
139053
41925
13909
59337
7
146270
66669
1077
4091
3
2...

result:

ok 199982 numbers

Test #22:

score: 0
Accepted
time: 865ms
memory: 881540kb

input:

199900
78690 820471
3 4242 531 1591 1243 639 701
350077 537673
2 2906 1644 1996 2563
519283 295902
2 1692 1820 180 4879
208195 417170
1 3597 2277
282917 929980
1 798 517
615590 225385
2 4024 1291 152 4632
86541 683217
3 314 4423 2362 3917 2935 1967
33589 406147
3 4094 4478 3069 234 4285 979
454586 2...

output:

15359
114877
149266
58974
118321
40999
148940
532
14483
64287
8866
22654
129942
61632
109711
3927
153100
71435
2177
30441
28073
86539
45196
68783
82972
80262
65262
84238
117008
1087
17884
128527
48712
25016
103846
39000
61746
76189
8023
7813
10502
49894
105981
46505
9256
31425
154264
5667
45148
1006...

result:

ok 200000 numbers

Test #23:

score: 0
Accepted
time: 888ms
memory: 879472kb

input:

199987
212495 690296
3 2211 2384 3463 1623 4397 98
788317 313858
2 1218 3653 460 2398
276899 302136
3 960 3279 3790 1492 2930 2590
592888 466734
1 1938 3102
232542 208827
3 2408 4364 153 2513 4528 3130
336342 363920
1 2451 916
553994 822203
2 505 2680 1524 2648
477482 80133
1 3366 2194
170616 431748...

output:

2848
8201
50339
6660
16767
110662
3191
24591
66905
77921
49986
30208
68132
3655
32728
38291
127466
175067
98798
14339
34081
68281
18756
2527
54881
19947
9943
22880
36424
107904
98360
37827
51983
9476
4691
47778
170101
6580
142774
86794
11847
22791
52841
54793
30466
150293
61105
16792
21133
46137
404...

result:

ok 199936 numbers

Test #24:

score: 0
Accepted
time: 880ms
memory: 880884kb

input:

200000
607780 128071
3 4280 2827 4926 1431 1610 1681
718674 662164
4 3178 467 1478 1233 3442 3952 4196 2133
641607 7028
3 4460 3173 3768 3818 1884 232
448230 512426
4 1684 4065 1980 4706 1590 3175 2418 1606
605366 235823
3 3754 1702 4298 4142 2545 1964
692258 609171
1 189 4286
52916 189132
3 4892 84...

output:

7675
388
23524
40366
67485
3971
77425
2612
177284
73819
87300
86224
14970
18357
14912
88059
15023
97386
142963
8550
24228
39238
27597
132898
53228
65770
11733
66830
57708
97106
7567
5356
2649
28520
479
51533
125151
18769
126176
13509
50777
90839
9528
56250
159592
33753
138984
62105
69918
229
13267
6...

result:

ok 199975 numbers

Test #25:

score: 0
Accepted
time: 812ms
memory: 850584kb

input:

199953
142561117 474175298
4 3719 154 2429 4996 2633 2432 4560 4149
141373697 22414249
3 2448 1149 4026 3041 1232 161
126914209 400530096
4 1486 3925 245 212 1811 2487 3272 1295
327219634 328108615
2 3275 757 351 627
9347529 468040920
5 1531 2208 4180 826 3699 2436 980 4886 2864 4444
62450112 451004...

output:

75447
12244
122033
124150
78605
80776
70046
46001
4905
3889
11646
12216
71533
166040
55718
142972
73624
16898
40056
12319
153304
69143
56748
47703
80338
70788
17686
60233
33504
83809
77704
4841
17081
11683
37766
51658
85399
17202
105691
48602
82006
5722
27631
87399
75189
2963
123766
2072
112062
5369...

result:

ok 199919 numbers

Test #26:

score: 0
Accepted
time: 803ms
memory: 852156kb

input:

200000
59874959 283731044
3 638 1092 907 2892 4303 2533
223263132 50393364
1 2195 2223
95200195 145583768
3 2610 793 1421 3193 4707 639
197055310 294066377
1 741 3992
118585604 219943492
2 4815 3612 3236 1887
218563794 25623048
1 917 4569
44315832 264892800
2 2464 2670 4637 2845
97726329 154588982
1...

output:

6388
81686
31209
79809
65193
90639
3781
97032
66711
6756
22791
4381
29561
9743
17542
48047
27677
61695
12712
57494
52435
109251
85407
33906
17542
130393
33119
184388
40557
-1
90503
70517
83217
13297
9900
9027
25308
117742
69266
2966
111482
46336
147358
150891
147172
40477
110331
79050
30430
19683
87...

result:

ok 200000 numbers

Test #27:

score: 0
Accepted
time: 747ms
memory: 856548kb

input:

200000
246174057 382791134
3 3880 3106 3734 711 4015 2302
20079721 484929831
1 2061 997
223865187 355513072
4 879 4541 3235 1301 3105 1236 1630 4533
142533043 269545254
2 4245 1903 3821 2381
393154979 154666975
4 2984 1783 1491 1837 2285 4545 374 4755
59420490 483179350
4 1994 854 457 2141 4398 336 ...

output:

27859
123483
15393
152454
47896
1201
33614
41017
185257
95292
138407
88769
112740
116135
-1
133322
65051
14877
75604
91209
58904
26078
101227
32710
2725
9863
162222
1637
68150
29277
81768
4572
60685
98204
175051
112947
69266
73996
107101
8338
5856
70244
144471
147576
59688
19088
60623
93479
3401
485...

result:

ok 199963 numbers

Test #28:

score: -100
Wrong Answer
time: 104ms
memory: 564092kb

input:

200000
85 80
2 883 707 58 1513
1767 0
1 3087 0
808 3948
4 192 1419 1599 27 597 1021 850 771
224 6116
4 2514 1873 2065 2312 1280 3074 4021 342
711 9955
1 111 28
229 10555
1 487 170
20 11396
4 13 1262 1079 211 774 515 256 1024
12608 311
3 1701 891 854 1750 104 2483
14710 792
2 380 9 126 266
15847 21
6...

output:

93974 119217254 330999377 46203603317890686

result:

wrong answer 1st numbers differ - expected: '44686', found: '93974'