QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#448189#8525. MercenariesmarherAC ✓822ms434780kbC++145.0kb2024-06-19 13:46:002024-06-19 13:46:00

Judging History

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

  • [2024-06-19 13:46:00]
  • 评测
  • 测评结果:AC
  • 用时:822ms
  • 内存:434780kb
  • [2024-06-19 13:46:00]
  • 提交

answer

#pragma GCC optimize("Ofast","inline")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+50;

struct poi
{
    int x,y;

    friend poi operator+(poi a,poi b)
    {
        return (poi){a.x+b.x,a.y+b.y};
    }

    friend poi operator-(poi a,poi b)
    {
        return (poi){a.x-b.x,a.y-b.y};
    }

    int operator^(poi b)
    {
        return x*b.y-y*b.x;
    }

    int len()
    {
        return x*x+y*y;
    }

    friend bool operator<(poi a,poi b)
    {
        int w=a^b;
        return w==0?a.len()>b.len():w<0;
    }
    
    int operator*(poi b)
    {
        return x*b.x+y*b.y;
    }
}a[N];

struct query
{
    poi x;int c,id,p;
    
    friend bool operator<(query a,query b)
    {
        return a.x<b.x;
    }
}Q[N];

int n,q,ans[N];
vector<poi>p[N];
poi st[N<<3];

#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
#define LS ls,l,mid
#define RS rs,mid+1,r

struct convex
{
    vector<poi>p;
    int pos;

    void merge1(convex a,convex b)// mink
    {
        vector<poi>().swap(p);
        p.resize(a.p.size()+b.p.size());
        int pos=0,cc=0;
        for(auto x:a.p)
        {
            while(pos<b.p.size()&&b.p[pos]<x)p[cc++]=b.p[pos++];
            p[cc++]=x;
        }
        while(pos<b.p.size())p[cc++]=b.p[pos++];
    }
    
    void merge2(convex a,convex b)// convex hull
    {
        vector<poi>().swap(p);
        int cc=0,pos=0;
        for(auto x:a.p)
        {
            while(pos<b.p.size()&&(x.x>b.p[pos].x||(x.x==b.p[pos].x&&x.y>b.p[pos].y)))st[cc++]=b.p[pos++];
            st[cc++]=x;
        }
        while(pos<b.p.size())st[cc++]=b.p[pos++];
        if(cc==0)return;
        int top=0;
        for(int i=1;i<cc;i++)
        {
            while(top&&((st[i]-st[top-1])^(st[top]-st[top-1]))<=0)top--;
            st[++top]=st[i];
        }
        p.resize(top+1);
        for(int i=0;i<=top;i++)p[i]=st[i];
    }

    void diff()
    {
        for(int i=p.size()-1;i>0;i--)p[i]=p[i]-p[i-1];
    }
    
    void integral()
    {
        for(int i=1;i<p.size();i++)p[i]=p[i]+p[i-1];
    }

    int find(poi x)
    {
        if(p.empty())return 0;
        int w=x*p[pos];
        while(pos+1<p.size()&&w<=x*p[pos+1])w=x*p[++pos];
        return w;
    }
}f[N],g[N],tmp;

void build(int x,int l,int r)
{
    if(l==r)
    {
        sort(p[l].begin(),p[l].end(),[&](poi a,poi b){return a.x==b.x?a.y<b.y:a.x<b.x;});
        f[x].merge2((convex){p[l]},(convex){});
        g[x]=f[x];
        for(auto&t:g[x].p)t=t+a[l];
        f[x].diff();
        return;
    }
    build(LS);build(RS);
    f[x].merge1(f[ls],f[rs]);
    tmp=g[ls];tmp.diff();
    tmp.merge1(tmp,f[rs]);
    tmp.integral();
    g[x].merge2(tmp,g[rs]);
}

int c;poi t;

int solve(int x,int l,int r,int L,int R)
{
    if(L>R)return -1;
    if(L<=l&&R>=r)
    {
        if(g[x].find(t)<c)
        {
            c-=f[x].find(t);
            return -1;
        }
        if(l==r)return l;
        int w=solve(RS,L,R);
        return w==-1?solve(LS,L,R):w;
    }
    if(R>mid)
    {
        int w=solve(RS,L,R);
        if(w!=-1)return w;
    }
    return solve(LS,L,R);
}

void dfs(int x,int l,int r)
{
    f[x].integral();
    if(l==r)return;
    dfs(LS);dfs(RS);
}

namespace IO {
#define iL (1 << 20)
char ibuf[iL], *iS = ibuf + iL, *iT = ibuf + iL;
#define gc() ((iS == iT) ? (iT = (iS = ibuf) + fread(ibuf, 1, iL, stdin), iS == iT ? EOF : *iS ++) : *iS ++)
template<class T> inline void read(T &x) {
  x = 0;int f = 0;char ch = gc();
  for (; !isdigit(ch); f |= ch == '-', ch = gc());
  for (; isdigit(ch); x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc());
  x = (f == 1 ? ~ x + 1 : x);
}
template<class T, class... Args> inline void read(T &x, Args&... args) { read(x), read(args...); }
template<class T> inline void readch(T &x) { char ch = gc(); for (; !isalpha(ch); ch = gc()); x = ch; }
char Out[iL], *iter = Out;
#define flush() fwrite(Out, 1, iter - Out, stdout), iter = Out
template<class T> inline void write(T x, char ch = '\n') {
  T l, c[35];
  if (x < 0) *iter ++ = '-', x = ~ x + 1;
  for (l = 0; !l || x; c[l] = x % 10, l++, x /= 10);
  for (; l; -- l, *iter ++ = c[l] + '0');*iter ++ = ch;
  flush();
}
template<class T, class... Args> inline void write(T x, Args... args) { write(x, ' '), write(args...); }
} // IO
using namespace IO;

main()
{
    read(n);
    for(int i=1;i<=n;i++)
    {
        read(a[i].x,a[i].y);
        if(i==n)break;
        int k;read(k);
        p[i].resize(k);
        while(k--)read(p[i][k].x,p[i][k].y);
    }
    build(1,1,n);dfs(1,1,n);read(q);
    for(int i=1;i<=q;i++)read(Q[i].p,Q[i].x.x,Q[i].x.y,Q[i].c),Q[i].id=i;
    sort(Q+1,Q+1+q);
    for(int i=1;i<=q;i++)
    {
        t=Q[i].x,c=Q[i].c;
        int pos=Q[i].p;
        if(a[pos]*t>=c)ans[Q[i].id]=pos;
        else ans[Q[i].id]=solve(1,1,n,1,Q[i].p-1);
    }
    for(int i=1;i<=q;i++)write(ans[i]);
}

详细

Test #1:

score: 100
Accepted
time: 11ms
memory: 91460kb

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: 15ms
memory: 90336kb

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: 11ms
memory: 91468kb

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: 96ms
memory: 117128kb

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: 259ms
memory: 277368kb

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: 12ms
memory: 91516kb

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: 20ms
memory: 90932kb

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: 12ms
memory: 90832kb

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: 16ms
memory: 90984kb

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: 24ms
memory: 92672kb

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: 22ms
memory: 97640kb

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: 64ms
memory: 112980kb

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: 132ms
memory: 136152kb

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: 235ms
memory: 166816kb

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: 340ms
memory: 207368kb

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: 822ms
memory: 330860kb

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: 639ms
memory: 282968kb

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: 624ms
memory: 286884kb

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: 573ms
memory: 285908kb

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: 788ms
memory: 332148kb

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: 780ms
memory: 331476kb

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: 739ms
memory: 325732kb

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: 782ms
memory: 323848kb

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: 775ms
memory: 324948kb

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: 680ms
memory: 317516kb

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: 621ms
memory: 318968kb

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: 641ms
memory: 316940kb

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: 0
Accepted
time: 723ms
memory: 426996kb

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:

44686
8476
62791
8712
70714
-1
19902
-1
81267
161132
146323
34841
22913
29635
63141
97338
3992
16255
40877
139469
123399
174831
-1
192581
156890
41550
99146
149
116506
70649
42747
99581
10218
58946
137726
1937
7923
160633
65409
-1
93331
36229
12492
91800
142342
183775
62909
72739
163683
21518
69037
...

result:

ok 200000 numbers

Test #29:

score: 0
Accepted
time: 760ms
memory: 433684kb

input:

200000
18 635
1 21 474
682 465
2 907 608 1414 99
272 2386
2 910 298 167 1042
3736 129
1 298 136
148 4148
1 409 271
4960 16
1 1229 177
14 6351
2 19 1709 597 1126
7613 484
1 118 187
8192 205
2 5 957 846 119
1067 8302
1 725 153
27 10200
2 455 1078 1372 172
11741 36
1 177 37
400 11570
2 1479 142 688 943...

output:

4809
113219
19270
22649
-1
28510
46480
-1
-1
120187
5286
30255
175327
-1
35132
48373
-1
99785
22171
28
-1
-1
35212
59741
820
117119
53211
-1
-1
-1
19352
62556
26264
38722
-1
-1
151132
-1
17649
43686
52991
50944
17571
147761
72757
28818
43190
49005
-1
41258
81990
2708
163827
19888
7358
-1
46781
-1
17...

result:

ok 200000 numbers

Test #30:

score: 0
Accepted
time: 690ms
memory: 377628kb

input:

200000
436 378
4 885 2681 306 3260 1726 1841 2404 1157
4284 99
1 447 1
436 4382
5 2405 2013 711 3674 4401 12 3522 902 3069 1358
324 8862
3 396 2333 1481 1249 2314 426
9639 2352
1 153 822
12731 186
1 289 466
11 13608
1 10 1111
14599 133
4 1479 140 622 1021 1142 488 81 1565
15202 1178
1 179 1936
16965...

output:

157518
17572
187931
199076
63066
-1
78934
60398
48066
14973
103216
56643
11650
74487
23179
82309
145622
114081
158785
40162
-1
449
122
3225
74486
185203
7394
70407
5863
89491
16328
75242
95279
82958
149790
78639
68321
-1
144343
76478
69242
62085
169527
156207
3157
87724
101731
-1
6084
82097
88390
76...

result:

ok 200000 numbers

Test #31:

score: 0
Accepted
time: 669ms
memory: 375688kb

input:

200000
144 19
1 199 252
36 599
1 467 920
1257 749
1 11 450
2478 8
2 1372 4 872 494
3236 603
2 922 2397 3317 2
1423 5734
1 145 48
778 6561
1 408 5
3 7749
1 3 50
316 7475
1 1 69
6876 1005
1 3 798
8479 218
1 4 562
9247 8
1 5 2781
10808 1208
1 9 261
11683 604
2 1581 332 27 1877
2077 12138
1 37 102
14312...

output:

122554
166028
151591
133209
132479
83388
135665
171737
128171
64162
182032
150016
134261
119943
181370
147433
145822
88611
190288
170112
184223
148694
76436
156539
139033
119080
179451
154324
144570
132959
132450
190070
162212
129772
129764
170698
168832
79045
109670
133209
176082
134288
109820
1432...

result:

ok 200000 numbers

Test #32:

score: 0
Accepted
time: 686ms
memory: 376060kb

input:

200000
87 517
1 2404 187
29 3068
1 207 575
3868 47
2 1099 159 280 959
4306 932
1 579 713
133 6153
3 51 2472 1644 914 2237 303
8695 319
2 1153 902 589 1446
11013 28
2 241 945 1128 47
5173 7009
3 793 914 908 794 43 1653
3693 10196
1 927 1159
14609 1387
3 1165 291 783 684 140 1319
105 17224
1 19 826
18...

output:

120717
89227
31424
138493
61473
70993
140327
32140
140750
158458
78869
3418
60211
71693
42140
16573
6841
149018
49293
74183
25820
152371
124524
38271
39644
49700
36393
58326
164776
86958
102614
164903
-1
85452
3426
-1
63791
39452
-1
185294
89165
53092
69253
63901
25820
196685
146530
21098
111233
161...

result:

ok 200000 numbers

Test #33:

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

input:

200000
72 377
1 778 154
1358 28
1 49 1578
2270 751
2 107 465 530 46
1 3566
2 18 1196 614 605
4463 360
1 167 1561
6363 195
1 81 246
6880 6
1 1115 40
432 7542
2 2268 233 1526 970
164 10269
3 1918 1897 2983 846 163 3622
13821 551
3 1447 166 648 956 199 1399
13582 2399
1 20 771
16076 701
1 8 122
4053 12...

output:

158545
130177
64780
51445
30098
52797
-1
136448
89210
168099
-1
40962
673
89898
99618
14468
37550
18398
46467
23216
-1
150446
123787
20640
12014
22896
121336
23963
20158
182611
135346
96535
5269
-1
23636
125099
100717
62013
-1
57260
55457
-1
75367
143038
4213
47860
79442
166380
-1
33366
6156
88790
5...

result:

ok 200000 numbers

Test #34:

score: 0
Accepted
time: 771ms
memory: 427784kb

input:

200000
13 995
1 2 208
1032 190
4 3 3241 2898 404 1961 1331 1010 2271
4474 51
4 1098 2037 69 3034 1463 1676 2152 990
7647 15
3 192 2652 1457 1394 351 2495
9960 546
2 473 1595 1207 870
12551 11
3 154 1746 1077 828 1869 29
13589 884
3 2511 230 792 1912 1485 1239
1076 15982
2 1518 596 486 1639
18848 457...

output:

438
3043
71015
29700
11928
5949
-1
50427
-1
16973
17935
1
15771
-1
3650
116535
2499
168454
154556
38442
145214
7014
32669
35009
28005
78322
772
120296
106927
150322
3176
125309
2257
-1
-1
51350
9101
26106
45192
27080
54123
126202
22634
51002
64446
7356
5630
16676
2727
36236
64183
155913
445
104033
1...

result:

ok 200000 numbers

Test #35:

score: 0
Accepted
time: 716ms
memory: 375112kb

input:

200000
525 222
1 379 255
60 1324
1 122 227
1570 161
1 167 1047
2780 184
2 497 174 611 58
17 3593
1 956 293
606 4234
1 986 212
6001 79
1 72 113
955 5250
1 860 89
7 7098
3 1 2590 1426 1188 1035 1574
8952 872
1 2 1180
9957 1044
4 3 3713 3053 724 2139 1625 3543 239
14426 361
1 9 983
14709 1058
2 832 507...

output:

102579
99582
91117
54714
-1
30032
149771
142714
111647
187614
-1
10001
-1
34752
152947
77609
12922
114096
2743
90879
129082
21838
78367
67310
-1
-1
213
31162
194881
-1
59301
163331
622
60123
121301
91369
5185
156371
116174
79069
107588
74862
-1
33351
151658
5814
154288
-1
119127
192818
175543
-1
745...

result:

ok 200000 numbers

Test #36:

score: 0
Accepted
time: 694ms
memory: 375692kb

input:

200000
51 343
4 4 2739 2029 746 1288 1481 444 2306
3037 44
3 1709 1327 2299 740 3 2984
6035 64
2 197 1000 48 1158
1085 6236
1 293 1207
7231 1624
2 558 72 52 568
8246 1212
3 1126 499 743 876 173 1452
10836 135
1 149 209
243 11083
2 31 495 403 107
10498 1500
6 4337 481 400 4411 1342 3491 3324 1496 214...

output:

91863
46027
-1
188189
31776
4454
13699
89554
168812
42913
42041
144291
61869
90272
129278
30969
-1
122307
33213
114115
14
128238
20117
77146
99598
166460
119332
76051
149919
64458
136537
4916
82478
128615
20724
120962
94933
14004
143755
4500
196753
76346
7926
66815
105179
-1
47879
118974
113922
1633...

result:

ok 200000 numbers

Test #37:

score: 0
Accepted
time: 733ms
memory: 421488kb

input:

200000
1805 3
1 622 6
1294 1129
1 192 21
617 2009
1 1105 1283
3 4989
2 2241 245 3 2447
7103 433
1 10 628
8172 13
2 1526 127 7 1632
861 8873
2 1326 474 471 1315
10210 1421
1 0 1682
13151 185
3 1544 1257 2590 222 379 2408
430 15536
1 686 83
14 16700
1 4 830
17558 201
1 221 2084
20005 50
1 337 133
4279...

output:

103094
9586
134620
129734
89733
45854
-1
193681
144964
100895
44009
184001
-1
107191
71290
160114
-1
194746
114154
-1
117973
172550
70262
119612
141536
11374
175082
138964
66643
117589
91033
104013
62449
164919
58265
38067
45383
-1
80335
86258
3737
63296
86463
75431
5335
112345
15000
59405
21949
369...

result:

ok 200000 numbers

Test #38:

score: 0
Accepted
time: 739ms
memory: 427972kb

input:

200000
646 256
4 2042 3141 486 4671 3142 2038 4813 326
146 5892
2 2686 101 347 2403
21 8752
2 103 1629 1287 438
8734 1838
5 2901 977 78 3782 3631 234 321 3547 1860 2022
6166 8311
3 3121 15 305 2865 940 2242
16982 549
2 924 210 825 307
143 18484
4 2467 443 1187 1737 1542 1380 37 2842
21510 25
2 553 4...

output:

28955
88880
73210
-1
78387
108664
-1
-1
19813
1764
56396
3863
-1
171255
36289
3
18281
19424
-1
-1
7009
52499
96956
-1
35775
25664
-1
239
-1
44800
161677
85452
27151
5378
-1
33865
63551
26170
42145
45845
178274
35779
17317
27809
10152
-1
-1
-1
17808
10893
44652
42669
85353
-1
31571
-1
108550
12210
10...

result:

ok 200000 numbers

Test #39:

score: 0
Accepted
time: 686ms
memory: 375100kb

input:

200000
77 47
3 718 2879 2149 1436 2565 1004
282 3440
1 488 148
4273 52
2 1429 5 314 1123
197 5583
2 1987 76 1356 711
372 7471
1 758 2507
9336 1701
1 1102 582
12492 193
2 374 1567 1218 716
604 14126
2 35 1961 1736 246
16588 0
1 424 1
61 17080
2 114 1043 1099 53
2219 16094
1 235 9
3149 15413
1 32 66
9...

output:

171884
189801
30480
5344
65941
135761
76610
150752
120550
48464
167867
95427
110936
72823
47235
57070
117274
32805
74073
72823
42384
34801
42768
31485
33553
14352
140986
144232
63735
-1
124697
12028
165667
87283
7321
-1
70433
8116
17702
180252
-1
65351
169863
40832
196290
140524
181531
63837
129896
...

result:

ok 200000 numbers

Test #40:

score: 0
Accepted
time: 661ms
memory: 377888kb

input:

200000
6 595
3 3 3178 952 2245 2608 606
3706 110
1 1 3889
4594 3113
2 1 1842 775 1074
7371 2195
5 3285 229 286 3199 1425 2081 4 3474 2302 1210
11834 1221
1 7 1838
13963 870
2 4 1892 1632 248
16407 279
4 3 3212 658 2552 1800 1387 2619 540
11822 8179
2 952 1885 142 2717
21696 910
4 368 3744 1281 2843 ...

output:

144800
197864
127908
51986
150337
76232
79223
82713
133756
180683
106297
154050
125652
194336
159447
168815
160559
119126
119679
183257
194943
107178
159035
103404
181692
120584
159150
169589
184564
109341
196588
124718
167422
120907
77863
76039
159793
109361
121605
140792
151453
151474
197517
10642...

result:

ok 200000 numbers

Test #41:

score: 0
Accepted
time: 672ms
memory: 373892kb

input:

200000
890 4
1 205 302
258 1248
1 29 623
2150 43
2 1748 2669 4021 384
980 5539
1 299 493
150 7182
1 135 810
8222 15
1 131 13
11 8452
1 9 413
7757 1013
1 10 992
8982 801
1 371 1660
11372 422
1 359 44
137 12074
1 87 712
12903 144
1 700 5
594 13241
1 376 198
329 14103
1 1856 391
1274 15313
1 337 1065
6...

output:

12879
92699
28205
162399
34194
42863
194377
52679
45004
56470
50838
152395
137832
111846
11931
186081
27469
-1
20506
18175
131515
24266
124206
179427
-1
141422
-1
28711
156110
24885
41168
8788
15332
81003
87535
163876
93691
14021
-1
-1
17261
142803
168460
58662
2196
18126
88135
4892
134255
39657
191...

result:

ok 200000 numbers

Test #42:

score: 0
Accepted
time: 604ms
memory: 257656kb

input:

200000
405921222 94476182
2 1185 1315 1079 1421
173441042 326953901
1 2398 102
419262353 81130113
2 126 2374 522 1978
106488017 393901962
1 2419 81
219170141 281217299
1 1415 1085
240970564 259414354
1 1274 1226
294048775 206333659
1 1536 964
355641566 144738357
1 1052 1448
161977362 338400053
1 827...

output:

5806
57317
6284
5820
87385
68622
29949
7343
66503
113154
10625
153587
4149
35638
2197
54094
28094
73483
92932
48624
52830
49965
43581
115349
3053
73536
19861
109118
94936
74184
74038
11145
138541
23075
119533
76760
35783
76028
145290
36189
7248
21609
87183
75908
38749
1042
20734
79151
103102
31662
2...

result:

ok 200000 numbers

Test #43:

score: 0
Accepted
time: 579ms
memory: 256992kb

input:

199999
94466816 405528244
1 2181 319
89764210 410228321
2 998 1502 692 1808
492219531 7770476
2 815 1685 232 2268
441627531 58360065
1 1252 1248
229698301 270286725
23 1288 980 8 190 2260 240 121 125 106 2394 1377 272 1742 169 1638 158 1262 199 163 566 1289 613 1075 1237 934 427 1 2244 132 1159 1037...

output:

13140
43767
26259
34020
37189
10950
5938
25959
50348
41765
57644
125394
138610
68520
100789
573
11530
20138
17214
116783
22664
93070
11867
101959
81142
56672
53035
17063
55910
8986
40935
16666
104011
117500
36119
20212
13495
90652
14061
103730
17197
22038
29796
71189
61826
119139
69307
55062
89976
5...

result:

ok 199999 numbers

Test #44:

score: 0
Accepted
time: 594ms
memory: 428576kb

input:

200000
331 785
3 2281 275 545 1977 2435 122
3279 392
3 1657 75 948 780 1195 536
20 5296
1 14 822
5827 402
3 214 3738 1811 2147 2568 1384
2863 7307
6 1618 2848 946 3510 4272 226 3370 1121 998 3459 27 4409
13391 1277
2 275 882 618 538
14907 902
2 683 631 50 1269
16396 710
1 552 889
4 18405
2 660 339 2...

output:

1
1
1
1
1
-1
1
1
-1
1
1
1
1
-1
-1
1
1
1
1
26
1
1
1
1
1
1
-1
1
1
1
1
1
1
1
-1
1
1
26
1
1
-1
1
1
-1
1
1
1
1
1
1
1
1
2
806
1
1
1
1
1
1
1
1
1
-1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
26
1
1
1
1
-1
1
1
1
1
1
1
1
1
1
1
-1
1
1
1
1
1
1
1
26
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
-1
1
1
1
1
1
-1
-1
1
1
1
26
26
1
-1
8...

result:

ok 200000 numbers

Test #45:

score: 0
Accepted
time: 560ms
memory: 422100kb

input:

200000
1712 30
1 446 58
570 1653
1 244 556
73 2933
1 64 675
3424 374
1 157 920
27 4788
1 252 533
5653 25
1 1067 134
3135 3702
1 1022 241
248 7758
2 308 717 936 102
7651 1519
4 3423 452 1674 2188 837 3014 4 3831
13012 48
3 1852 2598 4380 81 3689 770
1769 15529
2 1533 279 614 1184
623 18421
1 397 75
1...

output:

-1
23
36
26
26
26
26
26
26
28
28
36
26
26
19
916
26
26
26
-1
26
26
-1
36
28
23
26
36
60081
26
26
36
26
-1
-1
26
36
26
26
36
36
26
36
23
-1
36
26
36
36
26
26
28
26
26
36
36
-1
36
36
26
-1
26
36
28
26
23
28
36
36
36
-1
-1
80
-1
25
36
-1
25
26
28
28
26
36
36
-1
26
26
36
-1
-1
26
-1
26
36
-1
26
-1
26
36...

result:

ok 200000 numbers

Extra Test:

score: 0
Extra Test Passed