QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#89438#4063. 倍增myee100 ✓55ms8260kbC++116.3kb2023-03-20 07:20:272023-03-20 07:20:30

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-20 07:20:30]
  • 评测
  • 测评结果:100
  • 用时:55ms
  • 内存:8260kb
  • [2023-03-20 07:20:27]
  • 提交

answer

// 那就是希望。
// 即便需要取模,也是光明。

#ifdef MYEE
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#endif

// 打了个表
// [Done] exited with code=0 in 148.246 seconds
// [Done] exited with code=0 in 88.832 seconds
// [Done] exited with code=0 in 44.381 seconds

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
std::vector<uint>Sol[200005];
voi update(uint B){
    if(Sol[B].size())return;
    bol ok=false;
    for(uint p=2;!ok;p++){
        std::vector<uint>P;for(uint i=0;i<p;i++)P.push_back(i);
        while(!ok&&std::next_permutation(P.begin(),P.end())){
            if(P.back()==p-1)continue;
            for(uint S=1;!ok&&S<(1u<<(p-1));S++){
                std::vector<bol>Gone(p);
                std::vector<llt>Ans(p);
                ok=true;
                for(uint i=0;ok&&i<p;i++)if(!Gone[i]){
                    uint j=i,t=0;llt a=1,b=0,x;std::vector<std::pair<llt,llt> >V;
                    do 
                        V.push_back({a,b}),a*=2,b=2*b+(j?S>>(j-1)&1:0)-(S>>j&1?(llt)B:0),j=P[j];
                    while(j!=i);
                    x=b/(1-a);if(x<0||x>=B||b!=x*(1-a)){ok=false;break;}
                    do
                        Ans[j]=x*V[t].first+V[t].second,t++,Gone[j]=1,j=P[j];
                    while(j!=i);
                }
                if(ok)for(uint i=0;i<p;i++)ok&=S>>i&1?Ans[i]*2+(i?S>>(i-1)&1:0)>=B&&Ans[i]<B:Ans[i]>=0&&Ans[i]*2+(i?S>>(i-1)&1:0)<B;
                if(ok)for(uint i=0;i<p;i++)Sol[B].push_back(Ans[i]);
            }
        }
    }
}
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#endif
	Sol[1135]={832,529,1059,983,302,605,75,151,};
	Sol[8191]={2152,4304,417,835,1670,6681,5171,3340,};
	Sol[8380]={6145,3910,7821,7262,2234,4469,558,1117,};
	Sol[18145]={13306,8467,16935,15725,4838,9677,1209,2419,};
	Sol[24256]={6373,12746,1236,2473,4946,19785,15314,9892,};
	Sol[32131]={3081,6162,12324,24648,17165,2200,17606,4401,8803,};
	Sol[32635]={23932,15229,30459,28283,8702,17405,2175,4351,};
	Sol[40195]={29476,18757,37515,34835,10718,21437,2679,5359,};
	Sol[48385]={35482,22579,45159,41933,12902,25805,3225,6451,};
	Sol[52165]={38254,24343,48687,45209,13910,27821,3477,6955,};
	Sol[56386]={14815,29630,2874,5749,11498,45993,35600,22996,};
	Sol[58150]={42643,27136,54273,50396,15506,31013,3876,7753,};
	Sol[64135]={47032,29929,59859,55583,17102,34205,4275,8551,};
	Sol[64261]={7168,14336,28672,57344,50427,36594,35714,8928,17857,};
	Sol[66151]={37615,9079,18159,36318,25941,6485,51883,12970,};
	Sol[72010]={52807,33604,67209,62408,19202,38405,4800,9601,};
	Sol[72136]={34229,68458,64780,57425,42715,53182,13295,26591,};
	Sol[72640]={53269,33898,67797,62954,19370,38741,4842,9685,};
	Sol[80011]={75304,70597,61184,42358,4706,9413,18826,37652,};
	Sol[80641]={30675,61350,42059,3478,6957,55658,13914,27829,};
	Sol[81145]={59506,37867,75735,70325,21638,43277,5409,10819,};
	Sol[88390]={64819,41248,82497,76604,23570,47141,5892,11785,};
	Sol[92170]={67591,43012,86025,79880,24578,49157,6144,12289,};
	Sol[96265]={70594,44923,89847,83429,25670,51341,6417,12835,};
	Sol[98155]={71980,45805,91611,85067,26174,52349,6543,13087,};
	Sol[100171]={89957,79743,59316,18462,95064,73851,36925,47532,};
	Sol[112141]={105544,98947,85754,59368,6596,13193,26386,52772,};
	Sol[120016]={17414,34828,69656,19296,38593,68715,77186,34357,};
	Sol[120205]={88150,56095,112191,104177,32054,64109,8013,16027,};
	Sol[120646]={31699,63398,6150,12301,24602,98409,76172,49204,};
	Sol[129151]={100788,72425,15700,31401,122060,114969,125605,62802,};
	Sol[136270]={99931,63592,127185,118100,36338,72677,9084,18169,};
	Sol[136396]={64721,129442,122488,108581,80767,100558,25139,50279,};
	Sol[140176]={13193,26386,52772,105544,70912,6596,1649,3298,};
	Sol[144271]={135784,127297,110324,76378,8486,16973,33946,67892,};
	Sol[146161]={16049,32098,64196,128392,110623,75086,8024,4012,};
	Sol[152020]={111481,70942,141885,131750,40538,81077,10134,20269,};
	Sol[152146]={22076,44152,88304,24462,48925,87111,97850,43555,};
	Sol[160021]={92247,24473,126134,48947,97895,143077,71538,35769,};
	Sol[160651]={53131,106262,51873,103747,53445,46843,106891,93686,26722,};
	Sol[168211]={24407,48814,97628,27045,54091,96309,108182,48154,};
	Sol[169156]={1990,3980,7960,85573,127364,15920,31841,63682,};
	Sol[176275]={129268,82261,164523,152771,47006,94013,11751,23503,};
	Sol[180181]={43102,86204,172408,164635,149090,118000,111641,55820,};
	Sol[184150]={135043,85936,171873,159596,49106,98213,12276,24553,};
    // for(uint B=2;B<=200000;B++){
    //     update(B);
    //     if(B%1000==0)fprintf(stderr,"Now:%u\n",B),fflush(stderr);
    // }
    // for(uint i=2;i<=200000;i++){
    //     printf("\n%u:%u ",i,(uint)Sol[i].size());
    //     for(auto s:Sol[i])printf("%u,",s);
    //     if(Sol[i].size()>=8)
    //     {
    //         fprintf(stderr,"\tSol[%u]={",i);
    //         for(auto s:Sol[i])fprintf(stderr,"%u,",s);
    //         fprintf(stderr,"};\n");
    //     }
    // }
    uint t;scanf("%u",&t);
    while(t--){
        uint n,B;scanf("%u%u",&n,&B),update(B);
        if(Sol[B].size()>n)puts("-1");
        else{
            std::vector<uint>Ans=Sol[B];
            uint t=0;
            while(Ans[t]*2<B)t++;
            Ans.insert(Ans.begin()+t+1,n-Ans.size(),B-1);
            for(uint i=Ans.size()-1;~i;i--)
                printf("%u%c",Ans[i]," \n"[!i]);
        }
    }
    return 0;
}

// 那就是希望。
// 即便需要取模,也是光明。

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 4
Accepted
time: 1ms
memory: 7636kb

input:

10
4 4
8 3
8 3
1 4
2 2
6 5
2 3
8 8
3 2
7 2

output:

1 0 3 2
0 1 2 2 2 2 2 1
0 1 2 2 2 2 2 1
-1
0 1
1 4 4 4 4 3
-1
2 7 7 7 7 7 7 5
0 1 1
0 1 1 1 1 1 1

result:

ok Accepted

Test #2:

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

input:

10000
6 2
6 4
6 2
6 3
3 3
1 4
2 3
2 2
5 4
5 4
6 2
5 3
7 2
3 3
3 6
3 2
7 3
5 3
4 2
8 3
4 2
3 3
2 3
2 2
4 2
7 3
8 2
6 2
3 2
8 3
5 2
5 4
8 2
8 3
2 3
8 2
1 2
2 2
1 2
2 3
3 3
7 3
3 4
1 2
5 3
3 2
2 2
6 3
1 2
6 4
3 5
7 3
7 2
5 2
6 5
7 3
4 2
8 3
4 2
7 2
5 2
2 2
8 3
7 3
1 2
6 3
8 2
6 2
7 3
4 3
8 2
7 2
6 2
1 ...

output:

0 1 1 1 1 1
1 0 3 3 3 2
0 1 1 1 1 1
0 1 2 2 2 1
-1
-1
-1
0 1
1 0 3 3 2
1 0 3 3 2
0 1 1 1 1 1
0 1 2 2 1
0 1 1 1 1 1 1
-1
-1
0 1 1
0 1 2 2 2 2 1
0 1 2 2 1
0 1 1 1
0 1 2 2 2 2 2 1
0 1 1 1
-1
-1
0 1
0 1 1 1
0 1 2 2 2 2 1
0 1 1 1 1 1 1 1
0 1 1 1 1 1
0 1 1
0 1 2 2 2 2 2 1
0 1 1 1 1
1 0 3 3 2
0 1 1 1 1 1 1...

result:

ok Accepted

Test #3:

score: 4
Accepted
time: 15ms
memory: 8260kb

input:

10
2 3
4 2
2 4
192276 5
11 3
6 7
7492 2
8 2
197 8
2 3

output:

-1
0 1 1 1
-1
1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ...

result:

ok Accepted

Test #4:

score: 4
Accepted
time: 15ms
memory: 7760kb

input:

10000
7 2
84 2
8 3
1 2
7 2
2 3
10 2
4 3
6 2
8 3
1 2
2 2
37 2
380 2
7 2
3 2
7 2
8 2
8 3
6 2
5 2
6 3
5 2
29 2
2 3
2 2
5 2
7 3
4 2
3 2
4 2
1 2
6 2
8 2
5 4
1 2
5 4
8 2
1 2
6 2
8 3
6 2
6 3
4 2
32 2
6 3
1 2
3 2
7 4
4 2
3 5
7 2
434 4
5 2
1 2
8 2
24 2
5 2
5 2
6 2
4 2
1 6
2 3
7 2
5 4
10 2
10 5
8 2
4 3
8 2
3 ...

output:

0 1 1 1 1 1 1
0 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 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 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
0 1 2 2 2 2 2 1
-1
0 1 1 1 1 1 1
-1
0 1 1 1 1 1 1 1 1 1
0 1 2 1
0 1 1 1 1 1
0 1 2 2 2 2 2 1
-1
0 1
0 1 1 1 1 1 1 1 1 1...

result:

ok Accepted

Test #5:

score: 4
Accepted
time: 16ms
memory: 7744kb

input:

10000
3 3
1 2
48 2
3 2
7 3
2 2
61 2
6 3
6 2
7 3
3 3
3 2
4 2
4 2
6 2
1 3
6 2
4 2
127 2
51 3
5 6
6 2
51 6
7 2
6 2
4 3
7 2
2 6
3 2
3 2
3 2
8 2
6 3
7 4
3 4
4 2
8 2
5 3
8 3
6 2
6 2
2 4
5 2
4 2
3 3
5 3
2 2
8 2
2 3
5 3
12 2
7 3
5 2
6 4
4 3
2 2
3 3
4 2
5 3
3 3
5 2
8 2
5 2
2 2
7 2
5 2
7 2
8 2
2 2
1 3
7 2
5 2...

output:

-1
-1
0 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 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1
0 1 2 2 2 2 1
0 1
0 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 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 1 1
0 1 2 2 2 1
0 1 1 1 1 1
0 1 2 2 2 2 1
-1
0 1 1
0 1 1...

result:

ok Accepted

Test #6:

score: 4
Accepted
time: 2ms
memory: 7664kb

input:

100
1 10
2 11
8 3
8 3
2 3
8 3
1 5
5 7
2 4
6 5
7 10
10 7
8 3
8 10
7 4
6 5
10 4
2 5
4 2
5 3
2 3
4 6
7 3
6 8
8 10
6 7
5 5
2 2
4 12
7 2
2 8
5 15
4 13
6 5
6 10
2 12
1 4
3 5
8 9
1 3
8 8
4 3
5 5
4 13
7 2
5 4
3 5
8 2
2 7
1 4
2 5
6 3
1 5
8 11
9 10
3 12
2 6
4 5
5 4
3 2
7 5
8 4
2 9
4 3
6 9
1 5
7 8
4 2
10 4
15 ...

output:

-1
3 7
0 1 2 2 2 2 2 1
0 1 2 2 2 2 2 1
-1
0 1 2 2 2 2 2 1
-1
1 2 5 6 4
-1
1 4 4 4 4 3
1 2 5 8 9 7 4
1 2 5 6 6 6 6 6 6 4
0 1 2 2 2 2 2 1
1 2 5 8 9 9 7 4
1 0 3 3 3 3 2
1 4 4 4 4 3
1 0 3 3 3 3 3 3 3 2
1 3
0 1 1 1
0 1 2 2 1
-1
1 3 4 2
0 1 2 2 2 2 1
2 7 7 7 7 5
1 2 5 8 9 9 7 4
1 2 5 6 6 4
1 4 4 4 3
0 1
3...

result:

ok Accepted

Test #7:

score: 4
Accepted
time: 7ms
memory: 7700kb

input:

100
4 10
3 18
4 31
7 10
3 4
4 13
1 14
3 33
6 8
3 34
2 16
5 8
9 26
5 18
7 16
15 12
8 16
3 10
8 18
40 6
4 2
1 12
1 28
5 17
8 20
4 2
7 30
1 16
2 30
6 31
4 32
8 21
8 28
2 12
8 3
15 23
8 11
37 3
4 12
2 13
2 17
2 15
3 34
16 24
3 10
4 17
1 5
2 17
7 12
7 12
4 17
7 15
8 15
5 24
2 40
3 6
6 2
27 4
8 32
1 36
1 ...

output:

-1
5 2 10
-1
1 2 5 8 9 7 4
1 0 2
5 2 7 10
-1
-1
2 7 7 7 7 5
-1
-1
2 7 7 7 5
8 25 25 25 25 25 25 25 17
5 2 17 17 10
2 4 15 15 15 15 9
3 7 11 11 11 11 11 11 11 11 11 11 11 8 4
2 4 15 15 15 15 15 9
-1
5 2 17 17 17 17 17 10
1 3 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 4 2
...

result:

ok Accepted

Test #8:

score: 4
Accepted
time: 6ms
memory: 7676kb

input:

100
2 93
6 69
14 82
49 80
1 50
9 64
7 31
5 31
2 13
6 100
4 93
4 19
6 18
2 37
2 76
1 60
8 33
5 68
3 6
2 93
57 41
2 79
6 78
47 34
9 61
7 66
3 13
3 12
5 15
7 57
8 66
6 45
5 59
4 23
1 98
6 90
1 8
30 33
8 49
2 82
38 86
6 49
29 12
6 10
7 90
7 63
5 2
8 57
4 64
5 72
8 76
6 15
4 78
28 63
60 30
37 87
6 14
7 4...

output:

-1
22 45 68 68 46 23
16 32 65 81 81 81 81 81 81 81 81 81 81 49
26 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 53
-1
4 8 63 63 63 63 63 34 17
4 8 17 26 30 22 13
-1
-1
14 28 99 99 99 57
13 26 92 53
1 2 10 ...

result:

ok Accepted

Test #9:

score: 4
Accepted
time: 7ms
memory: 7724kb

input:

100
4 150
3 25
1 213
36 202
4 96
4 211
8 176
50 182
5 221
93 63
4 108
1 100
1 8
30 6
27 131
2 80
5 157
6 192
300 65
7 12
20 192
88 103
7 236
50 97
6 256
7 136
8 187
8 40
2 17
1 71
2 243
7 200
70 123
7 91
14 266
4 77
3 127
3 61
4 94
3 161
2 45
6 165
3 261
7 160
7 115
1 138
148 50
8 105
8 256
1 67
88 ...

output:

49 99 100 50
7 3 14
-1
40 80 161 201 201 201 201 201 201 201 201 201 201 201 201 201 201 201 201 201 201 201 201 201 201 201 201 201 201 201 201 201 201 201 201 121
31 63 64 32
-1
58 175 175 175 175 175 175 117
60 181 181 181 181 181 181 181 181 181 181 181 181 181 181 181 181 181 181 181 181 181 18...

result:

ok Accepted

Test #10:

score: 4
Accepted
time: 26ms
memory: 7712kb

input:

100
11 840
2 9
5 501
3 691
5 287
29 599
7 407
88 97
5 775
5 307
3 499
1 610
8 432
8 820
64 85
7 39
6 691
6 544
2 387
4 626
6 611
7 158
8 236
69 502
7 432
6 160
2 516
8 866
8 242
3 558
6 433
6 177
6 88
679 460
4 253
7 505
4 565
9 931
8 366
6 331
7 640
4 778
60 4
4 667
1 913
5 376
29 88
3 59
8 441
3 7...

output:

279 559 839 839 839 839 839 839 839 560 280
-1
143 71 500 500 286
-1
95 286 286 286 191
199 598 598 598 598 598 598 598 598 598 598 598 598 598 598 598 598 598 598 598 598 598 598 598 598 598 598 598 399
135 406 406 406 406 406 271
19 38 77 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96...

result:

ok Accepted

Test #11:

score: 4
Accepted
time: 41ms
memory: 7872kb

input:

100
7 1391
7 2313
8 1127
3 674
1 845
5 2167
25 2265
70 92
8 2611
453 586
7 667
8 2280
7 1891
1 2897
60 26
4 2325
7 945
3000 608
7 1351
23 25
71 1435
5 2518
7 2669
6 91
6 243
5 2596
7 2114
4 1864
19 283
5 2958
31 50
7 1642
2052 17
6 505
108 2099
7 1379
17 1078
1400 1516
7 902
5 2629
7 1981
6 91
9 565...

output:

463 1390 1390 1390 1390 1390 927
770 1541 2312 2312 2312 1542 771
375 1126 1126 1126 1126 1126 1126 751
224 673 449
-1
619 309 2166 2166 1238
647 323 2264 2264 2264 2264 2264 2264 2264 2264 2264 2264 2264 2264 2264 2264 2264 2264 2264 2264 2264 2264 2264 2264 1294
30 91 91 91 91 91 91 91 91 91 91 91...

result:

ok Accepted

Test #12:

score: 4
Accepted
time: 38ms
memory: 7708kb

input:

100
8 9451
1 1885
3 433
6 763
2 53
3 1590
6 8566
4 1807
2 1514
7 10720
4 2103
622 155
98 22
4 1096
2 878
2129 562
2 582
5 37
4 2043
8 353
183 1550
6 2129
1 664
2 368
4598 514
51 2
8 8191
9 8335
51 99
5 974
1444 1405
6 513
5 777
3121 1395
8 139
6 1585
7 2113
8 10891
58 79
1 1748
5 114
4 675
4 1299
68...

output:

2679 1339 5358 669 9450 5060 2530 1265
-1
-1
305 152 457 762 762 610
17 35
-1
2447 1223 4894 6118 7342 3671
361 722 1445 1084
504 1009
1531 3062 6125 9188 10719 7657 4594
700 1401 1402 701
51 154 154 154 154 154 154 154 154 154 154 154 154 154 154 154 154 154 154 154 154 154 154 154 154 154 154 154 ...

result:

ok Accepted

Test #13:

score: 4
Accepted
time: 44ms
memory: 7772kb

input:

100
4 5
43 6
19 5
5 2
76 92
36 31
1 2
7 8
73 37
7 6541
9 196
5 3190
6 47755
3 4
8 5
8 7066
31 13
3 6
53 17
50000 6
6 6
10400 5
4591 2
3 3
6 2
6 11
2 2
6 2
1 4
36 74
7219 4
6 5
4 6
6 4
62 6
7 9
5 5
8 2
2 4
98 83
5 4
61 40
5 4
3 3
215 10
5 4
33830 10
12 2
8 11
8 9
10 12
1 6
6 2
6 3580
3 2
1943 6
8 283...

output:

1 4 4 3
1 3 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 4 2
1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3
0 1 1 1 1
30 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91...

result:

ok Accepted

Test #14:

score: 4
Accepted
time: 41ms
memory: 7844kb

input:

100
47 11
30210 3
7 2
8 72136
1 2
56 50
7 3
8 1270
4 4
5 4
72 90
1 9
7 7
5 7
7 5
29 3
6 7
5931 3
12 7
8 3
6 6
7 7
2 4
8 2
435 6
182 3
7 48385
7 5
80 3
8 4
1 3
9 160
7 346
8 17326
8952 4
2 3
1799 3
6 3
8 61
7 4
70 99
6 2
6 5
1091 2
8 3
3 5
1 9
8 3
8 7
2 2
4 4
14 94
13586 5
58 90
4 2
7 4
6 1216
8 3
38...

output:

3 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 7
0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...

result:

ok Accepted

Test #15:

score: 4
Accepted
time: 26ms
memory: 7656kb

input:

1500
101 13
103 130
109 39
102 108
104 52
105 165
100 28
105 103
100 42
108 37
100 144
105 160
105 13
105 113
111 25
107 61
101 126
103 97
111 20
105 146
140 14
107 35
103 123
103 12
105 142
108 92
100 64
106 74
107 78
106 165
108 13
108 42
102 19
104 66
101 33
103 22
100 17
100 84
101 104
104 98
10...

output:

5 2 7 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 10
...

result:

ok Accepted

Test #16:

score: 4
Accepted
time: 55ms
memory: 7684kb

input:

1300
108 88
103 212
105 174
542 39
108 110
218 262
106 28
103 166
103 47
102 11
101 41
108 193
101 288
107 131
101 6
101 206
103 125
1434 115
104 118
146 29
105 165
107 28
106 32
102 79
102 186
107 225
106 36
105 39
102 56
210 20
102 7
101 26
105 159
104 93
108 260
107 204
101 168
103 38
103 137
151...

output:

25 12 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 ...

result:

ok Accepted

Test #17:

score: 4
Accepted
time: 50ms
memory: 7740kb

input:

1000
106 3
101 391
102 2
101 3
108 2
106 3
100 2
108 2
102 3
107 3
845 2
108 2
103 2
106 2
231 2
103 4
102 2
105 2
108 2
103 2
106 2
131 2
102 2
108 2
107 2
100 2
100 2
108 2
104 2
108 2
112 2
100 2
100 2
242 4
1895 2
104 2
106 2
105 2
100 3
986 3
136 2
103 2
112 2
104 3
102 3
103 2
104 2
100 2
107 ...

output:

0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1
55 223 111 335 167 390 390 390 390 390 390 390 390 390 390 390 390 390 390 390 390 390 3...

result:

ok Accepted

Test #18:

score: 4
Accepted
time: 12ms
memory: 7892kb

input:

10000
4 5
7 2
4 83
3 68
2 8
1 47
15 5
2 2
5 2
2 2
6 68
1 5
6 56
3 2
2 17
1 80
6 5
7 17
8 8
6 41
8 89
9 14
7 32
5 17
2 2
76 23
8 2
7 20
6 5
2 38
3 5
8 53
3 5
1 86
2 23
4 2
3 2
6 2
2 44
2 53
245 77
4 32
4 8
2 2
6 5
7 2
1 2
7 8
1 2
5 2
1 29
1 2
7 2
6 62
3 20
3 35
130 2
5 8
7 14
6 17
4 2
6 14
3 2
6 14
8...

output:

1 4 4 3
0 1 1 1 1 1 1
27 82 82 55
22 67 45
2 5
-1
1 4 4 4 4 4 4 4 4 4 4 4 4 4 3
0 1
0 1 1 1 1
0 1
22 67 67 67 67 45
-1
18 55 55 55 55 37
0 1 1
5 11
-1
1 4 4 4 4 3
5 16 16 16 16 16 11
2 7 7 7 7 7 7 5
13 40 40 40 40 27
29 88 88 88 88 88 88 59
4 13 13 13 13 13 13 13 9
10 31 31 31 31 31 21
5 16 16 16 11...

result:

ok Accepted

Test #19:

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

input:

10000
4 2
6 2
7 35
8 53
7 14
1 20
8 2
2 2
47 59
8 5
4 77
6 2
5 26
3 26
1 2
4 2
7 41
8 74
3 2
3 2
5 5
5 14
7 32
3 5
3 2
6 2
4 32
5 44
4 14
8 32
6 8
6 2
7 2
15 2
1 8
3 2
7 2
2 11
8 44
1 5
1 56
4 23
1 14
4 5
1 5
1 2
1 8
8 50
90 2
1 8
2 2
154 2
6 2
4 2
1 44
4 56
177 2
6 17
1 2
7 5
1 11
8 56
7 2
6 2
6 17...

output:

0 1 1 1
0 1 1 1 1 1
11 34 34 34 34 34 23
17 52 52 52 52 52 52 35
4 13 13 13 13 13 9
-1
0 1 1 1 1 1 1 1
0 1
19 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 39
1 4 4 4 4 4 4 3
25 76 76 51
0 1 1 1 1 1
8 25 25 25 1...

result:

ok Accepted

Test #20:

score: 4
Accepted
time: 13ms
memory: 7740kb

input:

10000
1 12
144 3
6 3
5 48
1 18
2 21
6 45
3 42
5 18
8 3
7 3
8 6
7 39
2 3
7 15
2 3
2 6
1 3
49 27
2 54
6 39
8 3
8 30
1 3
4 3
8 3
6 54
7 12
3 39
8 42
6 12
8 9
7 12
15 6
6 24
6 3
3 27
5 3
7 3
5 27
3 3
4 15
5 45
7 36
3 9
8 6
1 51
162 12
4 18
7 3
4 72
1 21
6 3
120 3
10 15
1 21
3 3
5 63
2 9
2 9
3 33
8 63
3 ...

output:

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

result:

ok Accepted

Test #21:

score: 4
Accepted
time: 22ms
memory: 7892kb

input:

10000
1 54
4 3
265 18
406 3
2 66
2 21
3 51
6 69
18 6
3 3
137 3
6 54
1 3
2 15
2 30
6 18
4 63
1 9
396 6
3 6
1 30
155 3
9 66
3 57
4 39
1 54
7 30
3 21
1 15
7 15
2 3
3 27
2 3
92 12
2 21
3 3
4 15
3 45
7 27
44 6
8 3
8 12
3 15
8 15
5 3
7 30
1 3
2 12
8 3
4 12
2 96
8 33
5 3
5 3
4 9
9 3
2 54
4 3
5 6
1 3
110 3
...

output:

-1
0 1 2 1
5 2 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 ...

result:

ok Accepted

Test #22:

score: 4
Accepted
time: 11ms
memory: 7708kb

input:

10000
6 18
4 37
4 40
1 16
6 6
8 14
7 7
4 12
5 32
7 29
2 13
4 39
1 10
1 27
6 31
3 11
6 14
8 32
6 16
6 13
7 10
4 8
1 42
24 18
6 7
1 37
7 4
6 8
7 13
6 26
8 34
3 38
3 21
4 7
60 15
2 29
6 29
8 27
4 36
7 32
5 31
1 22
3 7
3 12
8 32
3 13
3 5
7 30
5 37
3 27
6 18
2 29
6 23
8 24
5 17
36 12
4 24
8 19
2 11
6 22
...

output:

5 2 17 17 17 10
5 10 36 21
-1
-1
1 3 5 5 4 2
4 13 13 13 13 13 13 9
1 2 5 6 6 6 4
3 7 8 4
10 31 31 31 21
9 28 28 28 28 28 19
-1
11 5 38 22
-1
-1
4 8 17 26 22 13
3 10 7
4 13 13 13 13 9
10 31 31 31 31 31 31 21
2 4 15 15 15 9
5 2 7 12 12 10
1 2 5 8 9 7 4
2 7 7 5
-1
5 2 17 17 17 17 17 17 17 17 17 17 17 1...

result:

ok Accepted

Test #23:

score: 4
Accepted
time: 39ms
memory: 7824kb

input:

10000
8 4
5 4
1 3
7 23
6 32
1 25
8 23
1 7
5 29
6 23
8 18
1 28
8 30
3 20
6 39
8 36
1 16
393 3
5 3
3 28
8 19
6 5
6 7
8 5
5 6
2 35
1 24
5 19
7 4
1 9
4 13
3 22
4 16
6 21
1 15
7 9
8 29
8 10
17 14
2 27
8 13
2 18
5 17
8 23
44 32
7 11
18 13
3 7
1 20
6 37
3 2
2 3
3 2
304 17
132 5
14 20
5 10
2 40
5 2
2 18
6 7...

output:

1 0 3 3 3 3 3 2
1 0 3 3 2
-1
7 22 22 22 22 22 15
10 31 31 31 31 21
-1
7 22 22 22 22 22 22 15
-1
9 28 28 28 19
7 22 22 22 22 15
5 2 17 17 17 17 17 10
-1
4 8 29 29 29 29 29 17
6 19 13
11 5 38 38 38 22
11 23 35 35 35 35 24 12
-1
0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

result:

ok Accepted

Test #24:

score: 4
Accepted
time: 39ms
memory: 7896kb

input:

10000
4 2
12 2
5 2
5 2
234 2
6 2
7 2
14 2
368 2
6 2
8 2
8 2
8 2
8 2
7 2
2 2
2 2
8 2
5 2
3 2
6 2
7 2
7 2
7 2
4 2
5 2
55 2
8 2
3 2
3 2
2 2
8 2
11 2
2 2
8 2
8 2
31 2
8 2
8 2
192 2
4 2
8 2
2 2
2 2
4 2
7 2
2 2
3 3
7 2
5 2
1 2
2 2
2 2
1 2
8 2
5 2
17 2
7 2
4 2
151 2
4 2
6 2
8 2
5 2
8 2
2 2
68 2
6 2
1 2
6 2...

output:

0 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 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 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 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 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 1 1 1 1 1 1 1 ...

result:

ok Accepted

Test #25:

score: 4
Accepted
time: 36ms
memory: 7804kb

input:

10000
7 2
2 2
6 2
3 2
6 2
3 2
7 2
6 2
6 2
2 2
1 2
4 2
3 2
57 2
7 2
8 2
44 2
3 2
6 2
3 2
332 2
3 2
8 2
7 2
4 2
8 2
4 2
2 2
6 2
36 2
5 2
2 2
8 2
2 2
8 2
3 2
4 2
7 2
3 2
6 2
8 2
7 2
8 2
18 2
8 2
8 2
4 2
2 2
7 2
8 2
2 3
8 2
3 2
5 2
4 3
4 2
6 2
1 2
3 2
4 2
2 2
5 2
3 2
135 2
3 2
4 2
6 2
3 2
361 2
7 2
5 2
...

output:

0 1 1 1 1 1 1
0 1
0 1 1 1 1 1
0 1 1
0 1 1 1 1 1
0 1 1
0 1 1 1 1 1 1
0 1 1 1 1 1
0 1 1 1 1 1
0 1
-1
0 1 1 1
0 1 1
0 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 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
0 1 1 1 1 1 1
0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed