QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#858289#8939. PermutationI_like_magicAC ✓149ms3584kbC++141.5kb2025-01-16 15:40:302025-01-16 15:40:39

Judging History

This is the latest submission verdict.

  • [2025-01-16 15:40:39]
  • Judged
  • Verdict: AC
  • Time: 149ms
  • Memory: 3584kb
Show
  • [2025-01-16 15:40:30]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
constexpr double phi = 0.618;
constexpr int N = 0, P = 0;
int n;
int pos;
void solve(int l, int r) {
    if(l == r) {
        cout << "! " << l << endl;
        return ;
    }
    if(l == r - 1) {
        if(pos == l) cout << "! " << r << endl;
        else cout << "! " << l << endl;
        return ;
    }
    int len = (r - l + 1) / (1 + phi);
    if(l == r - 2) {
        len ++;
    } 
    if(pos <= l + len - 1) {
        int ps = 0;
        if(l < l + len - 1) {
            cout << "? " << l << " " << l + len - 1 << endl;
            cin >> ps;
        }
        if(ps == pos) {
            solve(l, l + len - 1);
        } else {
            if(l + len < r) {
                cout << "? " << (l + len) << " " << r << endl;
                cin >> pos;
            }
            solve(l + len, r);
        }
    } else {
        int ps = 0;
        if(r - len + 1 < r) {
            cout << "? " << r - len + 1 << " " << r << endl;
            cin >> ps;
        }
        if(ps == pos) {
            solve(r - len + 1, r);
        } else {
            if(l < r - len) {
                cout << "? " << l << " " << r - len << endl;
                cin >> pos;
            }
            solve(l, r - len);
        }
    }
}
int Main() {
    cin >> n;
    cout << "? " << 1 << " " << n << endl;
    cin >> pos;
    solve(1, n);
    return 0;
}
int main() {
    int t;
    cin >> t;
    while(t --) {
        Main();
    }
    return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok Correct (3 test cases)

Test #2:

score: 0
Accepted
time: 149ms
memory: 3584kb

input:

10000
10
2
2
3
5
5
10
10
10
8
5
5
10
5
1
10
9
8
10
4
4
6
2
1
10
10
6
3
4
2
10
3
3
3
2
10
1
5
9
10
7
10
1
3
8
8
10
2
4
9
9
10
3
3
1
5
5
10
4
1
7
8
9
10
8
7
1
2
4
10
4
1
9
9
10
7
7
7
6
10
5
1
7
8
10
10
8
8
8
9
10
2
2
1
5
4
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
4
4
10
8
7
4...

output:

? 1 10
? 1 6
? 1 3
? 4 6
? 4 5
! 4
? 1 10
? 5 10
? 8 10
? 5 7
? 5 6
! 6
? 1 10
? 1 6
? 7 10
? 9 10
? 7 8
! 7
? 1 10
? 1 6
? 4 6
? 1 3
? 1 2
! 3
? 1 10
? 5 10
? 1 4
? 3 4
? 1 2
! 1
? 1 10
? 1 6
? 1 3
? 2 3
! 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 ...

result:

ok Correct (10000 test cases)

Test #3:

score: 0
Accepted
time: 78ms
memory: 3584kb

input:

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

output:

? 1 3
? 1 2
! 3
? 1 11
? 1 6
? 4 6
? 4 5
! 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
? 4 6
? 1 3
? 1 2
! 3
? 1 2
! 1
? 1 15
? 7 15
? 7 11
? 9 11
? 10 11
! 9
? 1 14
? 1 8
? 1 4
? 1 2
? 3 4
! 4
? 1 16
? 1 9
? 1 5
? 6 9
? ...

result:

ok Correct (10000 test cases)

Test #4:

score: 0
Accepted
time: 106ms
memory: 3584kb

input:

10000
47
23
23
24
11
9
2
1
5
14
8
2
9
9
9
25
6
6
4
13
13
13
7
4
2
6
6
9
2
2
2
2
27
27
27
27
24
19
20
21
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
19
17
47
21
21
21
21
21
20
19
19
41
25
11
30
33
36
36
35
38
19
17
17
16
9
9
10
21
14
14
14
15
1...

output:

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

result:

ok Correct (10000 test cases)

Test #5:

score: 0
Accepted
time: 126ms
memory: 3456kb

input:

10000
100
47
61
93
96
71
71
71
71
71
9
2
2
2
1
53
46
35
6
6
6
6
7
4
33
3
16
31
31
31
30
32
82
60
41
29
29
29
28
23
24
26
88
39
8
59
59
59
59
59
59
71
24
29
59
44
65
65
64
61
61
92
52
45
88
88
88
88
85
89
89
24
11
11
9
5
5
5
66
51
51
45
29
28
39
36
40
40
92
43
43
50
20
20
20
21
17
17
48
1
1
1
1
5
9
1...

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 12
? 1 7
? 4 7
? 6 7
? 4 5
! 5
? 1 33
? 1 20
? 21 33
? 26 33
? 30 33
? 30 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: 130ms
memory: 3584kb

input:

10000
50
10
10
10
10
6
2
3
5
50
11
11
9
23
23
23
22
25
50
44
44
40
21
21
21
22
23
50
24
14
45
45
40
49
48
46
50
50
50
50
50
50
49
47
47
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
30
29
50
18
20
49
47
37
37
37
50
9
9
9
5
17
18
14
13
50
26
26
26
28
17
19
...

output:

? 1 50
? 1 30
? 1 18
? 1 11
? 6 11
? 1 5
? 1 3
? 4 5
! 4
? 1 50
? 1 30
? 1 18
? 19 30
? 19 25
? 22 25
? 22 23
? 24 25
! 24
? 1 50
? 21 50
? 33 50
? 21 32
? 21 27
? 21 24
? 21 22
? 23 24
! 24
? 1 50
? 1 30
? 31 50
? 39 50
? 39 45
? 46 50
? 48 50
? 46 47
! 47
? 1 50
? 21 50
? 33 50
? 40 50
? 45 50
? 4...

result:

ok Correct (10000 test cases)

Test #7:

score: 0
Accepted
time: 138ms
memory: 3456kb

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
80
81
100
51
57
98
98
92
79
79
77
81
80
100
44
44
50
13
13
13
12
9
10
7
100
64
92
22
19
27
25
35
36
39
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
10...

output:

? 1 100
? 40 100
? 1 39
? 16 39
? 1 15
? 1 9
? 10 15
? 10 12
? 10 11
! 10
? 1 100
? 1 61
? 1 37
? 16 37
? 25 37
? 25 32
? 29 32
? 25 28
? 25 26
! 25
? 1 100
? 40 100
? 40 76
? 77 100
? 77 90
? 83 90
? 77 82
? 77 79
? 80 82
? 80 81
! 82
? 1 100
? 1 61
? 62 100
? 77 100
? 87 100
? 77 86
? 77 82
? 77 7...

result:

ok Correct (10000 test cases)

Test #8:

score: 0
Accepted
time: 26ms
memory: 3584kb

input:

1000
1000
475
426
728
728
747
831
831
828
841
837
847
847
847
847
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
463
463
1000
978
978
978
978
978
978
997
914
914
920
932
929
9...

output:

? 1 1000
? 1 618
? 619 1000
? 619 854
? 619 763
? 764 854
? 799 854
? 799 832
? 833 854
? 833 845
? 846 854
? 846 850
? 846 848
? 846 847
! 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: 26ms
memory: 3584kb

input:

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

output:

? 1 272
? 105 272
? 1 104
? 1 64
? 65 104
? 65 88
? 65 78
? 71 78
? 71 74
? 73 74
! 74
? 1 114
? 45 114
? 1 44
? 1 27
? 1 16
? 1 9
? 1 5
? 1 3
? 1 2
! 1
? 1 910
? 1 562
? 1 347
? 1 214
? 83 214
? 1 82
? 1 50
? 1 30
? 31 50
? 31 42
? 43 50
? 43 46
? 47 50
? 47 48
? 49 50
! 49
? 1 726
? 1 448
? 1 276
...

result:

ok Correct (1017 test cases)

Test #10:

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

input:

10
100000
3893
3893
30673
43582
43582
43582
43582
43582
43582
43582
43582
43582
43470
43385
43385
43359
43289
43289
43290
43279
43278
43273
43273
43272
100000
32066
54928
68197
71764
88585
88585
85554
93282
94213
91599
91599
91599
91599
91474
91410
91410
91398
91348
91348
91341
91355
91354
91351
913...

output:

? 1 100000
? 1 61804
? 1 38197
? 38198 61804
? 38198 52787
? 38198 47214
? 38198 43769
? 40327 43769
? 41643 43769
? 42456 43769
? 42958 43769
? 43269 43769
? 43461 43769
? 43269 43460
? 43269 43386
? 43315 43386
? 43269 43314
? 43269 43296
? 43280 43296
? 43269 43279
? 43274 43279
? 43269 43273
? 4...

result:

ok Correct (10 test cases)

Test #11:

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

input:

21
84335
47947
47947
22445
9296
1509
19830
19830
19830
19815
17079
17079
17079
17084
17352
17352
17352
17346
17316
17308
17320
17320
17320
17321
159962
128177
145530
35270
7423
54814
49869
40850
38954
43550
43550
43550
43550
43550
43489
43765
43765
43753
43675
43670
43689
43689
43685
43691
43690
436...

output:

? 1 84335
? 1 52122
? 19910 52122
? 1 19909
? 1 12304
? 12305 19909
? 15210 19909
? 17006 19909
? 18116 19909
? 17006 18115
? 17006 17691
? 17006 17428
? 17006 17266
? 17267 17428
? 17267 17366
? 17306 17366
? 17330 17366
? 17306 17329
? 17306 17319
? 17320 17329
? 17320 17325
? 17320 17322
? 17320 ...

result:

ok Correct (21 test cases)

Test #12:

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

input:

1
1000000
641602
641602
418256
783270
783270
783270
783270
783270
778242
786055
785504
794273
794682
797591
797591
797004
796734
796559
796850
796850
796850
796850
796844
796864
796864
796864
796864
796863

output:

? 1 1000000
? 381955 1000000
? 381955 763935
? 763936 1000000
? 763936 909834
? 763936 854107
? 763936 819665
? 763936 798378
? 763936 785222
? 785223 798378
? 785223 793353
? 793354 798378
? 793354 796458
? 796459 798378
? 796459 797644
? 796912 797644
? 796459 796911
? 796459 796737
? 796738 79691...

result:

ok Correct (1 test case)

Test #13:

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

input:

16
232936
229707
229707
229707
229707
229707
229707
229707
229707
229707
227478
225790
225790
225790
225790
225611
225474
225483
225375
225395
225407
225409
225417
225419
225425
225426
225423
8676
6498
6498
6498
6498
5867
4978
4978
5022
4731
4731
4717
4684
4684
4676
4692
4692
4690
4693
4693
221085
1...

output:

? 1 232936
? 88972 232936
? 143960 232936
? 177946 232936
? 198950 232936
? 211932 232936
? 219955 232936
? 224914 232936
? 224914 229871
? 226808 229871
? 224914 226807
? 224914 226083
? 225361 226083
? 225361 225806
? 225532 225806
? 225361 225531
? 225427 225531
? 225361 225426
? 225361 225400
? ...

result:

ok Correct (16 test cases)

Test #14:

score: 0
Accepted
time: 35ms
memory: 3584kb

input:

1994
667
666
667
255
254
98
97
38
37
15
14
6
5
3
2
374
373
374
143
142
55
54
22
21
9
8
4
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
4
3
2
639
637
639
245
244
94
93
36
35
14
13
6
5
3
2
353
350
353
135
134
52
51
20
19
8
7
4
3
2
71
66
71
28
27
11
10
5
4
...

output:

? 1 667
? 256 667
? 1 255
? 99 255
? 1 98
? 39 98
? 1 38
? 16 38
? 1 15
? 7 15
? 1 6
? 4 6
? 1 3
? 2 3
! 1
? 1 374
? 144 374
? 1 143
? 56 143
? 1 55
? 23 55
? 1 22
? 10 22
? 1 9
? 5 9
? 1 4
? 3 4
? 1 2
! 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...

result:

ok Correct (1994 test cases)

Test #15:

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

input:

18
153667
153667
153666
58694
58693
22419
22418
8564
8563
3272
3271
1250
1249
478
477
183
182
70
69
27
26
11
10
5
4
2
211376
211374
211376
80736
80735
30838
30837
11779
11778
4500
4499
1719
1718
657
656
251
250
96
95
37
36
15
14
6
5
3
2
195330
195326
195330
74607
74606
28497
28496
10885
10884
4158
4...

output:

? 1 153667
? 58695 153667
? 1 58694
? 22420 58694
? 1 22419
? 8565 22419
? 1 8564
? 3273 8564
? 1 3272
? 1251 3272
? 1 1250
? 479 1250
? 1 478
? 184 478
? 1 183
? 71 183
? 1 70
? 28 70
? 1 27
? 12 27
? 1 11
? 6 11
? 1 5
? 3 5
? 1 2
! 1
? 1 211376
? 80737 211376
? 1 80736
? 30839 80736
? 1 30838
? 11...

result:

ok Correct (18 test cases)

Test #16:

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

input:

1
1000000
999998
1000000
381954
381953
145889
145888
55723
55722
21284
21283
8130
8129
3106
3105
1187
1186
454
453
174
173
67
66
26
25
10
9
4
3
2

output:

? 1 1000000
? 381955 1000000
? 1 381954
? 145890 381954
? 1 145889
? 55724 145889
? 1 55723
? 21285 55723
? 1 21284
? 8131 21284
? 1 8130
? 3107 8130
? 1 3106
? 1188 3106
? 1 1187
? 455 1187
? 1 454
? 175 454
? 1 174
? 68 174
? 1 67
? 27 67
? 1 26
? 11 26
? 1 10
? 5 10
? 1 4
? 3 4
? 1 2
! 1

result:

ok Correct (1 test case)

Test #17:

score: 0
Accepted
time: 43ms
memory: 3584kb

input:

1994
667
666
454
27
27
27
27
27
28
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
4
2
639
639
421
215
147
68
72
2
2
2
2
2
2
353
351
200
91
81
27
27
22
2
2
2
2
71
71
47
6
6
6
6
4
3
2
24
22
24
7
9
2
2
567
563
332
205
1...

output:

? 1 667
? 256 667
? 1 255
? 1 157
? 1 97
? 1 59
? 1 36
? 15 36
? 1 14
? 1 8
? 1 4
? 1 2
! 1
? 1 374
? 144 374
? 1 143
? 56 143
? 1 55
? 1 33
? 14 33
? 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
? 354 92...

result:

ok Correct (1994 test cases)

Test #18:

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

input:

18
153667
153667
65961
50668
47562
8350
8350
8350
5820
1644
1644
1499
306
306
477
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
1568
281
281...

output:

? 1 153667
? 58695 153667
? 1 58694
? 22420 58694
? 1 22419
? 1 13855
? 1 8563
? 3272 8563
? 1 3271
? 1 2021
? 773 2021
? 1 772
? 1 477
? 184 477
? 1 183
? 1 113
? 1 69
? 1 42
? 1 25
? 11 25
? 1 10
? 5 10
? 1 4
? 3 4
? 1 2
! 1
? 1 211376
? 80737 211376
? 1 80736
? 30839 80736
? 1 30838
? 1 19059
? 1...

result:

ok Correct (18 test cases)

Test #19:

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

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
6
2
2

output:

? 1 1000000
? 381955 1000000
? 1 381954
? 1 236065
? 90167 236065
? 1 90166
? 1 55726
? 1 34441
? 1 21286
? 1 13155
? 1 8130
? 3107 8130
? 1 3106
? 1 1919
? 734 1919
? 1 733
? 1 453
? 1 279
? 1 172
? 1 106
? 1 65
? 26 65
? 1 25
? 11 25
? 1 10
? 1 6
? 4 6
? 1 3
? 1 2
! 1

result:

ok Correct (1 test case)

Test #20:

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

input:

1
999999
260772
507886
955966
996647
730076
730076
751781
706326
706326
706326
706326
705072
701051
701051
700204
701978
701702
701488
701453
701361
701361
701361
701361
701361
701361
701359
701355
701356
701358

output:

? 1 999999
? 1 618046
? 618047 999999
? 763936 999999
? 618047 763935
? 673770 763935
? 708210 763935
? 673770 708209
? 686925 708209
? 695055 708209
? 700080 708209
? 703186 708209
? 700080 703185
? 700080 701998
? 700080 701265
? 701266 701998
? 701546 701998
? 701266 701545
? 701373 701545
? 7012...

result:

ok Correct (1 test case)

Test #21:

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

input:

1
999998
295598
295598
73514
537464
537464
537464
537464
537464
537464
537464
537464
537464
537464
537464
536777
536636
536350
536275
536275
536275
536271
536208
536208
536208
536209
536197
536197
536198

output:

? 1 999998
? 1 618045
? 1 381980
? 381981 618045
? 472147 618045
? 472147 562318
? 506589 562318
? 506589 541031
? 519745 541031
? 527876 541031
? 532901 541031
? 532901 537925
? 534821 537925
? 536007 537925
? 536740 537925
? 536007 536739
? 536287 536739
? 536007 536286
? 536114 536286
? 536181 53...

result:

ok Correct (1 test case)

Test #22:

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

input:

1
999997
339297
339297
355318
613666
489939
413343
417456
471212
471212
468570
453304
453304
453304
453304
453304
453304
453467
452873
452842
453059
453059
453052
453017
453017
453013
453005
453005
453006
453007

output:

? 1 999997
? 1 618045
? 1 381980
? 381981 618045
? 472147 618045
? 381981 472146
? 381981 437706
? 437707 472146
? 450862 472146
? 458992 472146
? 450862 458991
? 450862 455885
? 450862 453966
? 452048 453966
? 452781 453966
? 452781 453513
? 453061 453513
? 452781 453060
? 452781 452953
? 452954 45...

result:

ok Correct (1 test case)

Test #23:

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

input:

1
999996
578161
472988
665875
726172
958644
966123
888583
907890
865390
865390
865390
864247
859775
859775
859775
859775
859584
859300
859300
859300
859303
859239
859239
859239
859239
859237
859235
859235

output:

? 1 999996
? 1 618044
? 618045 999996
? 618045 854108
? 854109 999996
? 909832 999996
? 854109 909831
? 875393 909831
? 854109 875392
? 854109 867262
? 859134 867262
? 862239 867262
? 859134 862238
? 859134 861052
? 859134 860319
? 859134 859866
? 859414 859866
? 859134 859413
? 859134 859306
? 8592...

result:

ok Correct (1 test case)

Test #24:

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

input:

2
500000
114103
114103
98381
290103
281943
220637
220637
222630
226042
226042
226042
226042
226042
226074
226572
226450
226893
226893
226821
226805
226799
226759
226760
226770
226769
226776
226776
500000
313297
313297
313297
285097
246160
246160
246160
238712
228136
228136
229362
223239
223495
22511...

output:

? 1 500000
? 1 309023
? 1 190990
? 190991 309023
? 236075 309023
? 190991 236074
? 208211 236074
? 208211 225431
? 225432 236074
? 225432 232008
? 225432 229495
? 225432 227942
? 225432 226982
? 225432 226389
? 226390 226982
? 226390 226755
? 226756 226982
? 226756 226895
? 226810 226895
? 226756 22...

result:

ok Correct (2 test cases)

Test #25:

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

input:

2
499999
493493
493493
493493
493493
493493
493493
487773
471068
471068
471068
471825
466355
465991
467320
467320
467320
467236
467382
467382
467382
467361
467345
467345
467345
467344
467342
467341
499999
101651
101651
101651
101651
98374
24247
24247
18123
9237
9237
8975
6574
6338
4671
4669
4261
426...

output:

? 1 499999
? 190978 499999
? 309010 499999
? 381960 499999
? 427046 499999
? 454912 499999
? 472134 499999
? 454912 472133
? 461490 472133
? 465556 472133
? 468069 472133
? 465556 468068
? 465556 467108
? 467109 468068
? 467109 467701
? 467109 467474
? 467109 467334
? 467335 467474
? 467335 467420
?...

result:

ok Correct (2 test cases)

Test #26:

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

input:

2
499998
367462
193038
152483
183238
53076
53076
53076
53076
49244
42856
42864
39670
39405
40342
40342
40342
40342
40342
40342
40331
40310
40299
40296
40296
40294
40293
40293
499998
122343
122343
3768
201785
201785
209196
246144
244788
259205
259205
258709
254417
254417
254748
253733
253610
253302
2...

output:

? 1 499998
? 190977 499998
? 1 190976
? 72945 190976
? 1 72944
? 27863 72944
? 27863 55724
? 38505 55724
? 45083 55724
? 38505 45082
? 41018 45082
? 38505 41017
? 38505 40057
? 40058 41017
? 40058 40650
? 40058 40423
? 40198 40423
? 40285 40423
? 40285 40369
? 40318 40369
? 40285 40317
? 40298 40317...

result:

ok Correct (2 test cases)

Test #27:

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

input:

2
499997
274071
274071
274071
302688
167121
159831
135636
135636
135636
135636
135636
136187
133612
133612
133655
133080
132896
132781
132781
132781
132768
132743
132743
132743
132745
132746
132746
499997
242708
242708
242708
248273
160791
143467
177106
177106
172524
164685
164685
164685
164155
1635...

output:

? 1 499997
? 1 309021
? 118033 309021
? 190982 309021
? 118033 190981
? 145897 190981
? 118033 145896
? 128676 145896
? 128676 139318
? 132742 139318
? 132742 136805
? 134295 136805
? 132742 134294
? 132742 133700
? 133109 133700
? 132742 133108
? 132883 133108
? 132742 132882
? 132742 132828
? 1327...

result:

ok Correct (2 test cases)

Test #28:

score: 0
Accepted
time: 102ms
memory: 3584kb

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: 128ms
memory: 3584kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #30:

score: 0
Accepted
time: 84ms
memory: 3584kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #31:

score: 0
Accepted
time: 73ms
memory: 3584kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #32:

score: 0
Accepted
time: 65ms
memory: 3584kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #33:

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

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: 78ms
memory: 3584kb

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: 73ms
memory: 3456kb

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: 77ms
memory: 3584kb

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: 65ms
memory: 3584kb

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: 72ms
memory: 3584kb

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: 78ms
memory: 3456kb

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: 78ms
memory: 3456kb

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: 71ms
memory: 3584kb

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: 77ms
memory: 3584kb

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: 81ms
memory: 3584kb

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: 72ms
memory: 3584kb

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: 80ms
memory: 3584kb

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: 71ms
memory: 3584kb

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

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 18:06:40 | OpenSource Project