QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#580408#8939. PermutationForever_Young#AC ✓105ms3940kbC++141017b2024-09-21 21:45:582024-09-21 21:45:58

Judging History

This is the latest submission verdict.

  • [2024-09-21 21:45:58]
  • Judged
  • Verdict: AC
  • Time: 105ms
  • Memory: 3940kb
Show
  • [2024-09-21 21:45:58]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
int t,n;
int get(int x,int y,int z){
    //printf("%d %d %d\n",x,y,z);
    if (x==y) return x;
    if (z==-1){
        printf("? %d %d\n",x,y);
        fflush(stdout);
        scanf("%d",&z);
    }
    if (y==x+1) return x+y-z;
    int mid=(x+y)/2;
    if (z>mid){
        mid=round(x+(y-x)*0.386);
        if (mid==x) mid+=1;
        printf("? %d %d\n",mid,y);
        fflush(stdout);
        int tmp;
        scanf("%d",&tmp);
        if (tmp==z) return get(mid,y,z);
        return get(x,mid-1,-1);

    }
    else{
        mid=round(y-(y-x)*0.386);
        if (mid==y) mid-=1;
        printf("? %d %d\n",x,mid);
        fflush(stdout);
        int tmp;
        scanf("%d",&tmp);
        if (tmp==z) return get(x,mid,z);
        return get(mid+1,y,-1);
    }
}
int main(){
    scanf("%d",&t);
    while (t--){
        scanf("%d",&n);
        int res=get(1,n,-1);
        printf("! %d\n",res);
        fflush(stdout);
    }
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok Correct (3 test cases)

Test #2:

score: 0
Accepted
time: 72ms
memory: 3940kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #3:

score: 0
Accepted
time: 58ms
memory: 3932kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #4:

score: 0
Accepted
time: 87ms
memory: 3872kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #5:

score: 0
Accepted
time: 105ms
memory: 3868kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #6:

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

input:

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

output:

? 1 50
? 1 31
? 1 19
? 1 12
? 5 12
? 1 4
? 1 3
! 4
? 1 50
? 1 31
? 1 19
? 20 31
? 24 31
? 27 31
? 24 26
? 25 26
! 24
? 1 50
? 20 50
? 32 50
? 20 31
? 20 27
? 20 24
? 20 22
? 23 24
! 24
? 1 50
? 1 31
? 32 50
? 39 50
? 43 50
? 43 47
? 43 45
? 46 47
! 47
? 1 50
? 20 50
? 32 50
? 39 50
? 43 50
? 46 50
?...

result:

ok Correct (10000 test cases)

Test #7:

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

input:

10000
100
76
49
35
34
5
3
11
11
11
100
29
29
29
29
29
29
30
26
26
100
64
64
69
88
88
88
86
84
83
100
51
51
57
98
92
79
79
77
81
100
44
44
50
13
24
1
4
9
9
100
64
92
22
22
19
33
30
36
37
100
93
93
86
56
59
40
44
45
45
100
37
2
97
81
76
76
74
68
68
100
76
76
76
76
76
74
86
86
85
100
32
32
32
32
31
44
...

output:

? 1 100
? 39 100
? 1 38
? 15 38
? 1 14
? 1 9
? 10 14
? 10 12
? 10 11
! 10
? 1 100
? 1 62
? 1 38
? 15 38
? 24 38
? 24 33
? 27 33
? 24 26
? 25 26
! 25
? 1 100
? 39 100
? 39 76
? 77 100
? 77 91
? 82 91
? 85 91
? 82 84
? 83 84
! 82
? 1 100
? 39 100
? 39 76
? 77 100
? 86 100
? 77 85
? 77 82
? 77 80
? 81 ...

result:

ok Correct (10000 test cases)

Test #8:

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

input:

1000
1000
475
426
728
728
747
831
831
831
828
841
841
839
844
845
1000
278
17
974
811
757
751
637
637
637
628
647
645
642
643
1000
75
128
871
985
644
686
713
713
712
732
730
737
739
741
1000
239
239
45
577
607
432
432
442
458
459
462
462
463
465
1000
978
978
978
978
978
978
997
914
914
914
920
923
9...

output:

? 1 1000
? 1 614
? 615 1000
? 615 851
? 615 760
? 761 851
? 796 851
? 817 851
? 817 838
? 839 851
? 839 846
? 839 843
? 844 846
? 844 845
! 846
? 1 1000
? 1 614
? 615 1000
? 764 1000
? 615 763
? 672 763
? 615 671
? 615 649
? 628 649
? 628 641
? 642 649
? 645 649
? 642 644
? 642 643
! 644
? 1 1000
? ...

result:

ok Correct (1000 test cases)

Test #9:

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

input:

1017
272
246
111
27
52
73
73
73
73
73
73
71
75
114
105
91
2
2
2
2
2
2
2
2
910
173
173
173
148
14
14
14
29
35
37
44
48
50
726
229
229
438
118
149
63
28
17
17
13
24
24
24
23
861
315
104
671
671
688
593
593
593
593
593
593
593
594
596
1984
133
133
133
406
571
512
724
704
673
674
650
650
650
650
650
649...

output:

? 1 272
? 106 272
? 1 105
? 1 65
? 66 105
? 66 90
? 66 81
? 66 75
? 69 75
? 71 75
? 71 73
? 74 75
! 74
? 1 114
? 45 114
? 1 44
? 1 27
? 1 17
? 1 11
? 1 7
? 1 5
? 1 3
? 1 2
! 1
? 1 910
? 1 559
? 1 344
? 133 344
? 1 132
? 1 81
? 1 50
? 1 31
? 32 50
? 32 43
? 44 50
? 44 48
? 49 50
! 49
? 1 726
? 1 446
...

result:

ok Correct (1017 test cases)

Test #10:

score: 0
Accepted
time: 3ms
memory: 3928kb

input:

10
100000
3893
3893
30673
43582
43582
43582
43582
43582
43582
43582
43582
43582
43470
43385
43389
43289
43298
43268
43268
43268
43267
43273
43272
100000
32066
54928
68197
71764
88585
88585
85554
93282
94213
91599
91599
91599
91474
91257
91257
91305
91325
91339
91355
91355
91358
91349
91351
100000
50...

output:

? 1 100000
? 1 61400
? 1 37700
? 37701 61400
? 37701 52252
? 37701 46635
? 41150 46635
? 41150 44518
? 42450 44518
? 43248 44518
? 43248 44028
? 43248 43727
? 43433 43727
? 43248 43432
? 43319 43432
? 43248 43318
? 43275 43318
? 43248 43274
? 43258 43274
? 43264 43274
? 43264 43270
? 43271 43274
? 4...

result:

ok Correct (10 test cases)

Test #11:

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

input:

21
84335
47947
60969
22445
22445
22445
22445
20931
19830
19815
17510
17510
17510
17510
17496
17352
17352
17346
17316
17316
17320
17323
17323
17323
159962
128177
145530
35270
35270
35270
34180
40850
38954
46872
46914
43823
43823
43823
43823
43765
43675
43675
43670
43695
43695
43695
43695
43695
43695
...

output:

? 1 84335
? 32554 84335
? 1 32553
? 12566 32553
? 12566 24838
? 17303 24838
? 20212 24838
? 17303 20211
? 18425 20211
? 17303 18424
? 17303 17991
? 17303 17725
? 17303 17562
? 17403 17562
? 17303 17402
? 17303 17364
? 17327 17364
? 17303 17326
? 17312 17326
? 17312 17321
? 17322 17326
? 17322 17324
...

result:

ok Correct (21 test cases)

Test #12:

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

input:

1
1000000
641602
641602
418256
783270
783270
783270
783270
786055
805651
805651
802269
797591
797591
797591
797591
797468
797004
797004
796975
796864
796864
796864
796864
796864
796864
796864
796864
796865
796861

output:

? 1 1000000
? 386001 1000000
? 386001 762996
? 762997 1000000
? 762997 908517
? 762997 852346
? 762997 817857
? 762997 796681
? 796682 817857
? 796682 809683
? 801700 809683
? 796682 801699
? 796682 799762
? 796682 798573
? 796682 797843
? 797130 797843
? 796682 797129
? 796855 797129
? 796961 79712...

result:

ok Correct (1 test case)

Test #13:

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

input:

16
232936
229707
229707
229707
229707
229707
229707
229707
229707
231039
227478
227474
225790
225790
225915
225474
225474
225483
225407
225395
225417
225417
225417
225419
225425
225425
8676
6498
6498
7154
4978
4978
4978
4978
5022
4731
4717
4684
4684
4684
4676
4692
4692
4692
4691
4695
221085
172303
2...

output:

? 1 232936
? 89914 232936
? 145120 232936
? 179017 232936
? 199830 232936
? 212609 232936
? 220455 232936
? 225273 232936
? 228231 232936
? 225273 228230
? 226414 228230
? 225273 226413
? 225273 225973
? 225543 225973
? 225273 225542
? 225377 225542
? 225441 225542
? 225377 225440
? 225377 225416
? ...

result:

ok Correct (16 test cases)

Test #14:

score: 0
Accepted
time: 31ms
memory: 3860kb

input:

1994
667
666
667
257
256
99
98
38
37
14
13
5
4
2
374
373
374
144
143
55
54
21
20
8
7
3
2
488
486
488
188
187
72
71
27
26
10
9
3
2
922
921
922
356
355
137
136
52
51
20
19
7
6
2
639
637
639
246
245
95
94
36
35
14
13
5
4
2
353
350
353
136
135
52
51
20
19
7
6
2
71
66
71
27
26
10
9
3
2
24
21
24
9
8
3
2
5...

output:

? 1 667
? 258 667
? 1 257
? 100 257
? 1 99
? 39 99
? 1 38
? 15 38
? 1 14
? 6 14
? 1 5
? 3 5
? 1 2
! 1
? 1 374
? 145 374
? 1 144
? 56 144
? 1 55
? 22 55
? 1 21
? 9 21
? 1 8
? 4 8
? 1 3
? 2 3
! 1
? 1 488
? 189 488
? 1 188
? 73 188
? 1 72
? 28 72
? 1 27
? 11 27
? 1 10
? 4 10
? 1 3
? 2 3
! 1
? 1 922
? 3...

result:

ok Correct (1994 test cases)

Test #15:

score: 0
Accepted
time: 3ms
memory: 3800kb

input:

18
153667
153667
153666
59315
59314
22895
22894
8837
8836
3411
3410
1316
1315
508
507
196
195
75
74
29
28
11
10
4
3
211376
211374
211376
81591
81590
31494
31493
12156
12155
4692
4691
1811
1810
699
698
269
268
103
102
39
38
15
14
5
4
2
195330
195326
195330
75397
75396
29103
29102
11233
11232
4336
433...

output:

? 1 153667
? 59316 153667
? 1 59315
? 22896 59315
? 1 22895
? 8838 22895
? 1 8837
? 3412 8837
? 1 3411
? 1317 3411
? 1 1316
? 509 1316
? 1 508
? 197 508
? 1 196
? 76 196
? 1 75
? 30 75
? 1 29
? 12 29
? 1 11
? 5 11
? 1 4
? 2 4
! 1
? 1 211376
? 81592 211376
? 1 81591
? 31495 81591
? 1 31494
? 12157 31...

result:

ok Correct (18 test cases)

Test #16:

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

input:

1
1000000
999998
1000000
386000
385999
148996
148995
57512
57511
22199
22198
8568
8567
3307
3306
1276
1275
492
491
190
189
73
72
28
27
10
9
3
2

output:

? 1 1000000
? 386001 1000000
? 1 386000
? 148997 386000
? 1 148996
? 57513 148996
? 1 57512
? 22200 57512
? 1 22199
? 8569 22199
? 1 8568
? 3308 8568
? 1 3307
? 1277 3307
? 1 1276
? 493 1276
? 1 492
? 191 492
? 1 190
? 74 190
? 1 73
? 29 73
? 1 28
? 11 28
? 1 10
? 4 10
? 1 3
? 2 3
! 1

result:

ok Correct (1 test case)

Test #17:

score: 0
Accepted
time: 28ms
memory: 3852kb

input:

1994
667
666
454
27
27
27
27
27
28
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
2
922
921
662
40
40
40
40
40
51
18
12
7
3
2
639
639
421
215
147
68
95
2
2
2
2
2
2
2
2
353
351
200
91
81
27
22
2
2
2
2
2
2
71
71
47
6
6
6
6
3
2
24
22
24
7
9
2
2
567
563
332
205
...

output:

? 1 667
? 258 667
? 1 257
? 1 158
? 1 97
? 1 60
? 1 37
? 15 37
? 1 14
? 1 9
? 1 6
? 1 4
? 1 3
? 1 2
! 1
? 1 374
? 145 374
? 1 144
? 56 144
? 1 55
? 22 55
? 1 21
? 9 21
? 1 8
? 4 8
? 1 3
? 2 3
! 1
? 1 488
? 189 488
? 1 188
? 73 188
? 1 72
? 28 72
? 1 27
? 11 27
? 1 10
? 4 10
? 1 3
? 2 3
! 1
? 1 922
?...

result:

ok Correct (1994 test cases)

Test #18:

score: 0
Accepted
time: 3ms
memory: 3888kb

input:

18
153667
153667
65961
50668
47562
8350
8350
5820
1644
1644
1644
1499
306
306
477
24
24
24
24
38
16
12
3
3
4
211376
211375
91641
67652
80994
4235
4235
4235
4235
3075
973
973
961
436
539
221
163
79
60
10
10
10
8
2
2
2
195330
195325
161600
36944
36944
17928
1018
1018
1018
1018
1018
1018
1556
281
281
2...

output:

? 1 153667
? 59316 153667
? 1 59315
? 22896 59315
? 1 22895
? 1 14058
? 5427 14058
? 1 5426
? 1 3332
? 1 2046
? 790 2046
? 1 789
? 1 485
? 188 485
? 1 187
? 1 115
? 1 71
? 1 44
? 18 44
? 1 17
? 7 17
? 1 6
? 1 4
? 2 4
! 1
? 1 211376
? 81592 211376
? 1 81591
? 31495 81591
? 1 31494
? 1 19338
? 1 11874...

result:

ok Correct (18 test cases)

Test #19:

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

input:

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

output:

? 1 1000000
? 386001 1000000
? 1 386000
? 1 237004
? 91484 237004
? 1 91483
? 1 56171
? 1 34489
? 1 21177
? 1 13003
? 5020 13003
? 1 5019
? 1 3082
? 1 1893
? 731 1893
? 1 730
? 1 449
? 1 276
? 1 170
? 1 105
? 1 65
? 26 65
? 1 25
? 10 25
? 1 9
? 1 6
? 3 6
? 1 2
! 1

result:

ok Correct (1 test case)

Test #20:

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

input:

1
999999
260772
507886
955966
996647
730076
730076
751781
706326
706326
706326
706326
705072
701051
701051
701051
701101
701702
701586
701488
701453
701361
701361
701361
701361
701361
701359
701356
701356

output:

? 1 999999
? 1 614000
? 614001 999999
? 762996 999999
? 614001 762995
? 671513 762995
? 706825 762995
? 671513 706824
? 685143 706824
? 693512 706824
? 698650 706824
? 701805 706824
? 698650 701804
? 699867 701804
? 700615 701804
? 700615 701345
? 701346 701804
? 701523 701804
? 701346 701522
? 7014...

result:

ok Correct (1 test case)

Test #21:

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

input:

1
999998
295598
295598
73514
537464
537464
537464
537464
537464
537464
537464
537464
537464
537464
536777
535510
535185
535839
536097
536271
536271
536262
536170
536177
536206
536206
536204
536200
536200

output:

? 1 999998
? 1 613999
? 1 376996
? 376997 613999
? 468480 613999
? 468480 557829
? 502969 557829
? 524145 557829
? 524145 544827
? 532128 544827
? 532128 539925
? 535138 539925
? 535138 538077
? 536272 538077
? 535138 536271
? 535138 535834
? 535835 536271
? 535835 536103
? 536104 536271
? 536168 53...

result:

ok Correct (1 test case)

Test #22:

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

input:

1
999997
339297
339297
339297
339297
355318
413343
417456
453304
453304
453304
453304
453304
453304
453304
453304
453304
453304
453404
453059
453059
453067
453017
453017
453019
453013
453013
453010
453009

output:

? 1 999997
? 1 613999
? 237004 613999
? 237004 468479
? 237004 379130
? 379131 468479
? 379131 433991
? 433992 468479
? 447304 468479
? 447304 460305
? 447304 455287
? 450385 455287
? 452277 455287
? 452277 454125
? 452990 454125
? 452990 453687
? 452990 453418
? 453155 453418
? 452990 453154
? 4529...

result:

ok Correct (1 test case)

Test #23:

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

input:

1
999996
578161
578161
472988
785834
785834
797735
888583
907890
865390
864247
853100
853969
859775
859775
859913
858782
858873
859300
859300
859303
859239
859239
859239
859239
859239
859239
859237
859235

output:

? 1 999996
? 385999 999996
? 385999 762993
? 762994 999996
? 762994 908513
? 762994 852343
? 852344 908513
? 874025 908513
? 852344 874024
? 860712 874024
? 852344 860711
? 852344 857481
? 857482 860711
? 858728 860711
? 859493 860711
? 858728 859492
? 858728 859197
? 859198 859492
? 859198 859379
?...

result:

ok Correct (1 test case)

Test #24:

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

input:

2
500000
114103
114103
98381
290103
281943
220637
220637
220637
220637
222630
224587
223621
226042
226042
226572
226893
226893
226930
226805
226821
226759
226748
226770
226769
226777
226777
226776
500000
313297
313297
313297
285097
246160
246160
261097
230101
228136
227098
227098
227098
227313
22604...

output:

? 1 500000
? 1 307000
? 1 188498
? 188499 307000
? 234240 307000
? 188499 234239
? 206155 234239
? 216995 234239
? 216995 227583
? 216995 223496
? 223497 227583
? 223497 226006
? 226007 227583
? 226007 226975
? 226007 226601
? 226602 226975
? 226746 226975
? 226834 226975
? 226746 226833
? 226780 22...

result:

ok Correct (2 test cases)

Test #25:

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

input:

2
499999
493493
493493
493493
493493
493493
493493
487773
471068
471068
471068
471825
468187
467811
467320
467320
467320
467320
467320
467320
467320
467329
467345
467352
467338
467335
467341
499999
101651
101651
101651
159545
24247
24247
18123
9237
8975
3528
3528
3528
2642
4671
4669
4261
4261
4261
4...

output:

? 1 499999
? 193000 499999
? 311502 499999
? 384262 499999
? 428936 499999
? 456366 499999
? 473208 499999
? 456366 473207
? 462867 473207
? 466858 473207
? 469309 473207
? 466858 469308
? 467804 469308
? 466858 467803
? 466858 467438
? 467082 467438
? 467219 467438
? 467219 467353
? 467271 467353
?...

result:

ok Correct (2 test cases)

Test #26:

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

input:

2
499998
367462
193038
152483
183238
53076
53076
60946
29299
37492
46002
42856
39670
39670
39670
40106
40342
40342
40374
40253
40253
40255
40280
40285
40296
40296
40294
40293
499998
122343
122343
3768
201785
201785
209196
246144
244788
252131
252131
252131
251090
254417
253733
253046
253040
253451
2...

output:

? 1 499998
? 193000 499998
? 1 192999
? 74498 192999
? 1 74497
? 28756 74497
? 46412 74497
? 28756 46411
? 28756 39596
? 39597 46411
? 42227 46411
? 39597 42226
? 39597 41211
? 39597 40588
? 39597 40205
? 40206 40588
? 40206 40441
? 40297 40441
? 40206 40296
? 40241 40296
? 40241 40275
? 40276 40296...

result:

ok Correct (2 test cases)

Test #27:

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

input:

2
499997
274071
318426
94336
90770
167121
159831
135636
135636
135636
137448
130923
129808
133612
133655
132171
132428
132679
132679
132735
132781
132768
132743
132743
132743
132746
132748
132748
499997
242708
242708
242708
248273
160791
160791
160791
160791
160791
160791
160791
160496
163029
163029...

output:

? 1 499997
? 192999 499997
? 1 192998
? 1 118501
? 118502 192998
? 147257 192998
? 118502 147256
? 129601 147256
? 129601 140441
? 133785 140441
? 129601 133784
? 129601 132169
? 132170 133784
? 132793 133784
? 132170 132792
? 132170 132552
? 132553 132792
? 132645 132792
? 132645 132735
? 132736 13...

result:

ok Correct (2 test cases)

Test #28:

score: 0
Accepted
time: 72ms
memory: 3848kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #29:

score: 0
Accepted
time: 71ms
memory: 3908kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #30:

score: 0
Accepted
time: 40ms
memory: 3792kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #31:

score: 0
Accepted
time: 40ms
memory: 3796kb

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #33:

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

input:

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

output:

? 1 9
? 1 6
? 7 9
? 7 8
! 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
? 7 8
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 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: 47ms
memory: 3852kb

input:

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

output:

? 1 9
? 1 6
? 7 9
? 8 9
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 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 #35:

score: 0
Accepted
time: 62ms
memory: 3788kb

input:

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

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

result:

ok Correct (10000 test cases)

Test #36:

score: 0
Accepted
time: 79ms
memory: 3792kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #37:

score: 0
Accepted
time: 66ms
memory: 3932kb

input:

10000
9
4
3
9
8
9
4
3
8
8
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
3
9
4
4
4
4
3
9
4
4
4
4
3
9
4
4
4
4
3
9
4
4
4
4
3
9
4
4
4
4
3
9
4
4
4
4
3
9
4
4
4
4
3
9
4
4
4
4
3
9
4
4
4
4
3
9
4
4
4
4
3
9
4
4
4
4
3
9
4
4
4
4
3
9
4
4
4
4
3
9
4
4
4
4
3
9
4
4
4
4
3
9
4
4
4
4
3
9
4
4
4
4
3
9
4
4
4
4
...

output:

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

result:

ok Correct (10000 test cases)

Test #38:

score: 0
Accepted
time: 86ms
memory: 3856kb

input:

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

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

result:

ok Correct (10000 test cases)

Test #39:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #40:

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

input:

10000
9
2
5
9
8
9
2
5
8
8
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
? 7 8
! 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: 68ms
memory: 3832kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #42:

score: 0
Accepted
time: 53ms
memory: 3788kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #43:

score: 0
Accepted
time: 63ms
memory: 3848kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #44:

score: 0
Accepted
time: 47ms
memory: 3912kb

input:

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

result:

ok Correct (10000 test cases)

Test #45:

score: 0
Accepted
time: 91ms
memory: 3932kb

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
6
5
9
6
6
6
5
9
6
6
6
5
9
6
6
6
5
9
6
6
6
7
9
6
6
6
7
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: 61ms
memory: 3788kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #47:

score: 0
Accepted
time: 57ms
memory: 3904kb

input:

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

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

result:

ok Correct (10000 test cases)

Extra Test:

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

Server Time: 2025-02-08 18:06:58 | OpenSource Project