QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#540241#8939. Permutationucup-team112#AC ✓641ms11200kbPython31.2kb2024-08-31 16:42:512024-08-31 16:42:52

Judging History

This is the latest submission verdict.

  • [2024-08-31 16:42:52]
  • Judged
  • Verdict: AC
  • Time: 641ms
  • Memory: 11200kb
Show
  • [2024-08-31 16:42:51]
  • Submitted

answer


"""

"""

import math
import random
gold = 1.6180339887

def query(l,r):
    print ("?",l,r,flush=True)
    cat = int(input())
    return cat

TT = int(input())

for loop in range(TT):

    n = int(input())

    l = 1
    r = n
    x = None

    while r-l+1 >= 3:

        if x == None:
            x = query(l,r)
            continue
        else:
            m1 = (l*gold + r*1) / (gold+1)
            m2 = (l*1 + r*gold) / (gold+1)

            if x <= m1 or (x <= m2 and random.randint(0,100) <= 50):
                m2_floor = math.floor(m2)
                cat = query(l,m2_floor)
                if cat == x:
                    r = m2_floor
                else:
                    l = m2_floor + 1
                    x = None
            else:
                m1_ceil = math.ceil(m1)
                cat = query(m1_ceil , r)
                if cat == x:
                    l = m1_ceil
                else:
                    r = m1_ceil - 1
                    x = None
    
    lr_len = r-l+1
    if lr_len == 1:
        print ("!",l,flush=True)
    else:
        if x == None:
            x = query(l,r)
        print ("!" , l+r-x , flush=True)

"""

1 3 4 2 5
1 4 6 2 3 5

"""
Source code, Language: Python3

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 19ms
memory: 11016kb

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: 334ms
memory: 11196kb

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
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
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
? 3 6
? 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: 291ms
memory: 11080kb

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
11
11
10
14
1
1
1
3
5
16
4
4
4
4
3
5
3
3
2
19
13
17
5
6
2
1
2
2
4
1
2
3
7
2
2
2
3
2
2
17
1
1
1
2
6
14
9
9
9
9
9
20
9
9
9
9
10
11
6
4
2
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
4
6...

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

result:

ok Correct (10000 test cases)

Test #4:

score: 0
Accepted
time: 426ms
memory: 11136kb

input:

10000
47
23
31
11
9
2
2
1
3
14
8
8
8
8
9
25
6
6
4
13
13
12
15
7
4
4
4
9
2
2
2
3
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
22
17
47
21
21
21
19
15
15
16
17
41
25
25
30
33
33
34
36
19
17
17
16
9
10
12
21
14
14
14
14
14
13
...

output:

? 1 47
? 19 47
? 1 18
? 8 18
? 1 7
? 1 4
? 1 2
? 3 4
! 4
? 1 14
? 6 14
? 6 10
? 8 10
? 8 9
! 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 5
? 1 3
? 2 3
! 1
? 1 27
? 11 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: 568ms
memory: 11100kb

input:

10000
100
47
61
93
96
71
71
71
71
71
9
2
2
2
1
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
8
59
59
59
59
59
59
60
71
24
29
59
59
59
60
64
63
61
92
52
45
88
88
88
88
85
91
92
24
11
11
9
5
5
6
3
66
51
51
45
29
28
39
39
38
40
92
43
50
20
20
20
20
20
21
19
48
1
1
1
1
...

output:

? 1 100
? 1 62
? 63 100
? 78 100
? 63 77
? 63 71
? 67 71
? 69 71
? 70 71
! 70
? 1 9
? 1 5
? 1 3
? 1 2
! 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
! 25
? ...

result:

ok Correct (10000 test cases)

Test #6:

score: 0
Accepted
time: 512ms
memory: 11044kb

input:

10000
50
10
10
10
10
6
2
3
5
50
11
11
9
31
26
23
23
23
50
44
44
40
20
20
21
26
25
50
24
24
29
45
40
49
48
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
26
26
28
17
19
...

output:

? 1 50
? 1 31
? 1 19
? 1 12
? 6 12
? 1 5
? 1 3
? 4 5
! 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
? 39 45
? 46 50
? 48 50
? 46 47
! 47
? 1 50
? 20 50
? 32 50
? 39 50
? 44 50
? ...

result:

ok Correct (10000 test cases)

Test #7:

score: 0
Accepted
time: 641ms
memory: 11048kb

input:

10000
100
76
49
35
34
5
3
11
11
11
100
29
29
29
29
29
29
29
27
26
100
64
64
64
64
69
78
77
84
85
83
100
51
51
57
98
92
79
81
84
85
83
100
44
75
13
13
12
1
4
9
9
100
64
92
22
19
27
25
33
35
37
100
93
93
86
56
59
40
41
44
45
47
100
37
2
97
81
76
76
77
70
70
100
76
76
58
94
95
80
79
85
85
100
32
32
32
...

output:

? 1 100
? 39 100
? 1 38
? 16 38
? 1 15
? 1 9
? 10 15
? 10 13
? 10 11
! 10
? 1 100
? 1 62
? 1 38
? 16 38
? 16 29
? 21 29
? 25 29
? 27 29
? 25 26
! 25
? 1 100
? 39 100
? 63 100
? 63 85
? 63 76
? 77 85
? 77 81
? 82 85
? 84 85
? 82 83
! 82
? 1 100
? 39 100
? 39 76
? 77 100
? 86 100
? 77 85
? 77 81
? 82 ...

result:

ok Correct (10000 test cases)

Test #8:

score: 0
Accepted
time: 124ms
memory: 11196kb

input:

1000
1000
475
475
728
896
867
831
831
828
841
837
847
847
847
848
1000
278
17
974
811
757
751
637
637
637
637
637
639
642
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
460
460
460
462
463
1000
978
978
978
978
978
978
997
914
914
920
927
929
9...

output:

? 1 1000
? 383 1000
? 383 764
? 765 1000
? 855 1000
? 765 854
? 799 854
? 799 832
? 833 854
? 833 845
? 846 854
? 846 850
? 846 848
? 847 848
! 846
? 1 1000
? 1 618
? 619 1000
? 765 1000
? 619 764
? 675 764
? 619 674
? 619 652
? 632 652
? 632 644
? 637 644
? 637 641
? 642 644
? 642 643
! 644
? 1 100...

result:

ok Correct (1000 test cases)

Test #9:

score: 0
Accepted
time: 85ms
memory: 10976kb

input:

1017
272
246
111
27
52
73
73
73
68
77
78
75
114
105
91
2
2
2
2
2
2
2
910
173
173
173
173
127
14
14
29
35
37
51
51
51
50
726
229
229
438
118
149
63
28
17
17
13
24
24
24
861
315
104
671
688
632
632
652
593
593
593
593
593
594
596
1984
133
133
133
406
571
512
724
704
688
673
650
650
650
652
649
1145
98...

output:

? 1 272
? 105 272
? 1 104
? 1 64
? 65 104
? 65 89
? 65 79
? 65 73
? 74 79
? 76 79
? 74 75
! 74
? 1 114
? 45 114
? 1 44
? 1 27
? 1 17
? 1 10
? 1 6
? 1 4
? 1 2
! 1
? 1 910
? 1 562
? 1 347
? 1 214
? 83 214
? 1 82
? 1 51
? 1 31
? 32 51
? 32 43
? 44 51
? 47 51
? 49 51
? 50 51
! 49
? 1 726
? 1 449
? 173 4...

result:

ok Correct (1017 test cases)

Test #10:

score: 0
Accepted
time: 14ms
memory: 11116kb

input:

10
100000
3893
3893
30673
43582
43582
43582
43582
43582
43582
43582
43582
43582
43470
43385
43385
43359
43289
43289
43279
43268
43268
43267
43273
43272
100000
32066
54928
68197
71764
88585
88585
85554
93282
94213
91599
92129
91474
91474
91474
91446
91305
91325
91348
91348
91341
91355
91354
91351
913...

output:

? 1 100000
? 1 61803
? 1 38196
? 38197 61803
? 38197 52786
? 38197 47213
? 41641 47213
? 41641 45084
? 41641 43768
? 42454 43768
? 42956 43768
? 43267 43768
? 43459 43768
? 43267 43458
? 43267 43385
? 43313 43385
? 43267 43312
? 43267 43294
? 43278 43294
? 43267 43277
? 43267 43273
? 43267 43270
? 4...

result:

ok Correct (10 test cases)

Test #11:

score: 0
Accepted
time: 18ms
memory: 11016kb

input:

21
84335
47947
60969
22445
22445
22445
22445
20931
19830
19815
17079
17079
17079
17084
17352
17352
17352
17346
17316
17316
17316
17318
17320
17319
17321
159962
128177
145530
35270
35270
35270
34180
40850
38954
43550
43550
43550
43550
43550
43489
43765
43765
43753
43675
43675
43670
43695
43695
43695
...

output:

? 1 84335
? 32214 84335
? 1 32213
? 12305 32213
? 12305 24608
? 17005 24608
? 19910 24608
? 17005 19909
? 18115 19909
? 17005 18114
? 17005 17690
? 17005 17428
? 17005 17266
? 17267 17428
? 17267 17366
? 17305 17366
? 17329 17366
? 17305 17328
? 17314 17328
? 17314 17322
? 17314 17318
? 17319 17322
...

result:

ok Correct (21 test cases)

Test #12:

score: 0
Accepted
time: 6ms
memory: 11180kb

input:

1
1000000
641602
641602
641602
641602
732855
783270
783270
783270
783270
786055
794273
790964
797591
797591
797591
797004
796734
796734
796788
796850
796850
796850
796850
796844
796864
796864
796866
796863

output:

? 1 1000000
? 381967 1000000
? 618035 1000000
? 618035 854102
? 618035 763932
? 763933 854102
? 763933 819660
? 763933 798374
? 777089 798374
? 777089 790243
? 790244 798374
? 790244 795268
? 795269 798374
? 796456 798374
? 796456 797641
? 796909 797641
? 796456 796908
? 796629 796908
? 796629 79680...

result:

ok Correct (1 test case)

Test #13:

score: 0
Accepted
time: 16ms
memory: 11036kb

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
5243
4731
4717
4684
4684
4684
4684
4684
4681
4692
4692
4691
4693
221085
1...

output:

? 1 232936
? 88975 232936
? 143964 232936
? 177949 232936
? 198953 232936
? 211934 232936
? 219957 232936
? 224915 232936
? 224915 229872
? 226809 229872
? 224915 226808
? 224915 226084
? 225362 226084
? 225362 225808
? 225533 225808
? 225362 225532
? 225427 225532
? 225362 225426
? 225362 225401
? ...

result:

ok Correct (16 test cases)

Test #14:

score: 0
Accepted
time: 173ms
memory: 11036kb

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
4
3
2
922
921
922
352
351
135
134
52
51
20
19
8
7
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
...

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
? 5 11
? 1 4
? 3 4
? 1 2
! 1
? 1 92...

result:

ok Correct (1994 test cases)

Test #15:

score: 0
Accepted
time: 24ms
memory: 11024kb

input:

18
153667
153667
153666
58696
58695
22420
22419
8564
8563
3271
3270
1250
1249
478
477
183
182
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
? 1251 3271
? 1 1250
? 479 1250
? 1 478
? 184 478
? 1 183
? 71 183
? 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: 10ms
memory: 11092kb

input:

1
1000000
999998
1000000
381966
381965
145898
145897
55728
55727
21286
21285
8131
8130
3106
3105
1187
1186
454
453
174
173
67
66
26
25
10
9
4
3
2

output:

? 1 1000000
? 381967 1000000
? 1 381966
? 145899 381966
? 1 145898
? 55729 145898
? 1 55728
? 21287 55728
? 1 21286
? 8132 21286
? 1 8131
? 3107 8131
? 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: 189ms
memory: 11028kb

input:

1994
667
666
454
27
27
27
27
27
28
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
40
51
18
12
7
8
3
2
639
639
421
215
147
68
72
2
2
2
2
2
2
3
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
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 9
? 1 5
? 1 3
? 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
? 5 11
? 1 4
? 3 4
? 1 2
! 1
? 1 922
?...

result:

ok Correct (1994 test cases)

Test #18:

score: 0
Accepted
time: 17ms
memory: 10992kb

input:

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

output:

? 1 153667
? 58697 153667
? 1 58696
? 22421 58696
? 1 22420
? 1 13856
? 5294 13856
? 1 5293
? 1 3271
? 1251 3271
? 1 1250
? 1 772
? 1 477
? 183 477
? 1 182
? 1 112
? 1 69
? 1 43
? 18 43
? 1 17
? 8 17
? 1 7
? 4 7
? 1 3
? 2 3
! 1
? 1 211376
? 80740 211376
? 1 80739
? 30841 80739
? 1 30840
? 1 19060
? ...

result:

ok Correct (18 test cases)

Test #19:

score: 0
Accepted
time: 10ms
memory: 11032kb

input:

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

output:

? 1 1000000
? 381967 1000000
? 1 381966
? 1 236068
? 90171 236068
? 1 90170
? 1 55728
? 1 34442
? 1 21286
? 1 13155
? 1 8130
? 3107 8130
? 1 3106
? 1188 3106
? 1 1187
? 1 733
? 1 453
? 1 280
? 1 173
? 1 107
? 42 107
? 1 41
? 17 41
? 1 16
? 7 16
? 1 6
? 1 4
? 3 4
? 1 2
! 1

result:

ok Correct (1 test case)

Test #20:

score: 0
Accepted
time: 12ms
memory: 11044kb

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
701359
701353
701352
701356

output:

? 1 999999
? 1 618033
? 618034 999999
? 763932 999999
? 618034 763931
? 673762 763931
? 708204 763931
? 673762 708203
? 686918 708203
? 695049 708203
? 700074 708203
? 703180 708203
? 700074 703179
? 700074 701992
? 700807 701992
? 700807 701539
? 700807 701259
? 701260 701539
? 701367 701539
? 7012...

result:

ok Correct (1 test case)

Test #21:

score: 0
Accepted
time: 15ms
memory: 11156kb

input:

1
999998
295598
295598
73514
537464
537464
537464
537464
537464
537464
537464
537464
537464
537464
537464
536777
536636
536275
536097
536002
536271
536262
536208
536208
536208
536206
536195
536197
536198

output:

? 1 999998
? 1 618033
? 1 381965
? 381966 618033
? 472136 618033
? 527864 618033
? 527864 583591
? 527864 562305
? 527864 549149
? 535995 549149
? 535995 544124
? 535995 541018
? 535995 539099
? 535995 537913
? 536728 537913
? 535995 536727
? 536275 536727
? 535995 536274
? 535995 536167
? 536168 53...

result:

ok Correct (1 test case)

Test #22:

score: 0
Accepted
time: 15ms
memory: 11120kb

input:

1
999997
339297
339297
339297
339297
339297
355318
471212
471212
471212
468570
453304
453304
453304
453304
453304
453304
453059
452873
452842
452945
452950
453017
453017
453030
453013
453011
453007
453007

output:

? 1 999997
? 1 618032
? 236068 618032
? 236068 472134
? 326238 472134
? 326238 416406
? 416407 472134
? 437693 472134
? 450849 472134
? 458980 472134
? 450849 458979
? 450849 455873
? 452768 455873
? 452768 454686
? 452768 453953
? 452768 453500
? 453048 453500
? 452768 453047
? 452768 452940
? 4529...

result:

ok Correct (1 test case)

Test #23:

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

input:

1
999996
578161
578161
472988
785834
785834
797735
888583
907890
865390
865390
865390
864247
859775
859775
859775
859775
859584
859300
859300
859303
859239
859239
859239
859239
859237
859232
859234
859235

output:

? 1 999996
? 381966 999996
? 381966 763929
? 763930 999996
? 763930 909826
? 763930 854098
? 854099 909826
? 875385 909826
? 854099 875384
? 854099 867253
? 859124 867253
? 862230 867253
? 859124 862229
? 859124 861042
? 859124 860309
? 859124 859856
? 859404 859856
? 859124 859403
? 859231 859403
?...

result:

ok Correct (1 test case)

Test #24:

score: 0
Accepted
time: 13ms
memory: 11132kb

input:

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

output:

? 1 500000
? 1 309017
? 1 190983
? 190984 309017
? 236069 309017
? 190984 236068
? 208205 236068
? 208205 225425
? 225426 236068
? 225426 232003
? 225426 229490
? 225426 227937
? 225426 226977
? 226019 226977
? 226019 226611
? 226612 226977
? 226752 226977
? 226838 226977
? 226752 226837
? 226785 22...

result:

ok Correct (2 test cases)

Test #25:

score: 0
Accepted
time: 15ms
memory: 11044kb

input:

2
499999
493493
493493
493493
493493
493493
493493
487773
471068
471068
471068
471825
466355
465991
467320
467320
467320
467320
467320
467277
467382
467361
467345
467345
467345
467344
467338
467339
499999
101651
101651
101651
159545
24247
24247
18123
9237
9237
9237
8975
6574
6338
4671
4669
4261
4261...

output:

? 1 499999
? 190984 499999
? 309018 499999
? 381967 499999
? 427052 499999
? 454916 499999
? 472137 499999
? 454916 472136
? 461494 472136
? 465559 472136
? 468072 472136
? 465559 468071
? 465559 467111
? 467112 468071
? 467112 467704
? 467112 467477
? 467252 467477
? 467252 467391
? 467252 467337
?...

result:

ok Correct (2 test cases)

Test #26:

score: 0
Accepted
time: 10ms
memory: 11096kb

input:

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

output:

? 1 499998
? 190983 499998
? 1 190982
? 72950 190982
? 1 72949
? 27865 72949
? 27865 55728
? 38508 55728
? 45086 55728
? 38508 45085
? 41021 45085
? 38508 41020
? 38508 40060
? 40061 41020
? 40061 40653
? 40061 40426
? 40201 40426
? 40287 40426
? 40287 40372
? 40320 40372
? 40287 40319
? 40300 40319...

result:

ok Correct (2 test cases)

Test #27:

score: 0
Accepted
time: 21ms
memory: 11200kb

input:

2
499997
274071
318426
94336
90770
167121
159831
135636
135636
137448
130923
129808
133612
133612
133655
133080
133116
132781
132781
132781
132811
132768
132770
132743
132743
132746
132748
132748
499997
242708
310592
44473
60177
160791
160791
160791
148482
172524
173588
164685
164685
164155
163524
1...

output:

? 1 499997
? 190983 499997
? 1 190982
? 1 118033
? 118034 190982
? 145898 190982
? 118034 145897
? 128677 145897
? 135255 145897
? 128677 135254
? 128677 132741
? 132742 135254
? 132742 134294
? 133335 134294
? 132742 133334
? 132969 133334
? 132742 132968
? 132742 132881
? 132742 132827
? 132775 13...

result:

ok Correct (2 test cases)

Test #28:

score: 0
Accepted
time: 278ms
memory: 11100kb

input:

10000
2
1
2
2
3
2
1
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
3
5
5
5
5
5
3
3
4
5
3
3
3
5
5
5
4
5
4
4
4
5
4
4
4
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
? 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: 334ms
memory: 11076kb

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

result:

ok Correct (10000 test cases)

Test #30:

score: 0
Accepted
time: 289ms
memory: 10984kb

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
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
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
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
? 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
? 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: 334ms
memory: 11024kb

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: 337ms
memory: 11032kb

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
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
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
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
? 6 7
! 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: 299ms
memory: 11024kb

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: 283ms
memory: 11032kb

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
3
4
9
3
3
3
4
9
3
3
3
4
9
3
3
2
4
9
3
3
2
4
9
3
3
3
4
9
3
3
3
4
9
3
3
3
4
9
3
3
2
4
9
3
3
2
4
9
3
3
2
4
9
3
3
3
4
9
3
3
3
4
9
3
3
3
4
9
3
3
2
4
9
3
3
2
4
9
3
3
2
4
9
3
3
3
4
9
3
3
3
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
? 3 5
? 3 4
...

result:

ok Correct (10000 test cases)

Test #35:

score: 0
Accepted
time: 366ms
memory: 11032kb

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: 287ms
memory: 11048kb

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: 298ms
memory: 11092kb

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

result:

ok Correct (10000 test cases)

Test #38:

score: 0
Accepted
time: 356ms
memory: 11064kb

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: 356ms
memory: 10980kb

input:

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

output:

? 1 9
? 5 9
? 7 9
? 8 9
! 9
? 1 9
? 5 9
? 7 9
? 8 9
! 8
? 1 9
? 5 9
? 7 9
? 7 8
! 9
? 1 9
? 5 9
? 7 9
? 7 8
! 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
? 7 9
? 7 8
! 8
? 1 9
? 5 9
? 7 9
? ...

result:

ok Correct (10000 test cases)

Test #40:

score: 0
Accepted
time: 343ms
memory: 11048kb

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: 322ms
memory: 11032kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #42:

score: 0
Accepted
time: 345ms
memory: 10976kb

input:

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

output:

? 1 9
? 5 9
? 7 9
? 8 9
! 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
? 8 9
! 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
? 7 9
? 7 8
! 8
? 1 9
? 5 9
? 7 9
? ...

result:

ok Correct (10000 test cases)

Test #43:

score: 0
Accepted
time: 313ms
memory: 10976kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #44:

score: 0
Accepted
time: 334ms
memory: 11080kb

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: 307ms
memory: 11100kb

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: 318ms
memory: 11184kb

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
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
4
9
4
4
4
3
9
4
4
4
3
9
4
4
4
4
9
4
4
4
4
9
4
4
4
3
9
4
4
4
4
9
4
4
4
3
9
4
4
4
4
9
4
4
4
4
9
4
4
4
3
9
4
4
4
4
9
4
4
4
4
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: 332ms
memory: 11096kb

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:13:19 | OpenSource Project