QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#542826#8939. Permutationucup-team1231#AC ✓963ms57852kbPython33.6kb2024-09-01 06:12:552024-09-01 06:12:56

Judging History

This is the latest submission verdict.

  • [2024-09-01 06:12:56]
  • Judged
  • Verdict: AC
  • Time: 963ms
  • Memory: 57852kb
Show
  • [2024-09-01 06:12:55]
  • Submitted

answer

import sys
T = int(input())
def calc(u):
    if u<=1: return 0
    if u==2: return 1
    if u==3: return 2
    return 3+calc((u+3)//4)
import math
cnt = 0
arr = []
tl = 0
def qry(a,b):
    if a==b:
        return -1
    # u = list(range(a,b+1))
    # global cnt
    # global tl
    # tl += b-a+1
    # cnt += 1
    # u.sort(key=lambda s:-arr[s])
    # return u[1]
    print('?',a,b)
    sys.stdout.flush()
    return int(input())
def sol():
    import random
    # n = random.randint(1,100)
    n = int(input())
    global cnt, arr, tl
    arr = list(range(1,n+1))
    random.shuffle(arr)
    arr = [0] + arr
    cnt = 0
    tl = 0
    up = math.ceil(math.log2(n)*1.5)
    L, R = 1, n
    while R-L+1 >= 4:
        u = R-L+1
        ls = [u*i//4-u*(i-1)//4 for i in [1,2,3,4]]
        ls.sort()
        x = qry(L, R)
        # [fid[t],fid[t+1])
        c0 = 10**9
        fid0 = None
        def upd(fid):
            nonlocal c0, fid0
            inseg = lambda t,u: fid[t]<=u<fid[t+1]
            if inseg(0,x) or inseg(1,x):
                co = fid[2]+fid[3]-fid[0]*2
            else:
                co = fid[4]*2-fid[1]-fid[2]
            if co>=c0: return
            c0 = co
            fid0 = fid
        upd([L,L+ls[0],L+ls[0]+ls[1],L+ls[0]+ls[1]+ls[2],L+sum(ls)])
        upd([L,L+ls[0],L+ls[0]+ls[1],L+ls[0]+ls[1]+ls[-1],L+sum(ls)])
        ls = ls[::-1]
        upd([L,L+ls[0],L+ls[0]+ls[1],L+ls[0]+ls[1]+ls[2],L+sum(ls)])
        upd([L,L+ls[1],L+ls[0]+ls[1],L+ls[0]+ls[1]+ls[2],L+sum(ls)])
        fid = fid0
        inseg = lambda t,u: fid[t]<=u<fid[t+1]
        if inseg(0,x) or inseg(1,x):
            # x = 0
            # [0,2]
            if qry(fid[0],fid[2]-1) == x:
                if inseg(0,x):
                    if qry(fid[0],fid[1]-1) == x:
                        L, R = fid[0], fid[1]-1
                    else:
                        L, R = fid[1], fid[2]-1
                else:
                    if qry(fid[1],fid[2]-1) == x:
                        L, R = fid[1], fid[2]-1
                    else:
                        L, R = fid[0], fid[1]-1
            else:
                if qry(x,fid[3]-1) == x:
                    L, R = fid[2], fid[3]-1
                else:
                    L, R = fid[3], fid[4]-1
        else:
            if qry(fid[2],fid[4]-1) == x:
                if inseg(3,x):
                    if qry(fid[3],fid[4]-1) == x:
                        L, R = fid[3], fid[4]-1
                    else:
                        L, R = fid[2], fid[3]-1
                else:
                    if qry(fid[2],fid[3]-1) == x:
                        L, R = fid[2], fid[3]-1
                    else:
                        L, R = fid[3], fid[4]-1
            else:
                if qry(fid[1],x) == x:
                    L, R = fid[1], fid[2]-1
                else:
                    L, R = fid[0], fid[1]-1

    ans = -1
    # print(R-L+1)
    if R-L+1 == 3:
        x = qry(L,L+2)
        if x == L:
            L = x+1
        elif x == R:
            R = x-1
        else:
            assert x == L+1
            u = qry(L,x)
            if u == x:
                ans = L
            else:
                ans = R
    if ans == -1:
        if R-L+1 == 2:
            ans = qry(L,R)^L^R
        else:
            assert R-L+1 == 1
            ans = L
    print('!',ans)#,'@@',tl,'@@',n,'CC',cnt,'w',up)
#    print(arr[ans])
    # assert cnt <= up
    # assert ans!=-1 and arr[ans] == n
    # assert tl <= n*3##+2 #+2
    sys.stdout.flush()
for _ in range(T):
    sol()
源文件, 语言: Python3

詳細信息

Test #1:

score: 100
Accepted
time: 6ms
memory: 11044kb

input:

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

output:

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

result:

ok Correct (3 test cases)

Test #2:

score: 0
Accepted
time: 350ms
memory: 11168kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #3:

score: 0
Accepted
time: 407ms
memory: 11164kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #4:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #5:

score: 0
Accepted
time: 703ms
memory: 11176kb

input:

10000
100
47
5
47
61
53
68
71
71
71
71
9
2
2
1
4
53
46
35
15
6
6
6
6
4
33
3
16
16
31
31
30
32
82
60
56
60
29
29
28
23
22
24
26
88
39
8
39
59
59
59
59
61
59
71
24
29
29
59
54
59
65
66
64
63
92
52
52
56
88
88
88
88
89
88
24
11
11
9
5
6
5
3
66
51
51
66
45
43
45
39
40
39
92
43
43
38
20
20
21
17
17
48
1
...

output:

? 1 100
? 1 50
? 47 75
? 51 75
? 51 62
? 61 68
? 69 75
? 69 71
? 70 71
? 70 71
! 70
? 1 9
? 1 4
? 1 2
? 3 4
! 3
? 1 53
? 28 53
? 15 46
? 1 14
? 1 6
? 4 6
? 4 6
? 4 5
! 5
? 1 33
? 1 16
? 3 24
? 25 33
? 30 33
? 30 31
? 32 33
! 33
? 1 82
? 43 82
? 22 60
? 22 42
? 22 31
? 27 31
? 22 26
? 22 23
? 23 24
?...

result:

ok Correct (10000 test cases)

Test #6:

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

input:

10000
50
10
10
10
10
7
10
6
5
50
11
11
9
18
16
21
23
22
50
44
40
44
20
20
21
26
25
26
50
24
14
29
45
45
45
45
46
50
50
50
50
50
50
49
47
45
50
36
39
23
12
12
11
8
10
50
29
36
20
13
12
6
3
3
50
30
42
22
1
1
1
1
2
50
25
25
25
25
25
27
30
29
50
18
20
20
49
47
47
39
39
50
9
9
9
9
9
7
11
10
50
26
43
26
1...

output:

? 1 50
? 1 24
? 1 12
? 1 12
? 7 12
? 4 10
? 4 6
? 4 5
! 4
? 1 50
? 1 24
? 1 12
? 13 24
? 13 18
? 18 21
? 22 24
? 22 23
! 24
? 1 50
? 27 50
? 14 44
? 14 26
? 20 26
? 20 22
? 23 26
? 25 26
? 24 26
! 24
? 1 50
? 1 24
? 24 37
? 38 50
? 45 50
? 45 47
? 45 47
? 46 47
! 47
? 1 50
? 27 50
? 39 50
? 39 50
? ...

result:

ok Correct (10000 test cases)

Test #7:

score: 0
Accepted
time: 963ms
memory: 11020kb

input:

10000
100
76
78
35
5
5
3
9
9
9
9
100
29
29
50
20
20
20
20
21
22
24
100
64
64
69
88
100
88
86
87
84
83
100
51
51
57
98
92
92
79
79
80
81
100
44
44
50
13
24
13
12
11
11
7
100
64
92
64
41
44
41
33
34
35
37
100
93
56
93
40
40
44
49
50
47
45
100
37
2
37
57
54
60
74
75
73
70
100
76
76
76
76
76
80
86
87
86...

output:

? 1 100
? 51 100
? 26 76
? 1 25
? 1 12
? 1 6
? 7 12
? 9 12
? 9 10
? 9 10
! 10
? 1 100
? 1 50
? 26 50
? 1 25
? 14 25
? 20 25
? 20 25
? 20 21
? 20 23
? 24 25
! 25
? 1 100
? 51 100
? 51 75
? 76 100
? 88 100
? 82 88
? 82 87
? 86 87
? 84 86
? 82 83
! 82
? 1 100
? 51 100
? 51 75
? 76 100
? 89 100
? 83 98
...

result:

ok Correct (10000 test cases)

Test #8:

score: 0
Accepted
time: 323ms
memory: 11108kb

input:

1000
1000
475
426
728
896
974
896
867
867
869
858
860
851
847
847
1000
278
17
278
598
534
598
679
665
679
652
655
647
641
642
642
1000
75
128
75
607
604
644
713
695
732
749
745
749
742
741
742
1000
239
239
45
432
432
429
442
442
451
458
459
458
462
461
463
1000
978
978
978
978
978
997
914
914
920
93...

output:

? 1 1000
? 1 500
? 475 750
? 751 1000
? 877 1000
? 814 896
? 814 876
? 846 876
? 862 876
? 846 861
? 854 861
? 850 858
? 846 849
? 846 847
! 846
? 1 1000
? 1 500
? 278 750
? 501 750
? 501 624
? 598 687
? 625 687
? 657 687
? 641 679
? 641 656
? 649 656
? 645 652
? 641 644
? 641 642
? 641 643
! 644
? ...

result:

ok Correct (1000 test cases)

Test #9:

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

input:

1017
272
246
186
246
111
110
110
73
73
73
73
73
114
105
91
91
2
2
2
2
2
3
910
173
173
173
173
127
127
14
28
29
56
51
56
48
47
48
726
229
229
201
118
149
63
28
28
28
28
28
29
26
861
315
104
315
491
528
551
632
641
614
593
593
594
597
596
1984
133
133
406
571
571
512
724
704
704
650
650
650
650
651
65...

output:

? 1 272
? 137 272
? 69 246
? 69 136
? 103 136
? 86 111
? 69 85
? 69 76
? 73 76
? 73 76
? 73 74
! 74
? 1 114
? 59 114
? 30 105
? 1 29
? 1 14
? 1 7
? 1 7
? 1 3
? 2 3
! 1
? 1 910
? 1 454
? 1 227
? 1 227
? 115 227
? 58 173
? 1 57
? 1 28
? 14 42
? 43 57
? 51 57
? 47 56
? 47 50
? 47 48
? 48 49
! 49
? 1 72...

result:

ok Correct (1017 test cases)

Test #10:

score: 0
Accepted
time: 336ms
memory: 18760kb

input:

10
100000
3893
3893
3505
30673
33920
30673
43582
43582
43582
43582
43582
43470
43242
43242
43197
43289
43289
43298
43268
43268
43267
43273
43272
43273
100000
32066
19090
54928
88585
88585
88585
88585
89959
88585
91599
91474
91599
91257
91257
91225
91398
91383
91398
91339
91337
91339
91348
91347
9134...

output:

? 1 100000
? 1 50000
? 1 25000
? 25001 50000
? 25001 37500
? 30673 43750
? 37501 43750
? 40627 43750
? 42189 43750
? 42189 43750
? 42971 43750
? 43361 43750
? 42971 43360
? 43167 43360
? 43167 43263
? 43264 43360
? 43264 43311
? 43288 43311
? 43264 43287
? 43264 43275
? 43264 43269
? 43270 43275
? 4...

result:

ok Correct (10 test cases)

Test #11:

score: 0
Accepted
time: 373ms
memory: 23908kb

input:

21
84335
47947
60969
22445
9296
1509
11772
20931
19830
20931
17510
17510
17606
17352
17352
17352
17352
17346
17352
17338
17337
17328
17320
17320
17321
17323
159962
128177
145530
128177
54814
54814
59035
49869
48003
49869
43214
43214
43214
43214
43231
43550
43675
43675
43675
43675
43670
43689
43695
4...

output:

? 1 84335
? 42169 84335
? 21085 47947
? 1 21084
? 1 10542
? 9296 15813
? 15814 21084
? 18450 21084
? 17132 20931
? 17132 18449
? 17132 17789
? 17461 17789
? 17132 17460
? 17297 17460
? 17297 17378
? 17297 17378
? 17339 17378
? 17318 17352
? 17318 17338
? 17329 17338
? 17324 17338
? 17318 17323
? 173...

result:

ok Correct (21 test cases)

Test #12:

score: 0
Accepted
time: 442ms
memory: 57836kb

input:

1
1000000
641602
641602
561698
783270
783270
783270
783270
783270
783270
783270
786055
786055
794273
794682
794682
796734
796734
796734
796734
796686
796788
796850
796850
796851
796864
796864
796866
796861
796863

output:

? 1 1000000
? 500001 1000000
? 500001 750000
? 750001 1000000
? 750001 875000
? 750001 812500
? 750001 812500
? 781251 812500
? 781251 796875
? 781251 796875
? 781251 789062
? 783270 792968
? 792969 796875
? 792969 794921
? 794273 795898
? 795899 796875
? 796388 796875
? 796632 796875
? 796632 79687...

result:

ok Correct (1 test case)

Test #13:

score: 0
Accepted
time: 395ms
memory: 39696kb

input:

16
232936
229707
229707
229707
229707
229707
229707
229707
231039
229707
223556
223533
224031
225261
225261
225261
225261
225290
225290
225375
225395
225407
225417
225419
225417
225425
225425
8676
6498
6498
6498
6498
5867
4978
4731
4731
4731
4731
4731
4717
4684
4684
4681
4692
4692
4691
4693
221085
1...

output:

? 1 232936
? 116469 232936
? 174703 232936
? 174703 232936
? 203821 232936
? 218379 232936
? 218379 232936
? 225659 232936
? 222019 229707
? 222019 225658
? 222019 223838
? 223556 224748
? 224749 225658
? 225205 225658
? 225205 225431
? 225205 225431
? 225205 225317
? 225261 225374
? 225375 225431
?...

result:

ok Correct (16 test cases)

Test #14:

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

input:

1994
667
666
667
665
167
166
166
42
41
41
11
10
10
3
2
374
373
374
372
94
93
93
24
23
23
6
5
5
2
488
486
488
485
122
121
121
31
30
30
8
7
7
2
922
921
922
920
231
230
230
58
57
57
15
14
14
4
3
3
639
637
639
636
160
159
159
40
39
39
10
9
9
3
2
353
350
353
349
89
88
88
23
22
22
6
5
5
2
71
66
71
65
18
1...

output:

? 1 667
? 335 667
? 168 666
? 1 167
? 85 167
? 43 167
? 1 42
? 23 42
? 12 42
? 1 11
? 7 11
? 4 11
? 1 3
? 1 2
! 1
? 1 374
? 189 374
? 95 373
? 1 94
? 49 94
? 25 94
? 1 24
? 13 24
? 7 24
? 1 6
? 5 6
? 3 6
? 1 2
! 1
? 1 488
? 245 488
? 123 486
? 1 122
? 63 122
? 32 122
? 1 31
? 17 31
? 9 31
? 1 8
? 5 ...

result:

ok Correct (1994 test cases)

Test #15:

score: 0
Accepted
time: 380ms
memory: 36732kb

input:

18
153667
153667
153666
153666
38417
38416
38416
9605
9604
9604
2402
2401
2401
601
600
600
151
150
150
38
37
37
10
9
9
3
2
211376
211374
211376
211373
52844
52843
52843
13211
13210
13210
3303
3302
3302
826
825
825
207
206
206
52
51
51
13
12
12
4
3
3
195330
195326
195330
195325
48833
48832
48832
1220...

output:

? 1 153667
? 76835 153667
? 38418 153667
? 1 38417
? 19210 38417
? 9606 38417
? 1 9605
? 4804 9605
? 2403 9605
? 1 2402
? 1203 2402
? 602 2402
? 1 601
? 302 601
? 152 601
? 1 151
? 77 151
? 39 151
? 1 38
? 21 38
? 11 38
? 1 10
? 7 10
? 4 10
? 1 3
? 1 2
! 1
? 1 211376
? 105689 211376
? 52845 211374
?...

result:

ok Correct (18 test cases)

Test #16:

score: 0
Accepted
time: 448ms
memory: 57852kb

input:

1
1000000
999998
1000000
999997
250000
249999
249999
62500
62499
62499
15625
15624
15624
3907
3906
3906
977
976
976
245
244
244
62
61
61
16
15
15
4
3
3

output:

? 1 1000000
? 500001 1000000
? 250001 999998
? 1 250000
? 125001 250000
? 62501 250000
? 1 62500
? 31251 62500
? 15626 62500
? 1 15625
? 7814 15625
? 3908 15625
? 1 3907
? 1955 3907
? 978 3907
? 1 977
? 490 977
? 246 977
? 1 245
? 124 245
? 63 245
? 1 62
? 33 62
? 17 62
? 1 16
? 9 16
? 5 16
? 1 4
? ...

result:

ok Correct (1 test case)

Test #17:

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

input:

1994
667
666
454
454
27
27
27
27
28
13
2
2
2
2
374
372
224
224
91
67
67
16
14
14
5
6
3
2
488
485
370
161
83
108
44
15
15
14
6
7
3
2
922
921
662
279
40
40
40
40
51
36
12
14
7
3
4
2
639
639
421
421
147
95
68
2
2
2
2
2
2
2
353
351
200
200
27
27
44
22
17
8
2
2
71
71
47
47
6
6
8
3
4
2
24
22
24
7
2
2
567
...

output:

? 1 667
? 335 667
? 168 666
? 1 167
? 1 83
? 1 41
? 1 41
? 22 41
? 12 27
? 1 11
? 1 5
? 1 2
? 1 2
! 1
? 1 374
? 189 374
? 95 372
? 1 94
? 49 94
? 25 91
? 1 24
? 13 24
? 7 16
? 1 6
? 5 6
? 3 5
? 1 2
! 1
? 1 488
? 245 488
? 123 485
? 1 122
? 63 122
? 32 83
? 1 31
? 1 15
? 8 15
? 1 7
? 5 7
? 3 6
? 1 2
...

result:

ok Correct (1994 test cases)

Test #18:

score: 0
Accepted
time: 385ms
memory: 36524kb

input:

18
153667
153667
101545
50668
27244
25988
25988
8350
5820
3091
1644
1499
1499
306
551
198
24
24
24
24
21
16
7
9
5
3
2
211376
211375
173406
91641
36438
47063
33589
4235
4235
5138
3075
2649
973
436
539
221
79
79
60
10
10
10
10
8
8
2
2
195330
195325
161600
161600
36944
36871
17928
1018
1018
1018
1018
1...

output:

? 1 153667
? 76835 153667
? 38418 153667
? 1 38417
? 19210 38417
? 9606 27244
? 1 9605
? 4804 9605
? 2403 8350
? 1 2402
? 1203 2402
? 602 1644
? 1 601
? 302 601
? 152 306
? 1 151
? 1 75
? 1 37
? 1 37
? 20 37
? 11 24
? 1 10
? 7 10
? 4 7
? 1 3
? 1 2
! 1
? 1 211376
? 105689 211376
? 52845 211375
? 1 52...

result:

ok Correct (18 test cases)

Test #19:

score: 0
Accepted
time: 445ms
memory: 57772kb

input:

1
1000000
999998
783271
783271
169408
237630
160728
8002
8002
8002
8002
11377
6079
1522
1522
1781
42
42
42
42
42
42
42
43
18
13
15
11
4
3
2

output:

? 1 1000000
? 500001 1000000
? 250001 999998
? 1 250000
? 125001 250000
? 62501 169408
? 1 62500
? 1 31250
? 1 15625
? 1 15625
? 7814 15625
? 3908 8002
? 1 3907
? 1 1953
? 977 1953
? 1 976
? 1 488
? 1 244
? 1 244
? 1 122
? 1 61
? 1 61
? 32 61
? 17 42
? 1 16
? 9 16
? 5 13
? 1 4
? 3 4
? 2 4
! 1

result:

ok Correct (1 test case)

Test #20:

score: 0
Accepted
time: 460ms
memory: 57788kb

input:

1
999999
260772
45203
260772
507886
500600
549347
730076
742879
706326
692862
692649
697541
701051
700204
701051
702009
701978
701978
701202
701249
701331
701361
701361
701361
701361
701368
701361
701359
701360
701358

output:

? 1 999999
? 1 499999
? 260772 749999
? 500000 749999
? 500000 624999
? 507886 687499
? 687500 749999
? 718750 749999
? 703125 730076
? 687500 703124
? 687500 695311
? 692862 699217
? 699218 703124
? 699218 701170
? 701051 702147
? 701171 702147
? 701660 702147
? 701416 702009
? 701171 701415
? 7011...

result:

ok Correct (1 test case)

Test #21:

score: 0
Accepted
time: 469ms
memory: 57780kb

input:

1
999998
295598
73514
295598
537464
537464
537464
537464
537464
537464
537464
537464
537464
537464
538126
537464
536777
536869
536636
536275
536350
536275
536229
536242
536219
536208
536209
536208
536201
536200
536201

output:

? 1 999998
? 1 499998
? 295598 749998
? 499999 749998
? 499999 624998
? 499999 562498
? 499999 562498
? 531249 562498
? 531249 546873
? 531249 546873
? 531249 539060
? 535155 539060
? 535155 539060
? 537109 539060
? 536132 537464
? 536132 537108
? 536621 537108
? 536377 536777
? 536132 536376
? 5362...

result:

ok Correct (1 test case)

Test #22:

score: 0
Accepted
time: 435ms
memory: 57844kb

input:

1
999997
339297
339297
339297
339297
355318
355318
489939
471212
471212
445254
439876
448004
449645
451130
451130
452873
452873
452687
453059
453059
453059
453059
453052
453052
453017
453013
453017
453007
453006
453007

output:

? 1 999997
? 1 499998
? 250000 499998
? 250000 499998
? 250000 374998
? 339297 437498
? 437499 499998
? 468749 499998
? 453124 489939
? 437499 453123
? 437499 445310
? 445254 449216
? 449217 453123
? 449217 451169
? 449645 452146
? 452147 453123
? 452636 453123
? 452636 452879
? 452880 453123
? 4530...

result:

ok Correct (1 test case)

Test #23:

score: 0
Accepted
time: 450ms
memory: 57852kb

input:

1
999996
578161
578161
665875
785834
785834
797735
839217
821597
839217
853100
853100
853969
858027
858027
857481
858782
858873
858873
859300
859303
859300
859239
859239
859239
859239
859239
859240
859237
859235

output:

? 1 999996
? 499999 999996
? 499999 749997
? 749998 999996
? 749998 874996
? 749998 812496
? 812497 874996
? 812497 843746
? 839217 859371
? 843747 859371
? 851560 859371
? 851560 855465
? 855466 859371
? 857420 859371
? 857420 858395
? 858396 859371
? 858396 858883
? 858782 859127
? 859128 859371
?...

result:

ok Correct (1 test case)

Test #24:

score: 0
Accepted
time: 409ms
memory: 50024kb

input:

2
500000
114103
114103
98381
180208
168263
207866
220637
220637
222630
228173
228173
228173
228173
227703
227703
226572
226572
226659
226739
226686
226739
226759
226748
226760
226770
226769
226772
226774
500000
313297
436237
313297
246160
246160
246160
246160
238712
238712
222822
222822
223239
22604...

output:

? 1 500000
? 1 250000
? 1 125000
? 125001 250000
? 125001 187500
? 180208 218750
? 218751 250000
? 218751 234374
? 218751 226562
? 226563 234374
? 226563 230468
? 226563 228515
? 226563 228515
? 227540 228515
? 227052 228173
? 226563 227051
? 226563 226806
? 226563 226684
? 226685 226806
? 226685 22...

result:

ok Correct (2 test cases)

Test #25:

score: 0
Accepted
time: 405ms
memory: 50060kb

input:

2
499999
493493
493493
493493
493493
493493
487773
442491
446831
459196
466355
466355
465991
468187
467811
468187
467320
467320
467320
467320
467320
467320
467320
467329
467329
467345
467344
467344
467339
499999
101651
101651
101651
101651
98374
98374
24247
18123
18123
3528
2080
3528
4671
4671
4669
...

output:

? 1 499999
? 250001 499999
? 375001 499999
? 375001 499999
? 437501 499999
? 468751 499999
? 437501 468750
? 437501 453124
? 442491 460937
? 460938 468750
? 464845 468750
? 464845 466797
? 466798 468750
? 467775 468750
? 467287 468187
? 467287 467774
? 467287 467530
? 467287 467408
? 467287 467408
?...

result:

ok Correct (2 test cases)

Test #26:

score: 0
Accepted
time: 415ms
memory: 50024kb

input:

2
499998
367462
261014
193038
89479
81508
89479
53076
60946
53076
46002
45253
42856
39670
39405
39670
40342
40342
40342
40342
40342
40331
40310
40309
40296
40285
40286
40290
40291
499998
122343
3768
122343
313385
354592
287080
278240
279535
274387
252131
252131
252131
252131
252079
252602
253733
253...

output:

? 1 499998
? 250001 499998
? 125001 367462
? 1 125000
? 62501 125000
? 31251 89479
? 31251 62500
? 46877 62500
? 39064 53076
? 39064 46876
? 42971 46876
? 41018 46002
? 39064 41017
? 39064 40039
? 39670 40528
? 40040 40528
? 40285 40528
? 40285 40406
? 40285 40406
? 40285 40344
? 40315 40344
? 40285...

result:

ok Correct (2 test cases)

Test #27:

score: 0
Accepted
time: 416ms
memory: 50060kb

input:

2
499997
274071
318426
274071
167121
167121
159831
135636
135636
137448
130923
130923
130923
130923
131482
132171
132428
132396
132543
132781
132811
132781
132735
132725
132743
132750
132748
132750
132746
499997
242708
242708
242708
242708
248273
242708
160791
160791
160791
160791
160791
160496
1630...

output:

? 1 499997
? 250000 499997
? 125001 274071
? 125001 249999
? 125001 187499
? 156250 187499
? 125001 156249
? 125001 140624
? 132813 140624
? 125001 132812
? 128907 132812
? 130860 132812
? 130860 132812
? 130860 131835
? 130923 132323
? 132324 132812
? 132324 132567
? 132428 132689
? 132690 132812
?...

result:

ok Correct (2 test cases)

Test #28:

score: 0
Accepted
time: 396ms
memory: 11192kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #29:

score: 0
Accepted
time: 348ms
memory: 11124kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #30:

score: 0
Accepted
time: 388ms
memory: 10988kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #31:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #32:

score: 0
Accepted
time: 365ms
memory: 11108kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #33:

score: 0
Accepted
time: 348ms
memory: 11144kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #34:

score: 0
Accepted
time: 394ms
memory: 11208kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #35:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #36:

score: 0
Accepted
time: 400ms
memory: 11028kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #37:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #38:

score: 0
Accepted
time: 369ms
memory: 11140kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #39:

score: 0
Accepted
time: 365ms
memory: 11040kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #40:

score: 0
Accepted
time: 395ms
memory: 11088kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #41:

score: 0
Accepted
time: 365ms
memory: 11020kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #42:

score: 0
Accepted
time: 346ms
memory: 11052kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #43:

score: 0
Accepted
time: 365ms
memory: 11168kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #44:

score: 0
Accepted
time: 352ms
memory: 11040kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #45:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #46:

score: 0
Accepted
time: 382ms
memory: 10988kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #47:

score: 0
Accepted
time: 427ms
memory: 11204kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Extra Test:

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

伺服器時間: 2025-02-08 20:30:39 | 開源專案