QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#620353#8939. Permutationzzpcd#AC ✓684ms23248kbC++202.3kb2024-10-07 17:41:012024-10-07 17:41:02

Judging History

This is the latest submission verdict.

  • [2024-10-07 17:41:02]
  • Judged
  • Verdict: AC
  • Time: 684ms
  • Memory: 23248kb
Show
  • [2024-10-07 17:41:01]
  • Submitted

answer

#include<bits/stdc++.h>
#define ll long long
#define P make_pair
using namespace std;
int n;
const double k = 0.629;
int ask(int l, int r) {
    if(l == r) return -1;
    cout << "? " << l << ' ' << r << endl;
    int x;
    cin >> x;
    return x;
}
void answer(int x) {
    cout << "! " << x << endl;
    return;
}
pair<int,ll> f[1000001];
int deg[1000001];
void solve(int l, int r, int sec = -1) {
    if(l == r) {
        answer(l);
        return;
    }
    if(sec == -1) sec = ask(l, r);
    if(l + 1 == r) {
        answer(l == sec ? r : l);
        return;
    }
    int mid = deg[r-l+1];
    if(l + mid - 1 >= sec) {
        mid = l + mid - 1;
        int u = ask(l, mid);
        if(u == sec) {
            return solve(l, mid, sec);
        } else return solve(mid + 1, r, -1);
    } else {
        mid = r - mid + 1;
        int u = ask(mid, r);
        if(u == sec) {
            return solve(mid, r, sec);
        } else return solve(l, mid - 1, -1);
    }
}
void init()
{
    int mx=0;
    memset(f,0x3f,sizeof(f));
    f[1]=P(0,0);
    f[2]=P(0,0),deg[2]=1;
    for(int i=3;i<=1000000;++i)
    {
        if(i<=1000)
        for(int j=(i+1)/2;j<=i;++j)
        {
            if(f[i]>max(P(f[j].first+1,f[j].second+j),P(f[i-j].first+2,f[i-j].second+i)))
            {
                f[i]=max(P(f[j].first+1,f[j].second+j),P(f[i-j].first+2,f[i-j].second+i));
                deg[i]=j;
            }
        }
        else
        {
            for(int j=i*k-100;j<=i*k+100;++j)
            if(f[i]>max(P(f[j].first+1,f[j].second+j),P(f[i-j].first+2,f[i-j].second+i)))
            {
                f[i]=max(P(f[j].first+1,f[j].second+j),P(f[i-j].first+2,f[i-j].second+i));
                deg[i]=j;
            }
        }
        // if(f[i].first+1>ceil(1.5*log2(i))||f[i].second>2*i)
        // {
        //     cout<<i<<" "<<ceill((long double)1.5*log2l(i))<<" "<<f[i].first+1<<" "<<f[i].second<<endl;
        //     exit(0);
        // }    
        // if(deg[i]*2<i)
        // {
        //     cout<<"er";
        //     exit(0);
        // }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    init();
    while(T--) {
        int n;
        cin >> n;
        solve(1, n);
    }
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 507ms
memory: 23248kb

input:

3
5
3
2
5
6
6
3
1
4
3
3

output:

? 1 5
? 1 3
? 4 5
! 4
? 1 6
? 3 6
? 1 2
! 2
? 1 4
? 3 4
! 4

result:

ok Correct (3 test cases)

Test #2:

score: 0
Accepted
time: 615ms
memory: 23244kb

input:

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

output:

? 1 10
? 1 6
? 1 4
? 1 2
? 3 4
! 4
? 1 10
? 5 10
? 7 10
? 5 6
! 6
? 1 10
? 1 6
? 7 10
? 9 10
? 7 8
! 7
? 1 10
? 1 6
? 1 4
? 3 4
! 3
? 1 10
? 5 10
? 1 4
? 3 4
? 1 2
! 1
? 1 10
? 1 6
? 1 4
? 3 4
? 1 2
! 1
? 1 10
? 1 6
? 7 10
? 9 10
? 7 8
! 8
? 1 10
? 1 6
? 7 10
? 7 8
! 7
? 1 10
? 1 6
? 7 10
? 9 10
! 1...

result:

ok Correct (10000 test cases)

Test #3:

score: 0
Accepted
time: 581ms
memory: 23168kb

input:

10000
3
1
2
11
5
5
5
5
2
2
19
3
3
4
11
11
11
7
5
7
1
2
3
3
3
19
6
6
6
6
5
4
2
2
15
11
11
11
11
10
14
1
1
1
3
5
16
4
4
4
1
5
3
3
2
19
13
17
5
5
5
4
2
2
4
1
2
3
7
2
2
2
3
2
2
17
1
1
1
2
6
14
9
9
9
7
11
20
9
9
9
6
11
10
6
4
2
5
18
7
7
7
7
6
9
8
8
8
6
5
8
6
6
6
5
16
10
10
10
10
10
6
1
1
2
3
10
3
3
4
6
2...

output:

? 1 3
? 1 2
! 3
? 1 11
? 1 6
? 3 6
? 5 6
! 6
? 1 2
! 1
? 1 19
? 1 11
? 1 6
? 7 11
? 9 11
? 10 11
! 10
? 1 7
? 4 7
? 1 3
? 1 2
! 3
? 1 3
? 2 3
! 2
? 1 19
? 1 11
? 1 6
? 3 6
? 5 6
? 3 4
! 3
? 1 2
! 1
? 1 15
? 7 15
? 7 11
? 9 11
? 10 11
! 9
? 1 14
? 1 8
? 1 5
? 1 3
? 4 5
! 4
? 1 16
? 1 10
? 1 6
? 1 4
?...

result:

ok Correct (10000 test cases)

Test #4:

score: 0
Accepted
time: 602ms
memory: 23132kb

input:

10000
47
23
23
24
11
9
2
1
5
14
8
2
9
9
9
25
6
6
4
13
12
15
7
4
2
6
6
9
2
2
2
2
27
27
27
27
27
24
23
21
7
7
7
7
6
5
43
41
21
7
7
8
4
3
1
22
6
12
14
17
20
19
21
34
29
29
25
17
17
18
14
42
20
20
20
20
20
20
19
17
47
21
21
21
21
21
19
17
41
25
11
30
33
36
36
36
19
17
17
16
9
9
10
21
14
14
14
14
14
13
2...

output:

? 1 47
? 1 29
? 12 29
? 1 11
? 6 11
? 1 5
? 1 3
? 4 5
! 4
? 1 14
? 1 8
? 9 14
? 9 12
? 9 10
! 10
? 1 25
? 1 15
? 1 9
? 10 15
? 10 13
? 14 15
! 14
? 1 7
? 1 4
? 5 7
? 5 6
! 5
? 1 9
? 1 5
? 1 3
? 1 2
! 1
? 1 27
? 12 27
? 18 27
? 22 27
? 24 27
? 22 23
! 22
? 1 21
? 1 13
? 1 8
? 4 8
? 6 8
? 4 5
! 4
? 1 ...

result:

ok Correct (10000 test cases)

Test #5:

score: 0
Accepted
time: 632ms
memory: 23184kb

input:

10000
100
47
61
93
96
71
71
71
71
71
9
2
2
2
1
53
46
35
6
6
6
6
6
6
33
3
16
31
31
31
29
32
82
60
41
29
29
29
28
23
24
26
88
39
8
59
59
59
59
59
59
59
71
24
29
59
49
65
65
64
61
92
52
45
88
88
88
88
85
91
91
24
11
11
9
5
5
6
3
66
51
51
45
29
28
39
40
42
92
43
43
50
20
20
20
20
20
19
48
1
1
1
1
5
9
9
...

output:

? 1 100
? 1 61
? 62 100
? 77 100
? 62 76
? 68 76
? 68 72
? 70 72
? 70 71
! 70
? 1 9
? 1 5
? 1 3
? 1 2
! 3
? 1 53
? 22 53
? 1 21
? 1 13
? 1 8
? 4 8
? 4 6
? 5 6
! 5
? 1 33
? 1 20
? 21 33
? 26 33
? 29 33
? 29 31
? 32 33
! 33
? 1 82
? 33 82
? 1 32
? 14 32
? 22 32
? 27 32
? 22 26
? 22 24
? 25 26
! 25
? 1...

result:

ok Correct (10000 test cases)

Test #6:

score: 0
Accepted
time: 625ms
memory: 23196kb

input:

10000
50
10
10
10
10
6
2
3
5
50
11
11
9
31
26
23
23
22
50
44
44
40
20
20
21
26
25
50
24
14
45
45
40
49
48
46
50
50
50
50
50
50
49
45
50
36
23
17
17
18
12
11
10
50
29
29
20
3
3
3
3
50
30
30
22
1
1
1
2
4
50
25
25
25
25
21
30
31
27
50
18
20
49
47
37
37
35
39
50
9
9
9
5
17
19
14
13
50
26
26
26
28
17
17
...

output:

? 1 50
? 1 31
? 1 19
? 1 11
? 6 11
? 1 5
? 1 3
? 4 5
! 4
? 1 50
? 1 31
? 1 19
? 20 31
? 25 31
? 20 24
? 22 24
? 22 23
! 24
? 1 50
? 20 50
? 32 50
? 20 31
? 20 26
? 20 23
? 24 26
? 25 26
! 24
? 1 50
? 1 31
? 32 50
? 40 50
? 40 45
? 46 50
? 48 50
? 46 47
! 47
? 1 50
? 20 50
? 32 50
? 40 50
? 45 50
? 4...

result:

ok Correct (10000 test cases)

Test #7:

score: 0
Accepted
time: 617ms
memory: 23196kb

input:

10000
100
76
49
35
34
5
3
11
11
11
100
29
29
29
29
29
29
30
26
26
100
64
64
69
88
88
86
78
77
81
100
51
57
98
98
92
79
79
77
81
100
44
44
50
13
13
13
12
9
9
100
64
92
22
19
27
25
35
36
39
100
93
93
86
56
59
40
44
49
48
47
100
37
2
97
81
76
76
74
68
68
100
76
76
58
94
95
80
79
86
85
83
100
32
32
11
5...

output:

? 1 100
? 40 100
? 1 39
? 16 39
? 1 15
? 1 9
? 10 15
? 10 13
? 10 11
! 10
? 1 100
? 1 61
? 1 37
? 15 37
? 24 37
? 24 31
? 27 31
? 24 26
? 25 26
! 25
? 1 100
? 40 100
? 40 76
? 77 100
? 77 90
? 83 90
? 77 82
? 77 80
? 81 82
! 82
? 1 100
? 1 61
? 62 100
? 77 100
? 87 100
? 77 86
? 77 82
? 77 80
? 81 8...

result:

ok Correct (10000 test cases)

Test #8:

score: 0
Accepted
time: 537ms
memory: 23244kb

input:

1000
1000
475
426
728
728
747
831
831
828
841
841
837
844
842
845
1000
278
17
974
811
757
751
637
637
628
652
647
640
641
643
1000
75
128
871
985
644
686
713
713
712
732
730
742
742
741
1000
239
239
45
577
607
432
429
442
458
459
459
460
466
465
1000
978
978
978
978
978
978
997
914
914
920
927
927
9...

output:

? 1 1000
? 1 618
? 619 1000
? 619 854
? 619 764
? 765 854
? 800 854
? 800 833
? 834 854
? 834 846
? 834 841
? 842 846
? 842 844
? 845 846
! 846
? 1 1000
? 1 618
? 619 1000
? 765 1000
? 619 764
? 675 764
? 619 674
? 619 652
? 619 639
? 640 652
? 645 652
? 640 644
? 640 642
? 643 644
! 644
? 1 1000
? ...

result:

ok Correct (1000 test cases)

Test #9:

score: 0
Accepted
time: 522ms
memory: 23196kb

input:

1017
272
246
111
27
52
73
73
73
73
73
71
75
114
105
91
2
2
2
2
2
2
2
910
173
173
173
173
127
14
14
29
35
37
44
47
48
48
726
229
229
229
201
63
63
28
17
17
13
24
24
24
861
315
104
671
671
688
593
593
593
593
593
590
597
597
596
1984
133
133
133
406
571
512
724
704
688
673
650
650
650
650
649
647
1145...

output:

? 1 272
? 105 272
? 1 104
? 1 64
? 65 104
? 65 88
? 65 78
? 71 78
? 71 75
? 71 73
? 74 75
! 74
? 1 114
? 45 114
? 1 44
? 1 27
? 1 16
? 1 10
? 1 6
? 1 4
? 1 2
! 1
? 1 910
? 1 562
? 1 347
? 1 214
? 83 214
? 1 82
? 1 50
? 1 31
? 32 50
? 32 42
? 43 50
? 43 47
? 48 50
? 48 49
! 49
? 1 726
? 1 448
? 1 277...

result:

ok Correct (1017 test cases)

Test #10:

score: 0
Accepted
time: 511ms
memory: 23196kb

input:

10
100000
3893
3893
30673
43582
43582
43582
43582
43582
43582
43582
43582
43582
43470
43242
43242
43197
43289
43289
43279
43268
43263
43273
43273
43272
100000
32066
54928
68197
71764
88585
88585
88585
86972
89959
89772
90979
90917
91257
91159
91415
91410
91370
91370
91355
91348
91349
91354
91354
913...

output:

? 1 100000
? 1 62800
? 1 39401
? 39402 62800
? 39402 54018
? 39402 48495
? 39402 45021
? 41549 45021
? 41549 43694
? 42369 43694
? 42876 43694
? 43189 43694
? 43383 43694
? 43189 43382
? 43189 43308
? 43189 43262
? 43263 43308
? 43263 43290
? 43274 43290
? 43263 43273
? 43263 43268
? 43269 43273
? 4...

result:

ok Correct (10 test cases)

Test #11:

score: 0
Accepted
time: 507ms
memory: 23132kb

input:

21
84335
47947
47947
22445
9296
1509
17079
17079
17079
17079
16598
17510
17510
17510
17566
17352
17352
17352
17346
17323
17323
17323
17323
17323
159962
128177
145530
35270
7423
54814
49869
40850
38954
43214
43214
43550
43823
43823
43823
43765
43675
43675
43670
43695
43695
43695
43695
43695
43696
436...

output:

? 1 84335
? 1 52946
? 19744 52946
? 1 19743
? 1 12318
? 12319 19743
? 15155 19743
? 15155 17990
? 16239 17990
? 16239 17320
? 17321 17990
? 17321 17734
? 17321 17576
? 17419 17576
? 17321 17418
? 17321 17380
? 17321 17357
? 17335 17357
? 17321 17334
? 17321 17328
? 17321 17325
? 17321 17323
? 17322 ...

result:

ok Correct (21 test cases)

Test #12:

score: 0
Accepted
time: 674ms
memory: 23116kb

input:

1
1000000
641602
641602
418256
783270
783270
783270
783270
783270
786055
802269
802269
802788
797591
797591
797591
797004
796734
796559
796850
796850
796850
796850
796844
796864
796864
796864
796864
796863
796861

output:

? 1 1000000
? 371101 1000000
? 371101 766578
? 766579 1000000
? 766579 913300
? 766579 858766
? 766579 824464
? 766579 802888
? 766579 789316
? 789317 802888
? 794453 802888
? 797676 802888
? 794453 797675
? 795684 797675
? 796445 797675
? 796916 797675
? 796445 796915
? 796445 796735
? 796736 79691...

result:

ok Correct (1 test case)

Test #13:

score: 0
Accepted
time: 540ms
memory: 23184kb

input:

16
232936
229707
229707
229707
229707
229707
229707
229707
229707
231039
227478
227478
227474
225790
225790
225611
225474
225474
225474
225466
225417
225417
225409
225419
225421
225423
8676
6498
6498
6498
6498
5867
4978
4978
5022
4731
4731
4717
4684
4684
4676
4692
4692
4690
4695
221085
172303
209705...

output:

? 1 232936
? 86521 232936
? 140942 232936
? 175173 232936
? 196704 232936
? 210247 232936
? 218765 232936
? 224123 232936
? 227490 232936
? 224123 227489
? 225409 227489
? 226204 227489
? 225409 226203
? 225409 225899
? 225597 225899
? 225409 225596
? 225409 225524
? 225409 225479
? 225436 225479
? ...

result:

ok Correct (16 test cases)

Test #14:

score: 0
Accepted
time: 562ms
memory: 23128kb

input:

1994
667
666
667
255
254
98
97
38
37
15
14
6
5
2
374
373
374
143
142
55
54
21
20
8
7
3
2
488
486
488
187
186
72
71
28
27
11
10
5
4
2
922
921
922
353
352
135
134
52
51
20
19
8
7
3
2
639
637
639
244
243
94
93
36
35
14
13
6
5
2
353
350
353
135
134
52
51
20
19
8
7
3
2
71
66
71
27
26
11
10
5
4
2
24
21
24...

output:

? 1 667
? 256 667
? 1 255
? 99 255
? 1 98
? 39 98
? 1 38
? 16 38
? 1 15
? 7 15
? 1 6
? 3 6
? 1 2
! 1
? 1 374
? 144 374
? 1 143
? 56 143
? 1 55
? 22 55
? 1 21
? 9 21
? 1 8
? 4 8
? 1 3
? 2 3
! 1
? 1 488
? 188 488
? 1 187
? 73 187
? 1 72
? 29 72
? 1 28
? 12 28
? 1 11
? 6 11
? 1 5
? 3 5
? 1 2
! 1
? 1 92...

result:

ok Correct (1994 test cases)

Test #15:

score: 0
Accepted
time: 525ms
memory: 23120kb

input:

18
153667
153667
153666
57111
57110
21289
21288
7999
7998
3056
3055
1168
1167
446
445
171
170
66
65
26
25
10
9
4
3
2
211376
211374
211376
78521
78520
29232
29231
10946
10945
4161
4160
1590
1589
608
607
233
232
89
88
34
33
13
12
5
4
2
195330
195326
195330
72568
72567
27023
27022
10126
10125
3857
3856...

output:

? 1 153667
? 57112 153667
? 1 57111
? 21290 57111
? 1 21289
? 8000 21289
? 1 7999
? 3057 7999
? 1 3056
? 1169 3056
? 1 1168
? 447 1168
? 1 446
? 172 446
? 1 171
? 67 171
? 1 66
? 27 66
? 1 26
? 11 26
? 1 10
? 5 10
? 1 4
? 3 4
? 1 2
! 1
? 1 211376
? 78522 211376
? 1 78521
? 29233 78521
? 1 29232
? 10...

result:

ok Correct (18 test cases)

Test #16:

score: 0
Accepted
time: 684ms
memory: 23196kb

input:

1
1000000
999998
1000000
371100
371099
137779
137778
51217
51216
19102
19101
7187
7186
2746
2745
1049
1048
401
400
154
153
59
58
23
22
9
8
4
3
2

output:

? 1 1000000
? 371101 1000000
? 1 371100
? 137780 371100
? 1 137779
? 51218 137779
? 1 51217
? 19103 51217
? 1 19102
? 7188 19102
? 1 7187
? 2747 7187
? 1 2746
? 1050 2746
? 1 1049
? 402 1049
? 1 401
? 155 401
? 1 154
? 60 154
? 1 59
? 24 59
? 1 23
? 10 23
? 1 9
? 5 9
? 1 4
? 3 4
? 1 2
! 1

result:

ok Correct (1 test case)

Test #17:

score: 0
Accepted
time: 553ms
memory: 23128kb

input:

1994
667
666
454
27
27
27
27
27
28
2
2
2
2
2
374
372
224
91
96
29
29
16
12
8
5
3
2
488
485
370
161
156
44
44
43
15
14
6
7
3
2
922
921
662
40
40
40
40
40
36
18
12
7
8
3
2
639
639
421
215
147
68
72
2
2
2
2
2
2
2
353
351
200
91
81
27
27
22
2
2
2
2
2
71
71
47
6
6
6
6
3
2
24
22
24
7
9
2
2
567
563
332
205...

output:

? 1 667
? 256 667
? 1 255
? 1 157
? 1 97
? 1 60
? 1 37
? 15 37
? 1 14
? 1 8
? 1 5
? 1 3
? 1 2
! 1
? 1 374
? 144 374
? 1 143
? 56 143
? 1 55
? 1 34
? 14 34
? 1 13
? 6 13
? 1 5
? 3 5
? 1 2
! 1
? 1 488
? 188 488
? 1 187
? 73 187
? 1 72
? 1 44
? 18 44
? 1 17
? 8 17
? 1 7
? 4 7
? 1 3
? 2 3
! 1
? 1 922
? ...

result:

ok Correct (1994 test cases)

Test #18:

score: 0
Accepted
time: 524ms
memory: 23116kb

input:

18
153667
153667
65961
50668
47562
8350
8350
5820
1644
1644
1644
1499
306
306
198
24
24
24
24
24
16
7
9
3
4
2
211376
211375
91641
67652
36438
4235
4235
4235
4235
4235
3075
973
973
961
221
221
163
79
60
10
10
10
8
2
2
2
195330
195325
161600
36944
36944
17928
1018
1018
1018
1018
1018
1018
923
281
281
...

output:

? 1 153667
? 57112 153667
? 1 57111
? 21290 57111
? 1 21289
? 1 13290
? 5032 13290
? 1 5031
? 1 3109
? 1 1921
? 735 1921
? 1 734
? 1 453
? 174 453
? 1 173
? 1 107
? 1 66
? 1 40
? 1 24
? 11 24
? 1 10
? 5 10
? 1 4
? 3 4
? 1 2
! 1
? 1 211376
? 78522 211376
? 1 78521
? 29233 78521
? 1 29232
? 1 18286
? ...

result:

ok Correct (18 test cases)

Test #19:

score: 0
Accepted
time: 676ms
memory: 23120kb

input:

1
1000000
999998
783271
169408
169408
188270
8002
8002
8002
8002
8002
8002
6079
1522
1522
1781
42
42
42
42
42
42
62
18
13
4
4
4
3
2

output:

? 1 1000000
? 371101 1000000
? 1 371100
? 1 233321
? 86664 233321
? 1 86663
? 1 54411
? 1 34124
? 1 21363
? 1 13337
? 1 8288
? 3167 8288
? 1 3166
? 1 1956
? 748 1956
? 1 747
? 1 461
? 1 285
? 1 176
? 1 108
? 1 66
? 27 66
? 1 26
? 11 26
? 1 10
? 1 6
? 1 4
? 3 4
? 1 2
! 1

result:

ok Correct (1 test case)

Test #20:

score: 0
Accepted
time: 679ms
memory: 23120kb

input:

1
999999
260772
507886
955966
996647
730076
730076
730076
730076
717528
706326
706326
705072
701051
701051
701051
700522
701488
701488
701453
701361
701361
701361
701361
701361
701359
701353
701355
701358

output:

? 1 999999
? 1 628899
? 628900 999999
? 766679 999999
? 628900 766678
? 680117 766678
? 680117 734463
? 700380 734463
? 713126 734463
? 700380 713125
? 700380 708296
? 703404 708296
? 700380 703403
? 700380 702248
? 700380 701534
? 700380 701092
? 701093 701534
? 701262 701534
? 701367 701534
? 7012...

result:

ok Correct (1 test case)

Test #21:

score: 0
Accepted
time: 675ms
memory: 23248kb

input:

1
999998
295598
295598
73514
537464
537464
537464
537464
537464
537464
537464
537464
537464
537464
537464
536777
535510
535839
536097
536002
536162
536162
536156
536177
536178
536195
536197
536202
536201
536198

output:

? 1 999998
? 1 628898
? 1 395476
? 395477 628898
? 395477 542198
? 450011 542198
? 484313 542198
? 505889 542198
? 519461 542198
? 527997 542198
? 533366 542198
? 533366 538824
? 535452 538824
? 535452 537535
? 536248 537535
? 535452 536247
? 535452 535943
? 535944 536247
? 535944 536131
? 536132 53...

result:

ok Correct (1 test case)

Test #22:

score: 0
Accepted
time: 678ms
memory: 23240kb

input:

1
999997
339297
339297
355318
613666
489939
413343
417456
471212
473604
453304
453304
453304
453304
453304
453304
453304
453059
452873
452842
452945
452950
453017
453017
453017
453019
453013
453010
453009

output:

? 1 999997
? 1 628898
? 1 395476
? 395477 628898
? 482177 628898
? 395477 482176
? 395477 449910
? 449911 482176
? 461982 482176
? 449911 461981
? 449911 457402
? 449911 454540
? 451680 454540
? 451680 453447
? 452356 453447
? 452773 453447
? 453031 453447
? 452773 453030
? 452773 452931
? 452932 45...

result:

ok Correct (1 test case)

Test #23:

score: 0
Accepted
time: 671ms
memory: 23196kb

input:

1
999996
578161
472988
665875
665875
726172
785834
797735
839217
830420
853100
853969
859775
859775
859775
859775
859775
859584
859300
859300
859300
859303
859239
859239
859239
859239
859239
859240
859237

output:

? 1 999996
? 1 628897
? 628898 999996
? 628898 862218
? 628898 775555
? 775556 862218
? 775556 829966
? 829967 862218
? 829967 850152
? 850153 862218
? 850153 857641
? 857642 862218
? 857642 860469
? 858723 860469
? 858723 859801
? 859135 859801
? 859390 859801
? 859135 859389
? 859233 859389
? 8592...

result:

ok Correct (1 test case)

Test #24:

score: 0
Accepted
time: 590ms
memory: 23184kb

input:

2
500000
114103
114103
98381
290103
281943
220637
207866
237265
236565
226042
226042
226042
224910
226572
226572
226450
226739
226739
226739
226728
226759
226748
226770
226769
226776
226776
226776
500000
313297
313297
313297
313297
246160
217669
198510
230101
228136
222822
222213
223239
223495
22511...

output:

? 1 500000
? 1 314400
? 1 197657
? 197658 314400
? 241070 314400
? 197658 241069
? 197658 224863
? 224864 241069
? 230977 241069
? 224864 230976
? 224864 228641
? 224864 227198
? 224864 226306
? 226307 227198
? 226307 226857
? 226307 226646
? 226647 226857
? 226647 226776
? 226697 226776
? 226697 22...

result:

ok Correct (2 test cases)

Test #25:

score: 0
Accepted
time: 595ms
memory: 23128kb

input:

2
499999
493493
493493
493493
493493
493493
493493
487773
459196
453608
466355
465991
468187
468187
468187
467811
467320
467320
467320
467320
467329
467345
467345
467345
467344
467338
467339
467341
499999
101651
101651
101651
101651
98374
24247
24247
18123
9237
9237
8975
6574
6338
4671
4671
4669
426...

output:

? 1 499999
? 185601 499999
? 302344 499999
? 375775 499999
? 421963 499999
? 451015 499999
? 469289 499999
? 451015 469288
? 451015 462408
? 462409 469288
? 462409 466660
? 466661 469288
? 466661 468284
? 467282 468284
? 467665 468284
? 467282 467664
? 467282 467517
? 467282 467427
? 467282 467371
?...

result:

ok Correct (2 test cases)

Test #26:

score: 0
Accepted
time: 585ms
memory: 23200kb

input:

2
499998
367462
193038
152483
183238
53076
53076
60946
29299
27151
37492
37153
39670
39670
39670
39518
40342
40342
40342
40342
40331
40280
40275
40296
40296
40293
40290
40291
499998
122343
122343
3768
313385
313385
278240
246144
246144
244788
252131
252131
252131
252079
253733
253733
253610
253302
2...

output:

? 1 499998
? 185601 499998
? 1 185600
? 68959 185600
? 1 68958
? 25685 68958
? 41840 68958
? 25685 41839
? 25685 35745
? 35746 41839
? 35746 39511
? 39512 41839
? 39512 40949
? 39512 40399
? 39512 40059
? 40060 40399
? 40190 40399
? 40271 40399
? 40271 40349
? 40302 40349
? 40271 40301
? 40271 40289...

result:

ok Correct (2 test cases)

Test #27:

score: 0
Accepted
time: 595ms
memory: 23120kb

input:

2
499997
274071
274071
274071
302688
167121
159831
135636
135636
135636
135636
137448
132171
131482
133080
133080
132896
132679
132623
132781
132781
132768
132743
132743
132743
132740
132746
132745
499997
242708
242708
242708
310592
160791
117737
177106
177106
172524
164685
164685
164685
164155
1630...

output:

? 1 499997
? 1 314398
? 116743 314398
? 190174 314398
? 116743 190173
? 144086 190173
? 116743 144085
? 126988 144085
? 126988 137641
? 131041 137641
? 133563 137641
? 131041 133562
? 131041 132598
? 132599 133562
? 132599 133193
? 132827 133193
? 132599 132826
? 132599 132739
? 132740 132826
? 1327...

result:

ok Correct (2 test cases)

Test #28:

score: 0
Accepted
time: 583ms
memory: 23184kb

input:

10000
2
1
2
2
3
2
1
3
3
3
3
1
2
3
1
1
3
3
2
3
2
2
4
3
3
4
4
4
4
2
1
3
4
2
1
4
4
4
3
1
4
3
4
1
4
3
3
4
4
4
4
2
1
3
4
2
1
4
4
4
3
1
4
3
4
1
4
1
2
3
4
1
2
4
4
1
2
3
4
1
2
4
4
1
1
4
1
1
4
4
3
2
4
3
4
2
4
4
3
2
4
3
4
2
4
2
2
4
2
2
5
4
4
3
5
5
5
5
5
3
2
4
5
3
2
5
5
5
5
4
5
4
4
4
5
4
4
3
5
5
5
5
5
3
2
4
5
...

output:

? 1 2
! 2
? 1 2
! 1
? 1 3
? 1 2
! 3
? 1 3
? 2 3
! 2
? 1 3
? 1 2
! 3
? 1 3
? 1 2
! 2
? 1 3
? 2 3
! 1
? 1 3
? 1 2
! 1
? 1 4
? 3 4
! 4
? 1 4
? 3 4
! 3
? 1 4
? 1 2
? 3 4
! 4
? 1 4
? 1 2
? 3 4
! 3
? 1 4
? 3 4
? 1 2
! 2
? 1 4
? 3 4
? 1 2
! 2
? 1 4
? 3 4
! 4
? 1 4
? 3 4
! 3
? 1 4
? 1 2
? 3 4
! 4
? 1 4
? 1 ...

result:

ok Correct (10000 test cases)

Test #29:

score: 0
Accepted
time: 609ms
memory: 23248kb

input:

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

output:

? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 6 7
! 7
? 1 8
? 1 5
? 6 8
? 7 8
! 6
? 1 8
? 1 5
? 6 8
? 6 7
! 6
? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 7 8
! 7
? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 6 7
! 7
? 1 8
? 1 5
? 6 8
? 7 8
! 6
? 1 8
? 1 5
? 6 8
? 6 7
! 6
? 1 8
? 1 5
? 1 3
? ...

result:

ok Correct (10000 test cases)

Test #30:

score: 0
Accepted
time: 617ms
memory: 23160kb

input:

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

output:

? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 7 8
! 7
? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 6 7
! 7
? 1 8
? 1 5
? 6 8
? 7 8
! 6
? 1 8
? 1 5
? 6 8
? 6 7
! 6
? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 7 8
! 7
? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 6 7
! 7
? 1 8
? 1 5
? 6 8
? ...

result:

ok Correct (10000 test cases)

Test #31:

score: 0
Accepted
time: 573ms
memory: 23200kb

input:

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

output:

? 1 8
? 1 5
? 6 8
? 7 8
! 6
? 1 8
? 1 5
? 6 8
? 6 7
! 6
? 1 8
? 1 5
? 1 3
? 4 5
! 5
? 1 8
? 1 5
? 1 3
? 4 5
! 5
? 1 8
? 1 5
? 1 3
? 4 5
! 5
? 1 8
? 1 5
? 1 3
? 4 5
! 5
? 1 8
? 1 5
? 1 3
? 4 5
! 5
? 1 8
? 1 5
? 1 3
? 4 5
! 5
? 1 8
? 1 5
? 1 3
? 4 5
! 4
? 1 8
? 1 5
? 1 3
? 4 5
! 4
? 1 8
? 1 5
? 1 3
? ...

result:

ok Correct (10000 test cases)

Test #32:

score: 0
Accepted
time: 588ms
memory: 23200kb

input:

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

output:

? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 6 7
! 7
? 1 8
? 1 5
? 6 8
? 7 8
! 6
? 1 8
? 1 5
? 6 8
? 6 7
! 6
? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 7 8
! 7
? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 6 7
! 7
? 1 8
? 1 5
? 6 8
? 7 8
! 6
? 1 8
? 1 5
? 6 8
? 6 7
! 6
? 1 8
? 1 5
? 1 3
? ...

result:

ok Correct (10000 test cases)

Test #33:

score: 0
Accepted
time: 652ms
memory: 23112kb

input:

10000
9
3
5
8
8
9
3
5
9
9
9
3
5
7
6
8
9
3
5
7
6
9
9
3
5
9
8
6
9
3
5
8
9
6
9
3
5
8
8
9
3
5
9
9
9
3
5
7
6
8
9
3
5
7
6
9
9
3
5
9
8
6
9
3
5
8
9
6
9
3
5
6
7
8
9
3
5
6
7
9
9
3
5
6
7
8
9
3
5
6
7
9
9
3
5
6
6
9
3
5
6
6
9
3
5
9
8
7
9
3
5
8
9
7
9
3
5
9
8
7
9
3
5
8
9
7
9
3
5
7
7
9
3
5
7
7
9
3
5
8
8
9
3
5
9
9
9
...

output:

? 1 9
? 1 5
? 6 9
? 8 9
! 9
? 1 9
? 1 5
? 6 9
? 8 9
! 8
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 9
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 8
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 8 9
! 9
? 1 9
? 1 5
? 6 9
? 8 9
! 8
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 9
? 1 9
? 1 5
? 6 9
...

result:

ok Correct (10000 test cases)

Test #34:

score: 0
Accepted
time: 554ms
memory: 23120kb

input:

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

output:

? 1 9
? 1 5
? 6 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 6 7
! 6
? 1 9
? 1 5
? 1 3
? 4 5
! 5
? 1 9
? 1 5
? 1 3
? 4 5
...

result:

ok Correct (10000 test cases)

Test #35:

score: 0
Accepted
time: 585ms
memory: 23192kb

input:

10000
9
3
2
7
6
8
9
3
2
7
6
9
9
3
2
9
8
6
9
3
2
8
9
6
9
3
2
6
7
8
9
3
2
6
7
9
9
3
2
6
7
8
9
3
2
6
7
9
9
3
2
6
6
9
3
2
6
6
9
3
2
9
8
7
9
3
2
8
9
7
9
3
2
9
8
7
9
3
2
8
9
7
9
3
2
7
7
9
3
2
7
7
9
3
2
8
8
9
3
2
9
9
9
3
2
7
6
8
9
3
2
7
6
9
9
3
2
9
8
6
9
3
2
8
9
6
9
3
2
8
8
9
3
2
9
9
9
3
2
7
6
8
9
3
2
7
6
...

output:

? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 9
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 8
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 9
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 8
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 9
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 8
? 1 9
? 1 5
? 6 9
? 6 7
! 7
...

result:

ok Correct (10000 test cases)

Test #36:

score: 0
Accepted
time: 564ms
memory: 23180kb

input:

10000
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
...

output:

? 1 9
? 1 5
? 1 3
? 4 5
! 4
? 1 9
? 1 5
? 1 3
? 4 5
! 4
? 1 9
? 1 5
? 1 3
? 4 5
! 4
? 1 9
? 1 5
? 1 3
? 4 5
! 4
? 1 9
? 1 5
? 1 3
? 4 5
! 4
? 1 9
? 1 5
? 1 3
? 4 5
! 4
? 1 9
? 1 5
? 1 3
? 4 5
! 4
? 1 9
? 1 5
? 1 3
? 4 5
! 4
? 1 9
? 1 5
? 1 3
? 4 5
! 4
? 1 9
? 1 5
? 1 3
? 4 5
! 4
? 1 9
? 1 5
? 1 3
? ...

result:

ok Correct (10000 test cases)

Test #37:

score: 0
Accepted
time: 595ms
memory: 23240kb

input:

10000
9
4
3
6
6
9
4
3
6
6
9
4
3
9
8
7
9
4
3
8
9
7
9
4
3
9
8
7
9
4
3
8
9
7
9
4
3
7
7
9
4
3
7
7
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
...

output:

? 1 9
? 1 5
? 6 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 6 7
! 6
? 1 9
? 1 5
? 3 5
? 3 4
! 5
? 1 9
? 1 5
? 3 5
? 3 4
...

result:

ok Correct (10000 test cases)

Test #38:

score: 0
Accepted
time: 600ms
memory: 23196kb

input:

10000
9
4
3
7
6
8
9
4
3
7
6
9
9
4
3
9
8
6
9
4
3
8
9
6
9
4
3
6
7
8
9
4
3
6
7
9
9
4
3
6
7
8
9
4
3
6
7
9
9
4
3
6
6
9
4
3
6
6
9
4
3
9
8
7
9
4
3
8
9
7
9
4
3
9
8
7
9
4
3
8
9
7
9
4
3
7
7
9
4
3
7
7
9
4
3
8
8
9
4
3
9
9
9
4
3
7
6
8
9
4
3
7
6
9
9
4
3
9
8
6
9
4
3
8
9
6
9
4
3
8
8
9
4
3
9
9
9
4
3
7
6
8
9
4
3
7
6
...

output:

? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 9
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 8
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 9
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 8
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 9
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 8
? 1 9
? 1 5
? 6 9
? 6 7
! 7
...

result:

ok Correct (10000 test cases)

Test #39:

score: 0
Accepted
time: 589ms
memory: 23116kb

input:

10000
9
8
8
8
7
9
9
9
9
9
9
7
7
5
8
9
7
7
5
9
9
9
9
9
8
9
8
8
8
8
9
8
8
8
7
9
9
9
9
9
9
7
7
5
8
9
7
7
5
9
9
9
9
9
8
9
8
8
8
8
9
6
6
5
8
9
6
6
5
9
9
6
6
5
8
9
6
6
5
9
9
6
6
6
5
9
6
6
6
5
9
9
9
8
5
9
8
8
9
5
9
9
9
7
5
9
8
8
7
5
9
7
7
7
7
9
7
7
7
7
9
5
3
8
8
9
5
3
9
9
9
5
3
7
6
8
9
5
3
7
6
9
9
5
3
9
8
...

output:

? 1 9
? 5 9
? 7 9
? 7 8
! 9
? 1 9
? 5 9
? 7 9
? 8 9
! 8
? 1 9
? 5 9
? 5 7
? 8 9
! 9
? 1 9
? 5 9
? 5 7
? 8 9
! 8
? 1 9
? 5 9
? 7 9
? 8 9
! 7
? 1 9
? 5 9
? 7 9
? 7 8
! 7
? 1 9
? 5 9
? 7 9
? 7 8
! 9
? 1 9
? 5 9
? 7 9
? 8 9
! 8
? 1 9
? 5 9
? 5 7
? 8 9
! 9
? 1 9
? 5 9
? 5 7
? 8 9
! 8
? 1 9
? 5 9
? 7 9
? ...

result:

ok Correct (10000 test cases)

Test #40:

score: 0
Accepted
time: 602ms
memory: 23180kb

input:

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

output:

? 1 9
? 1 5
? 6 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 6 7
! 6
? 1 9
? 1 5
? 1 3
? 4 5
! 5
? 1 9
? 1 5
? 1 3
? 4 5
...

result:

ok Correct (10000 test cases)

Test #41:

score: 0
Accepted
time: 593ms
memory: 23180kb

input:

10000
9
7
7
6
8
9
7
7
6
9
9
9
9
9
8
9
8
8
8
8
9
6
6
7
8
9
6
6
7
9
9
6
6
7
8
9
6
6
7
9
9
6
6
6
5
9
6
6
6
5
9
9
9
8
5
9
8
8
9
5
9
9
9
7
5
9
8
8
7
5
9
7
7
7
7
9
7
7
7
7
9
8
8
8
7
9
9
9
9
9
9
7
7
5
8
9
7
7
5
9
9
9
9
9
8
9
8
8
8
8
9
8
8
8
7
9
9
9
9
9
9
7
7
6
8
9
7
7
6
9
9
9
9
9
8
9
8
8
8
8
9
6
6
5
8
9
6
...

output:

? 1 9
? 5 9
? 5 7
? 8 9
! 9
? 1 9
? 5 9
? 5 7
? 8 9
! 8
? 1 9
? 5 9
? 7 9
? 8 9
! 7
? 1 9
? 5 9
? 7 9
? 7 8
! 7
? 1 9
? 5 9
? 5 7
? 8 9
! 9
? 1 9
? 5 9
? 5 7
? 8 9
! 8
? 1 9
? 5 9
? 5 7
? 8 9
! 9
? 1 9
? 5 9
? 5 7
? 8 9
! 8
? 1 9
? 5 9
? 5 7
? 5 6
! 7
? 1 9
? 5 9
? 5 7
? 5 6
! 7
? 1 9
? 5 9
? 7 9
? ...

result:

ok Correct (10000 test cases)

Test #42:

score: 0
Accepted
time: 561ms
memory: 23116kb

input:

10000
9
8
8
8
7
9
9
9
9
9
9
7
7
5
8
9
7
7
5
9
9
9
9
9
8
9
8
8
8
8
9
8
8
8
7
9
9
9
9
9
9
7
7
5
8
9
7
7
5
9
9
9
9
9
8
9
8
8
8
8
9
6
6
5
8
9
6
6
5
9
9
6
6
5
8
9
6
6
5
9
9
6
6
6
5
9
6
6
6
5
9
9
9
8
5
9
8
8
9
5
9
9
9
7
5
9
8
8
7
5
9
7
7
7
7
9
7
7
7
7
9
5
3
8
8
9
5
3
9
9
9
5
3
7
6
8
9
5
3
7
6
9
9
5
3
9
8
...

output:

? 1 9
? 5 9
? 7 9
? 7 8
! 9
? 1 9
? 5 9
? 7 9
? 8 9
! 8
? 1 9
? 5 9
? 5 7
? 8 9
! 9
? 1 9
? 5 9
? 5 7
? 8 9
! 8
? 1 9
? 5 9
? 7 9
? 8 9
! 7
? 1 9
? 5 9
? 7 9
? 7 8
! 7
? 1 9
? 5 9
? 7 9
? 7 8
! 9
? 1 9
? 5 9
? 7 9
? 8 9
! 8
? 1 9
? 5 9
? 5 7
? 8 9
! 9
? 1 9
? 5 9
? 5 7
? 8 9
! 8
? 1 9
? 5 9
? 7 9
? ...

result:

ok Correct (10000 test cases)

Test #43:

score: 0
Accepted
time: 565ms
memory: 23200kb

input:

10000
9
5
3
6
6
9
5
3
6
6
9
5
3
9
8
7
9
5
3
8
9
7
9
5
3
9
8
7
9
5
3
8
9
7
9
5
3
7
7
9
5
3
7
7
9
9
9
8
6
9
8
8
9
6
9
9
9
7
6
9
8
8
7
6
9
7
7
7
6
9
7
7
7
6
9
9
9
8
6
9
8
8
9
6
9
9
9
7
6
9
8
8
7
6
9
7
7
7
6
9
7
7
7
6
9
9
9
8
6
9
8
8
9
6
9
9
9
7
6
9
8
8
7
6
9
7
7
7
6
9
7
7
7
6
9
6
6
6
6
9
6
6
6
6
9
6
6
...

output:

? 1 9
? 1 5
? 6 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 6 7
! 6
? 1 9
? 5 9
? 7 9
? 5 6
! 5
? 1 9
? 5 9
? 7 9
? 5 6
...

result:

ok Correct (10000 test cases)

Test #44:

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

input:

10000
9
2
3
7
6
8
9
2
3
7
6
9
9
2
3
9
8
6
9
2
3
8
9
6
9
2
3
6
7
8
9
2
3
6
7
9
9
2
3
6
7
8
9
2
3
6
7
9
9
2
3
6
6
9
2
3
6
6
9
2
3
9
8
7
9
2
3
8
9
7
9
2
3
9
8
7
9
2
3
8
9
7
9
2
3
7
7
9
2
3
7
7
9
2
3
8
8
9
2
3
9
9
9
2
3
7
6
8
9
2
3
7
6
9
9
2
3
9
8
6
9
2
3
8
9
6
9
2
3
8
8
9
2
3
9
9
9
2
3
7
6
8
9
2
3
7
6
...

output:

? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 9
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 8
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 9
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 8
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 9
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 8
? 1 9
? 1 5
? 6 9
? 6 7
! 7
...

result:

ok Correct (10000 test cases)

Test #45:

score: 0
Accepted
time: 536ms
memory: 23196kb

input:

10000
9
9
8
3
3
9
8
9
3
3
9
9
7
3
3
9
8
7
3
3
9
7
9
3
3
9
7
8
3
3
9
9
8
3
3
9
8
9
3
3
9
9
7
3
3
9
8
7
3
3
9
7
9
3
3
9
7
8
3
3
9
9
6
3
3
9
8
6
3
3
9
9
6
3
3
9
8
6
3
3
9
7
6
3
3
9
7
6
3
3
9
6
9
3
3
9
6
8
3
3
9
6
9
3
3
9
6
8
3
3
9
6
7
3
3
9
6
7
3
3
9
9
5
3
3
9
8
5
3
3
9
9
5
3
3
9
8
5
3
3
9
7
5
3
3
9
7
...

output:

? 1 9
? 5 9
? 1 4
? 3 4
! 4
? 1 9
? 5 9
? 1 4
? 3 4
! 4
? 1 9
? 5 9
? 1 4
? 3 4
! 4
? 1 9
? 5 9
? 1 4
? 3 4
! 4
? 1 9
? 5 9
? 1 4
? 3 4
! 4
? 1 9
? 5 9
? 1 4
? 3 4
! 4
? 1 9
? 5 9
? 1 4
? 3 4
! 4
? 1 9
? 5 9
? 1 4
? 3 4
! 4
? 1 9
? 5 9
? 1 4
? 3 4
! 4
? 1 9
? 5 9
? 1 4
? 3 4
! 4
? 1 9
? 5 9
? 1 4
? ...

result:

ok Correct (10000 test cases)

Test #46:

score: 0
Accepted
time: 620ms
memory: 23128kb

input:

10000
9
4
5
6
6
9
4
5
6
6
9
4
5
9
8
7
9
4
5
8
9
7
9
4
5
9
8
7
9
4
5
8
9
7
9
4
5
7
7
9
4
5
7
7
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
...

output:

? 1 9
? 1 5
? 6 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 6 7
! 6
? 1 9
? 1 5
? 6 9
? 6 7
! 6
? 1 9
? 1 5
? 3 5
? 3 4
! 5
? 1 9
? 1 5
? 3 5
? 3 4
...

result:

ok Correct (10000 test cases)

Test #47:

score: 0
Accepted
time: 590ms
memory: 23196kb

input:

10000
9
4
2
7
6
8
9
4
2
7
6
9
9
4
2
9
8
6
9
4
2
8
9
6
9
4
2
6
7
8
9
4
2
6
7
9
9
4
2
6
7
8
9
4
2
6
7
9
9
4
2
6
6
9
4
2
6
6
9
4
2
9
8
7
9
4
2
8
9
7
9
4
2
9
8
7
9
4
2
8
9
7
9
4
2
7
7
9
4
2
7
7
9
4
2
8
8
9
4
2
9
9
9
4
2
7
6
8
9
4
2
7
6
9
9
4
2
9
8
6
9
4
2
8
9
6
9
4
2
8
8
9
4
2
9
9
9
4
2
7
6
8
9
4
2
7
6
...

output:

? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 9
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 8
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 8 9
? 6 7
! 7
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 9
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 8
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 9
? 1 9
? 1 5
? 6 9
? 6 7
? 8 9
! 8
? 1 9
? 1 5
? 6 9
? 6 7
! 7
...

result:

ok Correct (10000 test cases)

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-02-08 17:02:26 | OpenSource Project