QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#613594#8939. PermutationMu_SilkAC ✓136ms3700kbC++20982b2024-10-05 14:17:392024-10-05 14:19:09

Judging History

This is the latest submission verdict.

  • [2024-10-05 14:19:09]
  • Judged
  • Verdict: AC
  • Time: 136ms
  • Memory: 3700kb
Show
  • [2024-10-05 14:17:39]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int query(int l,int r){
    cout<<"? "<<l<<" "<<r<<"\n";
    int p;cin>>p;
    return p;
}

int ans=-1;
void calc(int l,int r,int p){
    if(r==l){
        ans=l;
        return;
    }
    if(r==l+1){
        if(p==0)p=query(l,r);
        ans=r+l-p;
        return;
    }
    if(p==0)p=query(l,r);
    int m1=(l*6+r*4)/10;
    int m2=(l*4+r*6)/10;
    if(p<=m2){
        if(m2-l+1>=2){
            int t=query(l,m2);
            if(t==p)calc(l,m2,p);
            else calc(m2+1,r,0);
        }
        else calc(m2+1,r,0);
    }
    else{
        if(r-m1>=2){
            int t=query(m1+1,r);
            if(t==p)calc(m1+1,r,p);
            else calc(l,m1,0);
        }
        else calc(l,m1,0);
    }
}

void solve(){
    int n;cin>>n;
    calc(1,n,0);
    cout<<"! "<<ans<<endl;
}

int main(){
    int n=1;
    cin>>n;
    while(n--)solve();
    return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok Correct (3 test cases)

Test #2:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #3:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #4:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #5:

score: 0
Accepted
time: 101ms
memory: 3564kb

input:

10000
100
47
5
61
61
61
68
71
71
72
69
9
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
28
23
24
26
88
39
8
59
59
59
59
59
59
59
71
24
29
59
44
65
65
64
61
61
92
52
45
88
88
88
88
85
91
91
24
11
11
9
5
5
5
66
51
51
45
29
28
39
39
38
40
92
43
43
50
20
20
20
20
20
19
48
1
1
1
1
...

output:

? 1 100
? 1 60
? 61 100
? 61 84
? 61 74
? 61 68
? 69 74
? 69 72
? 71 72
? 69 70
! 70
? 1 9
? 1 5
? 1 3
? 1 2
! 3
? 1 53
? 22 53
? 1 21
? 1 13
? 1 8
? 4 8
? 4 6
? 5 6
! 5
? 1 33
? 1 20
? 21 33
? 26 33
? 29 33
? 29 31
? 32 33
! 33
? 1 82
? 34 82
? 1 33
? 14 33
? 22 33
? 27 33
? 22 26
? 22 24
? 25 26
!...

result:

ok Correct (10000 test cases)

Test #6:

score: 0
Accepted
time: 136ms
memory: 3496kb

input:

10000
50
10
10
10
10
6
2
3
5
50
11
11
9
23
23
23
22
25
50
44
44
40
21
21
21
22
23
50
24
14
45
45
40
49
48
46
50
50
50
50
50
50
49
47
47
50
36
23
17
17
18
12
11
10
50
29
29
20
3
3
3
3
50
30
30
22
1
1
1
2
4
50
25
25
25
25
21
30
29
27
50
18
20
49
47
37
37
37
36
50
9
9
9
5
17
18
14
13
50
26
26
26
28
17
...

output:

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

result:

ok Correct (10000 test cases)

Test #7:

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

input:

10000
100
76
49
35
34
5
5
3
9
9
100
29
29
29
29
29
29
30
26
26
100
64
64
69
88
88
86
78
77
81
100
51
57
98
98
92
79
79
77
81
100
44
44
50
13
13
13
12
9
9
100
64
92
22
19
27
25
40
40
39
100
93
93
86
56
59
44
44
41
45
100
37
2
97
81
76
76
74
68
68
100
76
76
58
94
95
80
79
86
85
83
100
32
32
11
59
60
4...

output:

? 1 100
? 41 100
? 1 40
? 17 40
? 1 16
? 1 10
? 1 6
? 7 10
? 9 10
! 10
? 1 100
? 1 60
? 1 36
? 16 36
? 25 36
? 25 31
? 28 31
? 25 27
? 25 26
! 25
? 1 100
? 41 100
? 41 76
? 77 100
? 77 90
? 83 90
? 77 82
? 77 80
? 81 82
! 82
? 1 100
? 1 60
? 61 100
? 77 100
? 87 100
? 77 86
? 77 82
? 77 80
? 81 82
!...

result:

ok Correct (10000 test cases)

Test #8:

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

input:

1000
1000
475
426
728
747
896
896
896
867
841
841
841
844
847
847
1000
278
17
974
811
757
751
637
618
664
652
639
639
640
645
645
1000
75
128
871
985
607
644
713
732
749
749
742
735
737
741
741
1000
239
239
45
577
577
520
458
458
458
458
458
459
462
463
1000
978
978
978
978
978
978
997
944
950
932
9...

output:

? 1 1000
? 1 600
? 601 1000
? 601 840
? 841 1000
? 841 936
? 841 898
? 864 898
? 841 863
? 841 854
? 841 848
? 841 845
? 846 848
? 846 847
! 846
? 1 1000
? 1 600
? 601 1000
? 761 1000
? 601 760
? 665 760
? 601 664
? 601 638
? 639 664
? 650 664
? 639 649
? 639 645
? 639 642
? 643 645
? 644 645
! 644
...

result:

ok Correct (1000 test cases)

Test #9:

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

input:

1017
272
246
111
27
52
73
73
73
73
73
71
75
114
105
91
2
2
2
2
2
2
2
910
173
173
173
173
127
14
29
65
65
56
51
51
52
48
726
229
229
229
201
63
63
28
17
17
13
24
24
23
861
315
104
671
671
688
593
593
593
593
583
597
597
596
594
1984
133
133
133
406
571
512
704
704
701
673
658
650
650
650
649
647
1145...

output:

? 1 272
? 110 272
? 1 109
? 1 65
? 66 109
? 66 91
? 66 81
? 66 75
? 70 75
? 70 73
? 74 75
! 74
? 1 114
? 47 114
? 1 46
? 1 28
? 1 17
? 1 10
? 1 6
? 1 4
? 1 2
! 1
? 1 910
? 1 546
? 1 328
? 1 197
? 80 197
? 1 79
? 1 47
? 48 79
? 48 66
? 56 66
? 48 55
? 48 52
? 50 52
? 48 49
! 49
? 1 726
? 1 436
? 1 26...

result:

ok Correct (1017 test cases)

Test #10:

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

input:

10
100000
3893
3893
30673
43582
43582
43582
43582
43582
43582
43582
43582
43582
43470
43242
43242
43242
43245
43268
43268
43268
43267
43270
43269
100000
32066
54928
68197
71764
88585
88585
85554
93282
93282
93193
91599
91599
91599
91474
91415
91415
91410
91370
91365
91355
91355
91354
91351
91350
100...

output:

? 1 100000
? 1 60000
? 1 36000
? 36001 60000
? 36001 50400
? 36001 44640
? 39457 44640
? 41531 44640
? 42775 44640
? 42775 43894
? 43223 43894
? 43223 43625
? 43384 43625
? 43223 43383
? 43223 43319
? 43223 43280
? 43223 43257
? 43258 43280
? 43258 43271
? 43264 43271
? 43264 43268
? 43269 43271
? 4...

result:

ok Correct (10 test cases)

Test #11:

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

input:

21
84335
47947
47947
22445
9296
1509
19830
19830
19815
17079
17079
17079
17079
17084
17217
17221
17316
17316
17316
17308
17320
17320
17318
17323
159962
128177
145530
35270
7423
54814
49869
40850
40850
38954
42103
43214
43823
43823
43823
43765
43675
43675
43675
43675
43670
43689
43689
43687
43691
436...

output:

? 1 84335
? 1 50601
? 20242 50601
? 1 20241
? 1 12145
? 12146 20241
? 15385 20241
? 17328 20241
? 15385 17327
? 16162 17327
? 16629 17327
? 16909 17327
? 16909 17159
? 17160 17327
? 17160 17260
? 17261 17327
? 17288 17327
? 17304 17327
? 17304 17317
? 17318 17327
? 17318 17323
? 17318 17321
? 17322 ...

result:

ok Correct (21 test cases)

Test #12:

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

input:

1
1000000
641602
641602
418256
783270
783270
783270
783270
786055
805651
802269
794273
791414
797591
797591
797004
796734
796734
796734
796686
796850
796850
796844
796864
796864
796864
796864
796864
796865
796863

output:

? 1 1000000
? 400001 1000000
? 400001 760000
? 760001 1000000
? 760001 904000
? 760001 846400
? 760001 811840
? 760001 791104
? 791105 811840
? 799400 811840
? 791105 799399
? 791105 796081
? 796082 799399
? 796082 798072
? 796879 798072
? 796082 796878
? 796401 796878
? 796592 796878
? 796592 79676...

result:

ok Correct (1 test case)

Test #13:

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

input:

16
232936
229707
229707
229707
229707
229707
229707
229707
231039
223556
224031
225790
225790
225790
225915
225474
225474
225483
225375
225407
225417
225419
225431
225430
225425
225425
8676
6498
6498
6498
4978
3906
3959
4684
4684
4684
4684
4684
4684
4684
4676
4692
4692
4690
4693
221085
172303
209705...

output:

? 1 232936
? 93176 232936
? 149081 232936
? 182624 232936
? 202749 232936
? 214824 232936
? 222069 232936
? 226416 232936
? 222069 226415
? 222069 224676
? 224677 226415
? 225373 226415
? 225373 225998
? 225624 225998
? 225373 225623
? 225373 225523
? 225434 225523
? 225373 225433
? 225373 225409
? ...

result:

ok Correct (16 test cases)

Test #14:

score: 0
Accepted
time: 38ms
memory: 3600kb

input:

1994
667
666
667
267
266
107
106
43
42
17
16
7
6
3
2
374
373
374
150
149
60
59
24
23
10
9
4
3
2
488
486
488
195
194
78
77
31
30
13
12
5
4
2
922
921
922
369
368
148
147
59
58
24
23
10
9
4
3
2
639
637
639
256
255
103
102
41
40
17
16
7
6
3
2
353
350
353
141
140
57
56
23
22
9
8
4
3
2
71
66
71
29
28
12
1...

output:

? 1 667
? 268 667
? 1 267
? 108 267
? 1 107
? 44 107
? 1 43
? 18 43
? 1 17
? 8 17
? 1 7
? 4 7
? 1 3
? 2 3
! 1
? 1 374
? 151 374
? 1 150
? 61 150
? 1 60
? 25 60
? 1 24
? 11 24
? 1 10
? 5 10
? 1 4
? 3 4
? 1 2
! 1
? 1 488
? 196 488
? 1 195
? 79 195
? 1 78
? 32 78
? 1 31
? 14 31
? 1 13
? 6 13
? 1 5
? 3 ...

result:

ok Correct (1994 test cases)

Test #15:

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

input:

18
153667
153667
153666
61467
61466
24587
24586
9835
9834
3934
3933
1574
1573
630
629
252
251
101
100
41
40
17
16
7
6
3
2
211376
211374
211376
84551
84550
33821
33820
13529
13528
5412
5411
2165
2164
866
865
347
346
139
138
56
55
23
22
9
8
4
3
2
195330
195326
195330
78132
78131
31253
31252
12501
1250...

output:

? 1 153667
? 61468 153667
? 1 61467
? 24588 61467
? 1 24587
? 9836 24587
? 1 9835
? 3935 9835
? 1 3934
? 1575 3934
? 1 1574
? 631 1574
? 1 630
? 253 630
? 1 252
? 102 252
? 1 101
? 42 101
? 1 41
? 18 41
? 1 17
? 8 17
? 1 7
? 4 7
? 1 3
? 2 3
! 1
? 1 211376
? 84552 211376
? 1 84551
? 33822 84551
? 1 3...

result:

ok Correct (18 test cases)

Test #16:

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

input:

1
1000000
999998
1000000
400000
399999
160000
159999
64000
63999
25600
25599
10240
10239
4096
4095
1639
1638
656
655
263
262
105
104
42
41
17
16
7
6
3
2

output:

? 1 1000000
? 400001 1000000
? 1 400000
? 160001 400000
? 1 160000
? 64001 160000
? 1 64000
? 25601 64000
? 1 25600
? 10241 25600
? 1 10240
? 4097 10240
? 1 4096
? 1640 4096
? 1 1639
? 657 1639
? 1 656
? 264 656
? 1 263
? 106 263
? 1 105
? 43 105
? 1 42
? 18 42
? 1 17
? 8 17
? 1 7
? 4 7
? 1 3
? 2 3
...

result:

ok Correct (1 test case)

Test #17:

score: 0
Accepted
time: 37ms
memory: 3600kb

input:

1994
667
666
454
27
27
27
27
27
28
2
2
2
2
2
374
372
224
91
96
29
29
36
14
12
5
6
3
2
488
485
370
161
156
44
44
43
15
14
6
7
3
2
922
921
662
40
40
40
40
40
36
18
12
7
8
3
2
639
639
421
215
147
68
95
2
2
2
2
2
2
2
353
351
200
91
81
27
27
22
2
2
2
2
2
71
71
47
6
6
6
6
4
3
2
24
22
24
7
9
2
2
567
563
33...

output:

? 1 667
? 268 667
? 1 267
? 1 160
? 1 96
? 1 58
? 1 35
? 15 35
? 1 14
? 1 8
? 1 5
? 1 3
? 1 2
! 1
? 1 374
? 151 374
? 1 150
? 61 150
? 1 60
? 1 36
? 16 36
? 1 15
? 7 15
? 1 6
? 4 6
? 1 3
? 2 3
! 1
? 1 488
? 196 488
? 1 195
? 79 195
? 1 78
? 1 47
? 20 47
? 1 19
? 9 19
? 1 8
? 4 8
? 1 3
? 2 3
! 1
? 1 ...

result:

ok Correct (1994 test cases)

Test #18:

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

input:

18
153667
153667
65961
50668
47562
8350
8350
8350
5820
1644
1644
1499
306
306
306
198
24
24
24
24
16
11
7
3
3
2
211376
211375
91641
67652
80994
4235
4235
4235
4235
4235
3075
973
973
961
221
221
163
79
60
10
10
10
8
2
2
2
195330
195325
161600
36944
36944
36871
17928
10897
1018
1018
1018
1018
1568
281...

output:

? 1 153667
? 61468 153667
? 1 61467
? 24588 61467
? 1 24587
? 1 14752
? 1 8851
? 3542 8851
? 1 3541
? 1 2125
? 851 2125
? 1 850
? 1 510
? 1 306
? 124 306
? 1 123
? 1 74
? 1 44
? 1 26
? 12 26
? 1 11
? 6 11
? 1 5
? 1 3
? 2 3
! 1
? 1 211376
? 84552 211376
? 1 84551
? 33822 84551
? 1 33821
? 1 20293
? 1...

result:

ok Correct (18 test cases)

Test #19:

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

input:

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

output:

? 1 1000000
? 400001 1000000
? 1 400000
? 1 240000
? 96001 240000
? 1 96000
? 1 57600
? 1 34560
? 1 20736
? 1 12442
? 4978 12442
? 1 4977
? 1 2986
? 1 1792
? 718 1792
? 1 717
? 1 430
? 1 258
? 1 155
? 1 93
? 1 56
? 24 56
? 1 23
? 10 23
? 1 9
? 1 5
? 3 5
? 1 2
! 1

result:

ok Correct (1 test case)

Test #20:

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

input:

1
999999
260772
507886
955966
996647
730076
730076
751781
673047
681010
692862
692649
701051
701051
701051
701051
701051
701101
701488
701488
701453
701361
701361
701361
701361
701361
701359
701355
701356
701358

output:

? 1 999999
? 1 599999
? 600000 999999
? 760000 999999
? 600000 759999
? 664000 759999
? 702400 759999
? 664000 702399
? 664000 687039
? 687040 702399
? 687040 696255
? 696256 702399
? 698714 702399
? 700189 702399
? 700189 701515
? 700720 701515
? 700720 701197
? 701198 701515
? 701325 701515
? 7014...

result:

ok Correct (1 test case)

Test #21:

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

input:

1
999998
295598
295598
73514
537464
537464
537464
537464
537464
537464
537464
537464
537464
537464
536777
535510
535839
536275
536275
536275
536271
536229
536229
536219
536208
536209
536203
536202
536200

output:

? 1 999998
? 1 599999
? 1 359999
? 360000 599999
? 456000 599999
? 456000 542399
? 490560 542399
? 511296 542399
? 523738 542399
? 531203 542399
? 531203 537920
? 533890 537920
? 535503 537920
? 536470 537920
? 535503 536469
? 535503 536082
? 536083 536469
? 536083 536314
? 536176 536314
? 536232 53...

result:

ok Correct (1 test case)

Test #22:

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

input:

1
999997
339297
339297
355318
489939
489939
489939
489939
473604
471212
468570
453304
453304
453304
453304
453304
453304
453467
453059
453059
453059
453067
453013
453013
453013
453010
453005
453006
453007

output:

? 1 999997
? 1 599998
? 1 359999
? 360000 599998
? 360000 503998
? 417600 503998
? 452160 503998
? 472896 503998
? 452160 472895
? 460455 472895
? 452160 460454
? 452160 457136
? 452160 455145
? 452160 453951
? 452877 453951
? 452877 453521
? 453135 453521
? 452877 453134
? 452980 453134
? 452980 45...

result:

ok Correct (1 test case)

Test #23:

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

input:

1
999996
578161
472988
665875
726172
958644
966123
888583
869149
865390
865390
865390
864247
859775
859775
859775
859913
858782
858873
859117
859184
859239
859239
859239
859239
859239
859239
859240
859237
859237

output:

? 1 999996
? 1 599998
? 599999 999996
? 599999 839997
? 839998 999996
? 903998 999996
? 839998 903997
? 865598 903997
? 839998 865597
? 850238 865597
? 856382 865597
? 860069 865597
? 856382 860068
? 857857 860068
? 858742 860068
? 859273 860068
? 858742 859272
? 858742 859060
? 859061 859272
? 8590...

result:

ok Correct (1 test case)

Test #24:

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

input:

2
500000
114103
114103
98381
290103
281943
180208
207866
220637
220637
222630
224587
226042
227703
227371
226572
226254
226893
226893
226805
226739
226728
226770
226770
226761
226777
226777
226776
226774
500000
313297
313297
313297
285097
246160
266767
217669
217669
211604
228136
228136
227098
22604...

output:

? 1 500000
? 1 300000
? 1 180000
? 180001 300000
? 228001 300000
? 180001 228000
? 180001 208800
? 208801 228000
? 216481 228000
? 216481 223392
? 223393 228000
? 223393 226157
? 226158 228000
? 226895 228000
? 226158 226894
? 226158 226599
? 226600 226894
? 226718 226894
? 226789 226894
? 226718 22...

result:

ok Correct (2 test cases)

Test #25:

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

input:

2
499999
493493
493493
493493
493493
493493
493493
487773
471068
471825
466355
466355
466355
465991
467320
467320
467320
467320
467320
467320
467320
467310
467329
467330
467338
467339
467341
499999
101651
101651
101651
101651
98374
24247
24247
18123
9237
9237
8975
6574
6338
4671
4671
4669
4261
4261
...

output:

? 1 499999
? 200001 499999
? 320001 499999
? 392001 499999
? 435201 499999
? 461121 499999
? 476673 499999
? 461121 476672
? 467342 476672
? 461121 467341
? 463610 467341
? 465103 467341
? 465103 466445
? 466446 467341
? 466805 467341
? 467020 467341
? 467149 467341
? 467226 467341
? 467273 467341
?...

result:

ok Correct (2 test cases)

Test #26:

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

input:

2
499998
367462
261014
193038
152483
53076
53076
53076
49244
37492
37153
42856
42864
39670
39405
40342
40342
40342
40342
40342
40331
40280
40275
40296
40296
40293
40290
40289
40291
499998
122343
122343
3768
201785
209196
278240
278240
279535
252131
252131
252131
252131
252131
252079
253046
253040
25...

output:

? 1 499998
? 200000 499998
? 1 199999
? 80001 199999
? 1 80000
? 32001 80000
? 32001 60800
? 43521 60800
? 32001 43520
? 32001 38912
? 38913 43520
? 40756 43520
? 38913 40755
? 38913 40018
? 40019 40755
? 40019 40460
? 40196 40460
? 40196 40354
? 40260 40354
? 40298 40354
? 40260 40297
? 40260 40282...

result:

ok Correct (2 test cases)

Test #27:

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

input:

2
499997
274071
274071
274071
195007
167121
159831
135636
135636
135636
135636
133612
132171
131482
133080
133080
132896
132679
132594
132781
132781
132768
132735
132735
132737
132743
132745
132746
499997
242708
242708
242708
248273
160791
143467
177106
177106
172524
164685
164685
164685
164685
1641...

output:

? 1 499997
? 1 299998
? 120000 299998
? 192000 299998
? 120000 191999
? 148800 191999
? 120000 148799
? 120000 137279
? 126912 137279
? 131059 137279
? 133548 137279
? 131059 133547
? 131059 132551
? 132552 133547
? 132552 133149
? 132791 133149
? 132552 132790
? 132552 132694
? 132695 132790
? 1327...

result:

ok Correct (2 test cases)

Test #28:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #29:

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

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: 55ms
memory: 3532kb

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

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: 54ms
memory: 3540kb

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: 55ms
memory: 3608kb

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: 90ms
memory: 3692kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #35:

score: 0
Accepted
time: 99ms
memory: 3532kb

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: 91ms
memory: 3540kb

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: 57ms
memory: 3672kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #38:

score: 0
Accepted
time: 76ms
memory: 3568kb

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: 60ms
memory: 3632kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #40:

score: 0
Accepted
time: 69ms
memory: 3568kb

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: 60ms
memory: 3608kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #42:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #43:

score: 0
Accepted
time: 55ms
memory: 3568kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #44:

score: 0
Accepted
time: 111ms
memory: 3516kb

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: 62ms
memory: 3616kb

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #47:

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

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 20:44:25 | OpenSource Project