QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#801658#8939. PermutationNoobie_99#AC ✓192ms3756kbC++201.3kb2024-12-07 04:53:352024-12-07 04:53:35

Judging History

This is the latest submission verdict.

  • [2024-12-07 04:53:35]
  • Judged
  • Verdict: AC
  • Time: 192ms
  • Memory: 3756kb
Show
  • [2024-12-07 04:53:35]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) ::begin(x), ::end(x)
void _d(auto... x) { ((cerr << ' ' << x), ...) << endl; }
#define debug(x...) cerr << "["#x"]:", _d(x)

int query(int l, int r) {
    if (l+1 == r) return l;
    cout << "? " << l+1 << ' ' << r << endl;
    cin >> l;
    return l-1;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    long double phi = 1 - 0.61803;

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;

        int sec = query(0, n);
        int l = 0, r = n;
        while (l+2 < r) {
            int m = l + round((r-l) * phi);

            if (sec >= m) {
                int x = query(m, r);
                if (x == sec) {
                    l = m;
                } else {
                    r = m;
                    sec = query(l, r);
                }
            } else {
                m = r - round((r-l) * phi);
                int x = query(l, m);
                if (x == sec) {
                    r = m;
                } else {
                    l = m;
                    sec = query(l, r);
                }
            }
        }

        if (l+1 != r) sec = sec == l ? l+1 : l;
        cout << "! " << sec+1 << endl;
    }
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3732kb

input:

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

output:

? 1 5
? 3 5
? 3 4
! 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: 61ms
memory: 3608kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #3:

score: 0
Accepted
time: 80ms
memory: 3684kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #4:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #5:

score: 0
Accepted
time: 108ms
memory: 3656kb

input:

10000
100
47
47
47
61
71
71
75
68
69
9
2
2
2
1
4
53
46
35
6
6
8
2
1
4
33
3
16
31
31
31
31
32
82
60
41
29
29
29
29
28
26
27
88
39
39
39
51
59
59
59
59
60
71
24
29
59
59
59
59
59
60
61
92
52
52
45
88
88
88
88
88
87
89
24
11
20
9
9
8
5
66
51
51
45
29
28
39
39
38
40
92
43
50
20
20
20
25
17
17
17
48
1
1
...

output:

? 1 100
? 39 100
? 39 76
? 39 61
? 62 76
? 68 76
? 71 76
? 68 70
? 68 69
! 70
? 1 9
? 1 6
? 1 4
? 1 2
? 3 4
! 3
? 1 53
? 21 53
? 1 20
? 1 12
? 6 12
? 1 5
? 1 3
? 4 5
! 5
? 1 33
? 1 20
? 21 33
? 26 33
? 29 33
? 31 33
? 31 32
! 33
? 1 82
? 32 82
? 1 31
? 13 31
? 20 31
? 25 31
? 28 31
? 25 27
? 26 27
!...

result:

ok Correct (10000 test cases)

Test #6:

score: 0
Accepted
time: 192ms
memory: 3660kb

input:

10000
50
10
10
10
14
2
2
1
3
50
11
11
9
31
26
23
23
23
50
44
44
40
20
20
21
26
25
50
24
24
29
45
45
45
44
46
50
50
50
50
50
50
49
44
45
50
36
23
17
17
18
12
11
8
50
29
20
13
19
3
3
3
50
30
42
16
11
1
1
2
4
50
25
25
25
25
25
25
26
27
50
18
20
49
47
37
37
37
50
9
9
9
9
9
11
14
13
50
26
43
17
17
17
19
...

output:

? 1 50
? 1 31
? 1 19
? 8 19
? 1 7
? 1 4
? 1 2
? 3 4
! 4
? 1 50
? 1 31
? 1 19
? 20 31
? 25 31
? 20 24
? 22 24
? 23 24
! 24
? 1 50
? 20 50
? 32 50
? 20 31
? 20 26
? 20 23
? 24 26
? 25 26
! 24
? 1 50
? 20 50
? 20 38
? 39 50
? 44 50
? 44 47
? 44 45
? 46 47
! 47
? 1 50
? 20 50
? 32 50
? 39 50
? 44 50
? 4...

result:

ok Correct (10000 test cases)

Test #7:

score: 0
Accepted
time: 112ms
memory: 3672kb

input:

10000
100
76
49
35
34
5
3
11
11
11
100
29
29
29
29
29
29
30
26
27
100
64
64
64
64
69
78
78
77
81
100
51
51
57
98
92
79
79
79
80
81
100
44
75
13
13
12
1
4
9
9
100
64
92
22
22
19
33
33
35
37
100
93
93
86
56
59
40
44
45
45
100
37
2
97
81
76
76
77
70
71
100
76
76
76
76
76
74
85
85
85
100
32
32
32
32
31
...

output:

? 1 100
? 39 100
? 1 38
? 16 38
? 1 15
? 1 9
? 10 15
? 10 13
? 10 11
! 10
? 1 100
? 1 62
? 25 62
? 25 47
? 25 38
? 25 33
? 28 33
? 25 27
? 26 27
! 25
? 1 100
? 39 100
? 63 100
? 63 85
? 63 76
? 77 85
? 77 82
? 77 80
? 81 82
! 82
? 1 100
? 39 100
? 39 76
? 77 100
? 86 100
? 77 85
? 77 82
? 79 82
? 79...

result:

ok Correct (10000 test cases)

Test #8:

score: 0
Accepted
time: 20ms
memory: 3668kb

input:

1000
1000
475
475
728
896
867
831
831
831
841
844
844
844
844
845
1000
278
17
974
811
757
751
637
637
637
637
637
639
645
645
1000
75
128
871
985
644
686
713
713
712
732
735
742
741
739
1000
239
239
239
239
350
432
432
442
458
458
458
459
462
463
1000
978
978
978
978
978
978
997
914
914
920
927
929
...

output:

? 1 1000
? 383 1000
? 383 764
? 765 1000
? 855 1000
? 765 854
? 799 854
? 820 854
? 820 841
? 842 854
? 842 849
? 842 846
? 844 846
? 844 845
! 846
? 1 1000
? 1 618
? 619 1000
? 765 1000
? 619 764
? 675 764
? 619 674
? 619 653
? 632 653
? 632 645
? 637 645
? 637 642
? 643 645
? 644 645
! 644
? 1 100...

result:

ok Correct (1000 test cases)

Test #9:

score: 0
Accepted
time: 25ms
memory: 3684kb

input:

1017
272
246
111
27
52
73
73
73
73
73
73
73
114
105
91
2
2
2
2
2
2
2
910
173
173
173
148
14
14
14
29
35
37
51
51
50
48
726
229
229
438
118
149
63
28
17
17
17
21
24
24
861
315
104
671
688
632
632
652
593
593
593
593
593
592
594
1984
133
133
133
406
571
512
724
704
688
673
650
650
650
652
649
1145
988...

output:

? 1 272
? 105 272
? 1 104
? 1 64
? 65 104
? 65 89
? 65 79
? 71 79
? 71 76
? 73 76
? 73 74
! 74
? 1 114
? 45 114
? 1 44
? 1 27
? 1 17
? 1 11
? 1 7
? 1 4
? 1 2
! 1
? 1 910
? 1 562
? 1 347
? 134 347
? 1 133
? 1 82
? 1 51
? 1 32
? 33 51
? 33 44
? 45 51
? 48 51
? 50 51
? 48 49
! 49
? 1 726
? 1 449
? 173 ...

result:

ok Correct (1017 test cases)

Test #10:

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

input:

10
100000
3893
3893
30673
43582
43582
43582
43582
43582
43582
43582
43470
43242
43242
43242
43242
43242
43245
43289
43279
43268
43268
43268
43269
43270
100000
32066
54928
68197
71764
88585
88585
85554
93282
94213
91599
92129
91474
91474
91474
91446
91305
91325
91348
91348
91348
91348
91349
91351
913...

output:

? 1 100000
? 1 61803
? 1 38196
? 38197 61803
? 38197 52786
? 38197 47213
? 41641 47213
? 41641 45084
? 42957 45084
? 42957 44271
? 43459 44271
? 42957 43458
? 43149 43458
? 43149 43340
? 43222 43340
? 43222 43295
? 43222 43267
? 43268 43295
? 43279 43295
? 43268 43278
? 43268 43274
? 43268 43271
? 4...

result:

ok Correct (10 test cases)

Test #11:

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

input:

21
84335
47947
60969
22445
22445
20931
19830
19830
19830
19815
17079
17079
17079
17084
17352
17346
17316
17316
17316
17316
17316
17320
17323
17323
159962
128177
145530
35270
35270
35270
35270
34180
42103
42103
43214
43550
43550
43550
43550
43489
43765
43753
43675
43675
43670
43695
43695
43695
43696
...

output:

? 1 84335
? 32214 84335
? 1 32213
? 12305 32213
? 19910 32213
? 12305 19909
? 15210 19909
? 17005 19909
? 18115 19909
? 17005 18114
? 17005 17690
? 17005 17428
? 17005 17266
? 17267 17428
? 17329 17428
? 17267 17328
? 17291 17328
? 17306 17328
? 17315 17328
? 17315 17323
? 17315 17320
? 17321 17323
...

result:

ok Correct (21 test cases)

Test #12:

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

input:

1
1000000
641602
641602
641602
641602
732855
783270
783270
783270
783270
786055
794273
794273
794682
797591
798201
797004
797004
796975
796850
796850
796850
796850
796850
796844
796864
796864
796866
796863

output:

? 1 1000000
? 381971 1000000
? 618040 1000000
? 618040 854102
? 618040 763933
? 763934 854102
? 763934 819660
? 763934 798374
? 777089 798374
? 777089 790243
? 790244 798374
? 793350 798374
? 793350 796455
? 796456 798374
? 797189 798374
? 796456 797188
? 796736 797188
? 796909 797188
? 796736 79690...

result:

ok Correct (1 test case)

Test #13:

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

input:

16
232936
229707
229707
229707
229707
229707
229707
229707
229707
231039
227478
227474
225790
225790
225915
225474
225611
225375
225375
225395
225407
225409
225417
225419
225425
225426
225423
8676
6498
6498
7154
4978
4978
4978
5243
4731
4717
4684
4684
4684
4684
4684
4684
4690
4692
4691
4693
221085
1...

output:

? 1 232936
? 88976 232936
? 143965 232936
? 177950 232936
? 198953 232936
? 211934 232936
? 219957 232936
? 224915 232936
? 227979 232936
? 224915 227978
? 226085 227978
? 224915 226084
? 225362 226084
? 225638 226084
? 225362 225637
? 225467 225637
? 225362 225466
? 225362 225426
? 225362 225401
? ...

result:

ok Correct (16 test cases)

Test #14:

score: 0
Accepted
time: 39ms
memory: 3672kb

input:

1994
667
666
667
255
254
97
96
37
36
14
13
5
4
2
374
373
374
143
142
55
54
21
20
8
7
3
2
488
486
488
186
185
71
70
27
26
10
9
4
3
2
922
921
922
352
351
134
133
51
50
19
18
7
6
3
2
639
637
639
244
243
93
92
36
35
14
13
5
4
2
353
350
353
135
134
52
51
20
19
8
7
3
2
71
66
71
27
26
10
9
4
3
2
24
21
24
9...

output:

? 1 667
? 256 667
? 1 255
? 98 255
? 1 97
? 38 97
? 1 37
? 15 37
? 1 14
? 6 14
? 1 5
? 3 5
? 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
? 187 488
? 1 186
? 72 186
? 1 71
? 28 71
? 1 27
? 11 27
? 1 10
? 5 10
? 1 4
? 3 4
? 1 2
! 1
? 1 92...

result:

ok Correct (1994 test cases)

Test #15:

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

input:

18
153667
153667
153666
58696
58695
22420
22419
8564
8563
3271
3270
1249
1248
477
476
182
181
70
69
27
26
10
9
4
3
2
211376
211374
211376
80739
80738
30840
30839
11780
11779
4500
4499
1719
1718
657
656
251
250
96
95
37
36
14
13
5
4
2
195330
195326
195330
74610
74609
28499
28498
10886
10885
4158
4157...

output:

? 1 153667
? 58697 153667
? 1 58696
? 22421 58696
? 1 22420
? 8565 22420
? 1 8564
? 3272 8564
? 1 3271
? 1250 3271
? 1 1249
? 478 1249
? 1 477
? 183 477
? 1 182
? 71 182
? 1 70
? 28 70
? 1 27
? 11 27
? 1 10
? 5 10
? 1 4
? 3 4
? 1 2
! 1
? 1 211376
? 80740 211376
? 1 80739
? 30841 80739
? 1 30840
? 11...

result:

ok Correct (18 test cases)

Test #16:

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

input:

1
1000000
999998
1000000
381970
381969
145901
145900
55730
55729
21287
21286
8131
8130
3106
3105
1186
1185
453
452
173
172
66
65
25
24
10
9
4
3
2

output:

? 1 1000000
? 381971 1000000
? 1 381970
? 145902 381970
? 1 145901
? 55731 145901
? 1 55730
? 21288 55730
? 1 21287
? 8132 21287
? 1 8131
? 3107 8131
? 1 3106
? 1187 3106
? 1 1186
? 454 1186
? 1 453
? 174 453
? 1 173
? 67 173
? 1 66
? 26 66
? 1 25
? 11 25
? 1 10
? 5 10
? 1 4
? 3 4
? 1 2
! 1

result:

ok Correct (1 test case)

Test #17:

score: 0
Accepted
time: 30ms
memory: 3608kb

input:

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

output:

? 1 667
? 256 667
? 1 255
? 1 158
? 1 98
? 1 61
? 24 61
? 1 23
? 1 14
? 1 9
? 1 6
? 1 4
? 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
? 187 488
? 1 186
? 72 186
? 1 71
? 28 71
? 1 27
? 11 27
? 1 10
? 5 10
? 1 4
? 3 4
? 1 2
! 1
? 1 922
?...

result:

ok Correct (1994 test cases)

Test #18:

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

input:

18
153667
153667
65961
50668
47562
8350
8350
5820
1644
1644
3091
306
306
551
24
24
24
24
24
38
16
12
3
5
2
211376
211375
91641
67652
36438
4235
4235
4235
4235
3075
973
973
961
436
539
221
163
79
60
10
10
16
2
2
2
2
195330
195325
161600
36944
56808
17928
26132
1018
1018
1018
1018
1745
281
281
351
215...

output:

? 1 153667
? 58697 153667
? 1 58696
? 22421 58696
? 1 22420
? 1 13856
? 5294 13856
? 1 5293
? 1 3271
? 1250 3271
? 1 1249
? 1 772
? 296 772
? 1 295
? 1 182
? 1 112
? 1 69
? 1 43
? 17 43
? 1 16
? 7 16
? 1 6
? 3 6
? 1 2
! 1
? 1 211376
? 80740 211376
? 1 80739
? 30841 80739
? 1 30840
? 1 19060
? 1 1178...

result:

ok Correct (18 test cases)

Test #19:

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

input:

1
1000000
999998
783271
169408
303809
8002
8002
8002
8002
8002
8002
6079
1522
1522
2567
42
42
42
42
42
42
100
18
26
13
15
4
6
2

output:

? 1 1000000
? 381971 1000000
? 1 381970
? 145902 381970
? 1 145901
? 1 90171
? 1 55728
? 1 34442
? 1 21286
? 1 13155
? 5026 13155
? 1 5025
? 1 3106
? 1187 3106
? 1 1186
? 1 733
? 1 453
? 1 280
? 1 173
? 1 107
? 42 107
? 1 41
? 17 41
? 1 16
? 7 16
? 1 6
? 3 6
? 1 2
! 1

result:

ok Correct (1 test case)

Test #20:

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

input:

1
999999
260772
507886
955966
996647
730076
730076
751781
706326
706326
706326
706326
705072
701051
701051
701051
701051
701101
701488
701453
701361
701361
701361
701361
701361
701361
701363
701359
701358

output:

? 1 999999
? 1 618029
? 618030 999999
? 763931 999999
? 618030 763930
? 673760 763930
? 708203 763930
? 673760 708202
? 686916 708202
? 695047 708202
? 700072 708202
? 703178 708202
? 700072 703177
? 700072 701991
? 700805 701991
? 700805 701538
? 700805 701258
? 701259 701538
? 701366 701538
? 7012...

result:

ok Correct (1 test case)

Test #21:

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

input:

1
999998
295598
295598
295598
393831
537464
537464
537464
537464
537464
537464
537464
537464
537464
538126
536777
537160
536275
536275
536350
536271
536262
536170
536177
536204
536204
536205
536197
536196
536198

output:

? 1 999998
? 1 618029
? 236070 618029
? 236070 472132
? 472133 618029
? 527861 618029
? 527861 583587
? 527861 562301
? 527861 549146
? 535992 549146
? 535992 544121
? 535992 541016
? 535992 539097
? 537178 539097
? 535992 537177
? 536445 537177
? 535992 536444
? 536165 536444
? 536272 536444
? 5361...

result:

ok Correct (1 test case)

Test #22:

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

input:

1
999997
339297
339297
339297
339297
339297
355318
471212
471212
471212
468570
453304
453304
453304
453304
453304
453467
452873
452873
452873
452945
453017
453017
453017
453019
453013
453013
453010
453009

output:

? 1 999997
? 1 618028
? 236069 618028
? 236069 472131
? 326238 472131
? 326238 416404
? 416405 472131
? 437691 472131
? 450846 472131
? 458977 472131
? 450846 458976
? 450846 455870
? 452765 455870
? 452765 454684
? 452765 453951
? 453218 453951
? 452765 453217
? 452765 453044
? 452872 453044
? 4528...

result:

ok Correct (1 test case)

Test #23:

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

input:

1
999996
578161
578161
472988
785834
785834
797735
888583
907890
865390
864247
859775
859775
859775
859775
859775
859913
859300
859303
859239
859239
859239
859239
859239
859239
859239
859240
859237
859238

output:

? 1 999996
? 381969 999996
? 381969 763928
? 763929 999996
? 763929 909825
? 763929 854097
? 854098 909825
? 875384 909825
? 854098 875383
? 862229 875383
? 854098 862228
? 857204 862228
? 859123 862228
? 859123 861042
? 859123 860309
? 859576 860309
? 859123 859575
? 859296 859575
? 859123 859295
?...

result:

ok Correct (1 test case)

Test #24:

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

input:

2
500000
114103
114103
98381
290103
281943
220637
220637
220637
220637
222630
226042
226042
226042
226042
226572
226893
226893
226930
226805
226821
226759
226760
226770
226770
226772
226777
226776
500000
313297
313297
436237
246160
285097
217669
217669
217669
217669
217434
222822
223239
223884
22472...

output:

? 1 500000
? 1 309015
? 1 190981
? 190982 309015
? 236067 309015
? 190982 236066
? 208203 236066
? 218846 236066
? 218846 229488
? 218846 225423
? 225424 229488
? 225424 227935
? 225424 226975
? 226017 226975
? 226017 226609
? 226610 226975
? 226750 226975
? 226836 226975
? 226750 226835
? 226783 22...

result:

ok Correct (2 test cases)

Test #25:

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

input:

2
499999
493493
493493
493493
493493
493493
493493
487773
471068
471068
471068
471825
466355
465991
467320
467320
467320
467320
467320
467320
467320
467329
467345
467345
467344
467338
467338
467339
499999
101651
101651
101651
159545
24247
24247
18123
9237
8975
3528
3528
3528
3528
3528
3755
4261
4261...

output:

? 1 499999
? 190986 499999
? 309020 499999
? 381969 499999
? 427053 499999
? 454917 499999
? 472137 499999
? 454917 472136
? 461495 472136
? 465560 472136
? 468072 472136
? 465560 468071
? 465560 467111
? 467112 468071
? 467112 467704
? 467112 467477
? 467252 467477
? 467252 467391
? 467305 467391
?...

result:

ok Correct (2 test cases)

Test #26:

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

input:

2
499998
367462
193038
152483
183238
53076
53076
60946
29299
37492
42856
42864
39670
39670
39670
39518
40342
40342
40342
40374
40331
40310
40296
40296
40299
40293
40293
40293
499998
122343
122343
122343
201785
246144
246144
246144
244788
259205
263005
254417
254417
255518
253733
254075
253610
253610...

output:

? 1 499998
? 190985 499998
? 1 190984
? 72951 190984
? 1 72950
? 27866 72950
? 45087 72950
? 27866 45086
? 27866 38508
? 38509 45086
? 41022 45086
? 38509 41021
? 39469 41021
? 39469 40428
? 39469 40061
? 40062 40428
? 40202 40428
? 40289 40428
? 40342 40428
? 40289 40341
? 40309 40341
? 40289 40308...

result:

ok Correct (2 test cases)

Test #27:

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

input:

2
499997
274071
318426
94336
94336
94336
90770
135636
135636
137448
130923
129808
133612
133612
133655
133080
133116
132781
132781
132781
132811
132768
132770
132750
132752
132746
132746
132746
499997
242708
310592
44473
60177
160791
160791
160791
160791
160791
160791
160791
163029
163524
163524
164...

output:

? 1 499997
? 190985 499997
? 1 190984
? 72951 190984
? 72951 145899
? 72951 118035
? 118036 145899
? 128679 145899
? 135257 145899
? 128679 135256
? 128679 132743
? 132744 135256
? 132744 134296
? 133337 134296
? 132744 133336
? 132971 133336
? 132744 132970
? 132744 132883
? 132744 132830
? 132777 ...

result:

ok Correct (2 test cases)

Test #28:

score: 0
Accepted
time: 34ms
memory: 3612kb

input:

10000
2
1
2
2
3
2
2
3
3
3
3
1
2
3
1
1
3
3
2
3
2
3
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
4
5
5
5
5
5
3
3
4
5
3
3
3
5
5
5
4
5
4
4
5
5
4
4
4
5
5
5
5
5
3
3
4
5
...

output:

? 1 2
! 2
? 1 2
! 1
? 1 3
? 2 3
! 3
? 1 3
? 2 3
! 2
? 1 3
? 1 2
! 3
? 1 3
? 1 2
! 2
? 1 3
? 2 3
! 1
? 1 3
? 2 3
! 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: 30ms
memory: 3692kb

input:

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

result:

ok Correct (10000 test cases)

Test #30:

score: 0
Accepted
time: 70ms
memory: 3676kb

input:

10000
8
2
3
7
7
8
2
3
8
8
8
2
3
6
7
8
2
3
6
6
8
2
3
8
7
8
2
3
7
8
8
2
3
7
7
8
2
3
8
8
8
2
3
6
7
8
2
3
6
6
8
2
3
8
7
8
2
3
7
8
8
2
5
7
7
8
2
5
8
8
8
2
5
6
7
8
2
5
6
6
8
2
5
8
7
8
2
5
7
8
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
7
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
? 7 8
! 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
? 7 8
! 6
? 1 8
? 1 5
? 6 8
? 7 8
! 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: 54ms
memory: 3656kb

input:

10000
8
2
4
8
7
8
2
4
7
8
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
? 7 8
! 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: 67ms
memory: 3696kb

input:

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

result:

ok Correct (10000 test cases)

Test #33:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #34:

score: 0
Accepted
time: 82ms
memory: 3668kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #35:

score: 0
Accepted
time: 82ms
memory: 3660kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #36:

score: 0
Accepted
time: 22ms
memory: 3608kb

input:

10000
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
...

output:

? 1 9
? 1 6
? 1 4
? 1 2
? 3 4
! 4
? 1 9
? 1 6
? 1 4
? 1 2
? 3 4
! 4
? 1 9
? 1 6
? 1 4
? 1 2
? 3 4
! 4
? 1 9
? 1 6
? 1 4
? 1 2
? 3 4
! 4
? 1 9
? 1 6
? 1 4
? 1 2
? 3 4
! 4
? 1 9
? 1 6
? 1 4
? 1 2
? 3 4
! 4
? 1 9
? 1 6
? 1 4
? 1 2
? 3 4
! 4
? 1 9
? 1 6
? 1 4
? 1 2
? 3 4
! 4
? 1 9
? 1 6
? 1 4
? 1 2
? 3 ...

result:

ok Correct (10000 test cases)

Test #37:

score: 0
Accepted
time: 81ms
memory: 3728kb

input:

10000
9
4
4
4
5
6
9
4
4
4
5
6
9
4
4
4
5
7
9
4
4
4
5
7
9
4
4
4
5
7
9
4
4
4
5
7
9
4
4
4
5
7
9
4
4
4
5
7
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
...

output:

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

result:

ok Correct (10000 test cases)

Test #38:

score: 0
Accepted
time: 52ms
memory: 3644kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #39:

score: 0
Accepted
time: 52ms
memory: 3672kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #40:

score: 0
Accepted
time: 52ms
memory: 3604kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #41:

score: 0
Accepted
time: 77ms
memory: 3672kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #42:

score: 0
Accepted
time: 23ms
memory: 3696kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #43:

score: 0
Accepted
time: 23ms
memory: 3540kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #44:

score: 0
Accepted
time: 75ms
memory: 3660kb

input:

10000
9
2
3
7
8
9
2
3
7
7
9
2
3
9
8
9
2
3
8
9
9
2
6
8
8
9
2
6
9
9
9
2
6
7
8
9
2
6
7
7
9
2
6
9
8
9
2
6
8
9
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
3
8
8
9
2
3
9
9
9
2
3
7
8
9
2
3
7
7
9
2
3
9
8
9
2
3
8
9
9
2
3
8
8
9
2
3
9
9
9
2
3
7
8
9
2
3
7
7
9
2
3
9
8
9
2
3
8
9
9
2
6
8
8
9
2
...

output:

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

result:

ok Correct (10000 test cases)

Test #45:

score: 0
Accepted
time: 90ms
memory: 3544kb

input:

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

output:

? 1 9
? 4 9
? 6 9
? 4 5
! 4
? 1 9
? 4 9
? 6 9
? 4 5
! 4
? 1 9
? 4 9
? 6 9
? 4 5
! 4
? 1 9
? 4 9
? 6 9
? 4 5
! 4
? 1 9
? 4 9
? 6 9
? 4 5
! 4
? 1 9
? 4 9
? 6 9
? 4 5
! 4
? 1 9
? 4 9
? 6 9
? 4 5
! 4
? 1 9
? 4 9
? 6 9
? 4 5
! 4
? 1 9
? 4 9
? 6 9
? 4 5
! 4
? 1 9
? 4 9
? 6 9
? 4 5
! 4
? 1 9
? 4 9
? 6 9
? ...

result:

ok Correct (10000 test cases)

Test #46:

score: 0
Accepted
time: 52ms
memory: 3664kb

input:

10000
9
4
4
4
5
6
9
4
4
4
5
6
9
4
4
4
5
7
9
4
4
4
5
7
9
4
4
4
5
7
9
4
4
4
5
7
9
4
4
4
5
7
9
4
4
4
5
7
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
...

output:

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

result:

ok Correct (10000 test cases)

Test #47:

score: 0
Accepted
time: 50ms
memory: 3660kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Extra Test:

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

Server Time: 2025-02-08 17:55:35 | OpenSource Project