QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#637802#8939. Permutationucup-team173#AC ✓139ms4024kbC++201.4kb2024-10-13 14:07:462024-10-13 14:07:46

Judging History

This is the latest submission verdict.

  • [2024-10-13 14:07:46]
  • Judged
  • Verdict: AC
  • Time: 139ms
  • Memory: 4024kb
Show
  • [2024-10-13 14:07:46]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using db = double;

constexpr db k = 0.613512;
constexpr int dbg = 0;

mt19937_64 rng(time(0));

void solve() {
    int n;
    cin >> n;
    auto ask = [&](int l, int r) {
        cout << "? " << l << ' ' << r << endl;
        int res;
        cin >> res;
        return res;
    };
    auto dfs = [&](auto self, int l, int r, int p) {
        if(l == r) {
            cout << "! " << l << endl;
            return;
        } else if(r == l + 1) {
            if(p == l) l++;
            cout << "! " << l << endl;
            return;
        }
        int len = r - l + 1;
        int lenk = len * k;
        if(lenk == 1) lenk++;
        int res;
        if(p <= l + lenk - 1) {
            res = ask(l, l + lenk - 1);
            if(res == p) self(self, l, l + lenk - 1, p);
            else self(self, l + lenk, r, l + lenk == r ? 0 : ask(l + lenk, r));
        } else {
            res = ask(r - lenk + 1, r);
            if(res == p) self(self, r - lenk + 1, r, p);
            else self(self, l, r - lenk, l == r - lenk ? 0 : ask(l, r - lenk));
        }
    };
    dfs(dfs, 1, n, ask(1, n));
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cerr << 1. / (pow(2, -2. / 3) + 1) << '\n';
    int t = 1;
    cin >> t;
    while(t--) 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: 3968kb

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

input:

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

output:

? 1 10
? 1 6
? 1 3
? 4 6
? 4 5
! 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
? 4 6
? 1 3
? 1 2
! 3
? 1 10
? 5 10
? 1 4
? 3 4
? 1 2
! 1
? 1 10
? 1 6
? 1 3
? 2 3
! 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: 49ms
memory: 3980kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #4:

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

input:

10000
47
23
23
24
11
9
2
1
5
14
8
2
9
9
9
25
6
6
4
13
13
13
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
18
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
35
38
19
17
17
16
9
9
10
21
14
14
14
15
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 11
? 9 10
! 10
? 1 25
? 1 15
? 1 9
? 10 15
? 13 15
? 13 14
! 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 12
? 1 7
? 4 7
? 6 7
? 4 5
...

result:

ok Correct (10000 test cases)

Test #5:

score: 0
Accepted
time: 61ms
memory: 3844kb

input:

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

output:

? 1 100
? 1 61
? 62 100
? 78 100
? 62 77
? 69 77
? 69 73
? 69 71
? 70 71
! 70
? 1 9
? 1 5
? 1 3
? 1 2
! 3
? 1 53
? 22 53
? 1 21
? 1 12
? 1 7
? 4 7
? 6 7
? 4 5
! 5
? 1 33
? 1 20
? 21 33
? 27 33
? 30 33
? 30 31
? 32 33
! 33
? 1 82
? 33 82
? 1 32
? 14 32
? 22 32
? 27 32
? 22 26
? 22 24
? 25 26
! 25
? 1...

result:

ok Correct (10000 test cases)

Test #6:

score: 0
Accepted
time: 95ms
memory: 3920kb

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
30
29
50
18
20
49
47
37
37
37
50
9
9
9
5
17
18
14
13
50
26
26
26
28
17
19
...

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: 139ms
memory: 3904kb

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
86
78
77
80
81
100
51
57
98
98
92
79
79
78
81
100
44
44
50
13
13
13
12
9
10
7
100
64
92
22
19
27
25
33
35
39
39
100
93
93
86
56
59
40
44
49
48
47
100
37
2
97
81
76
76
77
70
70
100
76
76
58
94
95
80
79
86
85
83
100
3...

output:

? 1 100
? 40 100
? 1 39
? 17 39
? 1 16
? 1 9
? 10 16
? 10 13
? 10 11
! 10
? 1 100
? 1 61
? 1 37
? 16 37
? 25 37
? 25 31
? 28 31
? 25 27
? 25 26
! 25
? 1 100
? 40 100
? 40 76
? 77 100
? 77 90
? 83 90
? 77 82
? 77 79
? 80 82
? 80 81
! 82
? 1 100
? 1 61
? 62 100
? 78 100
? 87 100
? 78 86
? 78 82
? 78 8...

result:

ok Correct (10000 test cases)

Test #8:

score: 0
Accepted
time: 11ms
memory: 3924kb

input:

1000
1000
475
426
728
728
747
831
831
831
828
841
837
847
847
847
1000
278
17
974
811
757
751
637
637
637
628
640
640
641
643
1000
75
128
871
985
644
686
713
713
712
732
730
735
737
739
738
1000
239
239
45
577
607
432
429
442
434
458
459
463
463
463
1000
978
978
978
978
978
978
997
944
932
920
921
9...

output:

? 1 1000
? 1 613
? 614 1000
? 614 850
? 614 758
? 759 850
? 795 850
? 817 850
? 817 836
? 837 850
? 837 844
? 845 850
? 845 847
? 846 847
! 846
? 1 1000
? 1 613
? 614 1000
? 764 1000
? 614 763
? 672 763
? 614 671
? 614 648
? 628 648
? 628 639
? 640 648
? 640 644
? 640 642
? 643 644
! 644
? 1 1000
? ...

result:

ok Correct (1000 test cases)

Test #9:

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

input:

1017
272
246
111
27
52
73
73
73
73
73
73
72
114
105
91
2
2
2
2
2
2
2
910
173
173
173
173
127
14
14
29
35
37
44
42
48
48
726
229
229
229
201
63
63
28
17
17
13
24
24
24
861
315
104
671
671
688
593
593
593
593
593
593
593
594
1984
133
133
133
406
571
512
724
704
673
674
650
650
650
652
647
647
1145
988...

output:

? 1 272
? 107 272
? 1 106
? 1 65
? 66 106
? 66 90
? 66 80
? 66 74
? 70 74
? 72 74
? 72 73
! 74
? 1 114
? 46 114
? 1 45
? 1 27
? 1 16
? 1 9
? 1 5
? 1 3
? 1 2
! 1
? 1 910
? 1 558
? 1 342
? 1 209
? 82 209
? 1 81
? 1 49
? 1 30
? 31 49
? 31 41
? 42 49
? 42 45
? 46 49
? 48 49
! 49
? 1 726
? 1 445
? 1 273
...

result:

ok Correct (1017 test cases)

Test #10:

score: 0
Accepted
time: 2ms
memory: 3924kb

input:

10
100000
3893
3893
30673
43582
43582
43582
43582
43582
43582
43582
43582
43582
43470
43242
43242
43197
43268
43245
43279
43279
43278
43273
43273
43272
100000
32066
54928
68197
71764
88585
88585
85554
93282
94213
91599
91599
91599
91474
91257
91225
91410
91398
91339
91339
91337
91348
91349
91354
913...

output:

? 1 100000
? 1 61351
? 1 37639
? 37640 61351
? 37640 52186
? 37640 46563
? 41090 46563
? 41090 44447
? 42388 44447
? 42388 43650
? 42877 43650
? 43177 43650
? 43361 43650
? 43177 43360
? 43177 43288
? 43177 43244
? 43245 43288
? 43245 43270
? 43271 43288
? 43271 43281
? 43276 43281
? 43271 43275
? 4...

result:

ok Correct (10 test cases)

Test #11:

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

input:

21
84335
47947
47947
22445
9296
1509
19830
19830
19830
19815
17510
17510
17510
17510
17496
17352
17352
17352
17346
17320
17320
17318
17323
17323
159962
128177
145530
35270
7423
54814
49869
40850
38954
46872
46914
43823
43823
43823
43823
43765
43675
43675
43670
43695
43695
43695
43695
43695
43694
192...

output:

? 1 84335
? 1 51740
? 19998 51740
? 1 19997
? 1 12268
? 12269 19997
? 15257 19997
? 17090 19997
? 18214 19997
? 17090 18213
? 17090 17778
? 17090 17511
? 17254 17511
? 17354 17511
? 17254 17353
? 17293 17353
? 17317 17353
? 17332 17353
? 17317 17331
? 17317 17325
? 17317 17321
? 17322 17325
? 17322 ...

result:

ok Correct (21 test cases)

Test #12:

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

input:

1
1000000
641602
641602
418256
783270
783270
783270
783270
786055
805651
805651
802269
797591
797591
797591
797591
797004
796734
796559
796850
796788
796864
796864
796864
796864
796864
796864
796865
796861

output:

? 1 1000000
? 386489 1000000
? 386489 762884
? 762885 1000000
? 762885 908357
? 762885 852133
? 762885 817639
? 762885 796476
? 796477 817639
? 796477 809459
? 801495 809459
? 796477 801494
? 796477 799554
? 796477 798364
? 796477 797634
? 796925 797634
? 796477 796924
? 796477 796750
? 796751 79692...

result:

ok Correct (1 test case)

Test #13:

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

input:

16
232936
229707
229707
229707
229707
229707
229707
229707
229707
229707
227478
225790
225790
225790
225915
225474
225474
225474
225474
225466
225438
225431
225419
225419
225421
225423
225422
8676
6498
6498
6498
6498
5867
4978
4978
5022
4731
4731
4731
4717
4715
4705
4692
4692
4692
4693
221085
172303...

output:

? 1 232936
? 90028 232936
? 145261 232936
? 179147 232936
? 199937 232936
? 212692 232936
? 220517 232936
? 225318 232936
? 225318 229991
? 227125 229991
? 225318 227124
? 225318 226425
? 225318 225996
? 225581 225996
? 225318 225580
? 225318 225478
? 225381 225478
? 225419 225478
? 225443 225478
? ...

result:

ok Correct (16 test cases)

Test #14:

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

input:

1994
667
666
667
258
257
100
99
39
38
16
15
7
6
3
2
374
373
374
145
144
57
56
23
22
9
8
4
3
2
488
486
488
189
188
74
73
29
28
12
11
5
4
2
922
921
922
357
356
138
137
54
53
21
20
9
8
4
3
2
639
637
639
247
246
96
95
38
37
15
14
6
5
3
2
353
350
353
137
136
53
52
21
20
9
8
4
3
2
71
66
71
28
27
11
10
5
4...

output:

? 1 667
? 259 667
? 1 258
? 101 258
? 1 100
? 40 100
? 1 39
? 17 39
? 1 16
? 8 16
? 1 7
? 4 7
? 1 3
? 2 3
! 1
? 1 374
? 146 374
? 1 145
? 58 145
? 1 57
? 24 57
? 1 23
? 10 23
? 1 9
? 5 9
? 1 4
? 3 4
? 1 2
! 1
? 1 488
? 190 488
? 1 189
? 75 189
? 1 74
? 30 74
? 1 29
? 13 29
? 1 12
? 6 12
? 1 5
? 3 5
...

result:

ok Correct (1994 test cases)

Test #15:

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

input:

18
153667
153667
153666
59391
59390
22954
22953
8872
8871
3429
3428
1326
1325
513
512
199
198
77
76
30
29
12
11
5
4
2
211376
211374
211376
81695
81694
31575
31574
12204
12203
4717
4716
1824
1823
705
704
273
272
106
105
41
40
16
15
7
6
3
2
195330
195326
195330
75493
75492
29178
29177
11277
11276
4359...

output:

? 1 153667
? 59392 153667
? 1 59391
? 22955 59391
? 1 22954
? 8873 22954
? 1 8872
? 3430 8872
? 1 3429
? 1327 3429
? 1 1326
? 514 1326
? 1 513
? 200 513
? 1 199
? 78 199
? 1 77
? 31 77
? 1 30
? 13 30
? 1 12
? 6 12
? 1 5
? 3 5
? 1 2
! 1
? 1 211376
? 81696 211376
? 1 81695
? 31576 81695
? 1 31575
? 12...

result:

ok Correct (18 test cases)

Test #16:

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

input:

1
1000000
999998
1000000
386488
386487
149373
149372
57731
57730
22313
22312
8624
8623
3334
3333
1289
1288
499
498
193
192
75
74
29
28
12
11
5
4
2

output:

? 1 1000000
? 386489 1000000
? 1 386488
? 149374 386488
? 1 149373
? 57732 149373
? 1 57731
? 22314 57731
? 1 22313
? 8625 22313
? 1 8624
? 3335 8624
? 1 3334
? 1290 3334
? 1 1289
? 500 1289
? 1 499
? 194 499
? 1 193
? 76 193
? 1 75
? 30 75
? 1 29
? 13 29
? 1 12
? 6 12
? 1 5
? 3 5
? 1 2
! 1

result:

ok Correct (1 test case)

Test #17:

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

input:

1994
667
666
454
27
27
27
27
27
28
2
2
2
2
374
372
224
91
96
29
29
16
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
4
2
639
639
421
215
147
68
95
2
2
2
2
2
2
353
351
200
91
81
27
27
22
2
2
2
2
71
71
47
6
6
6
6
4
3
2
24
22
24
7
9
2
2
567
563
332
20...

output:

? 1 667
? 259 667
? 1 258
? 1 158
? 1 96
? 1 58
? 1 35
? 15 35
? 1 14
? 1 8
? 1 4
? 1 2
! 1
? 1 374
? 146 374
? 1 145
? 58 145
? 1 57
? 1 34
? 15 34
? 1 14
? 7 14
? 1 6
? 4 6
? 1 3
? 2 3
! 1
? 1 488
? 190 488
? 1 189
? 75 189
? 1 74
? 1 45
? 19 45
? 1 18
? 8 18
? 1 7
? 4 7
? 1 3
? 2 3
! 1
? 1 922
? ...

result:

ok Correct (1994 test cases)

Test #18:

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

input:

18
153667
153667
65961
50668
47562
8350
8350
8350
5820
1644
1644
1499
306
306
477
24
24
24
24
24
16
7
9
3
4
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
17928
1018
1018
1018
1018
1018
1018
923
281
281
...

output:

? 1 153667
? 59392 153667
? 1 59391
? 22955 59391
? 1 22954
? 1 14082
? 1 8639
? 3340 8639
? 1 3339
? 1 2048
? 793 2048
? 1 792
? 1 485
? 189 485
? 1 188
? 1 115
? 1 70
? 1 42
? 1 25
? 11 25
? 1 10
? 5 10
? 1 4
? 3 4
? 1 2
! 1
? 1 211376
? 81696 211376
? 1 81695
? 31576 81695
? 1 31575
? 1 19371
? 1...

result:

ok Correct (18 test cases)

Test #19:

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

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
2

output:

? 1 1000000
? 386489 1000000
? 1 386488
? 1 237115
? 91644 237115
? 1 91643
? 1 56224
? 1 34494
? 1 21162
? 1 12983
? 5019 12983
? 1 5018
? 1 3078
? 1 1888
? 731 1888
? 1 730
? 1 447
? 1 274
? 1 168
? 1 103
? 1 63
? 26 63
? 1 25
? 11 25
? 1 10
? 1 6
? 4 6
? 1 3
? 1 2
! 1

result:

ok Correct (1 test case)

Test #20:

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

input:

1
999999
260772
507886
955966
996647
730076
730076
751781
706326
706326
706326
706326
705072
701051
701051
701051
700522
701488
701586
701202
701249
701361
701361
701361
701361
701361
701359
701355
701354
701356

output:

? 1 999999
? 1 613511
? 613512 999999
? 762885 999999
? 613512 762884
? 671243 762884
? 706662 762884
? 671243 706661
? 684933 706661
? 693331 706661
? 698484 706661
? 701645 706661
? 698484 701644
? 699706 701644
? 700456 701644
? 700456 701184
? 701185 701644
? 701363 701644
? 701185 701362
? 7011...

result:

ok Correct (1 test case)

Test #21:

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

input:

1
999998
295598
295598
73514
537464
537464
537464
537464
537464
537464
537464
537464
537464
537464
537464
536777
535839
535839
536002
536097
536052
536162
536156
536208
536208
536209
536197
536197
536198

output:

? 1 999998
? 1 613510
? 1 376395
? 376396 613510
? 468039 613510
? 468039 557286
? 502533 557286
? 523695 557286
? 523695 544303
? 531661 544303
? 531661 539416
? 534659 539416
? 534659 537577
? 535788 537577
? 536480 537577
? 535788 536479
? 535788 536211
? 535788 536047
? 536048 536211
? 536048 53...

result:

ok Correct (1 test case)

Test #22:

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

input:

1
999997
339297
339297
355318
489939
489939
489939
471212
453304
453304
453304
453304
453304
453304
453304
453304
453304
453304
453247
453059
453059
453067
453017
453017
453013
453005
453007
453010
453011
453009

output:

? 1 999997
? 1 613510
? 1 376395
? 376396 613510
? 376396 521867
? 432620 521867
? 467114 521867
? 432620 467113
? 432620 453781
? 440799 453781
? 445817 453781
? 448896 453781
? 450785 453781
? 451944 453781
? 452655 453781
? 452655 453345
? 452923 453345
? 453087 453345
? 452923 453086
? 452987 45...

result:

ok Correct (1 test case)

Test #23:

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

input:

1
999996
578161
472988
665875
726172
958644
966123
888583
907890
865390
859775
853100
853969
858027
858027
857481
858782
858873
859117
858976
859239
859239
859239
859239
859239
859239
859237
859235
859235

output:

? 1 999996
? 1 613509
? 613510 999996
? 613510 850623
? 850624 999996
? 908355 999996
? 850624 908354
? 872937 908354
? 850624 872936
? 859248 872936
? 850624 859247
? 850624 855913
? 855914 859247
? 857203 859247
? 857203 858456
? 858457 859247
? 858457 858941
? 858942 859247
? 858942 859128
? 8591...

result:

ok Correct (1 test case)

Test #24:

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

input:

2
500000
114103
114103
98381
290103
281943
220637
220637
207866
224587
224587
224587
223621
226042
226572
227012
227180
226739
226739
226739
226728
226759
226748
226770
226764
226777
226777
226776
500000
313297
313297
313297
285097
246160
246160
246160
238712
230101
228136
222822
223239
223884
22472...

output:

? 1 500000
? 1 306756
? 1 188198
? 188199 306756
? 234021 306756
? 188199 234020
? 205909 234020
? 205909 223155
? 223156 234020
? 223156 229820
? 223156 227244
? 223156 225663
? 225664 227244
? 225664 226632
? 226633 227244
? 226870 227244
? 226633 226869
? 226633 226777
? 226690 226777
? 226690 22...

result:

ok Correct (2 test cases)

Test #25:

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

input:

2
499999
493493
493493
493493
493493
493493
493493
487773
471068
471068
471068
471825
468187
468187
467811
467320
467320
467320
467320
467320
467329
467345
467345
467345
467345
467344
467342
467341
499999
101651
101651
101651
101651
98374
24247
24247
18123
9237
9237
8975
6574
6338
4671
4671
4669
426...

output:

? 1 499999
? 193245 499999
? 311803 499999
? 384539 499999
? 429164 499999
? 456542 499999
? 473338 499999
? 456542 473337
? 463034 473337
? 467017 473337
? 469460 473337
? 467017 469459
? 467017 468514
? 467596 468514
? 467017 467595
? 467017 467371
? 467155 467371
? 467239 467371
? 467291 467371
?...

result:

ok Correct (2 test cases)

Test #26:

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

input:

2
499998
367462
261014
193038
152483
53076
53076
53076
53076
49244
46002
42856
40342
40342
40342
40342
40342
40342
40342
40374
40253
40255
40280
40285
40296
40296
40294
40293
499998
122343
122343
3768
201785
201785
209196
246144
244788
252131
252131
252131
251090
253733
253733
253733
253733
253610
2...

output:

? 1 499998
? 193245 499998
? 1 193244
? 74688 193244
? 1 74687
? 28867 74687
? 28867 56977
? 39732 56977
? 46398 56977
? 39732 46397
? 42309 46397
? 39732 42308
? 39732 41312
? 39732 40700
? 40107 40700
? 40107 40470
? 40248 40470
? 40248 40383
? 40301 40383
? 40248 40300
? 40248 40279
? 40280 40300...

result:

ok Correct (2 test cases)

Test #27:

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

input:

2
499997
274071
274071
274071
302688
167121
159831
135636
135636
135636
135636
135636
133612
132171
132171
132002
132428
132543
132679
132661
132735
132725
132750
132750
132750
132748
132746
132745
499997
242708
242708
242708
248273
160791
143467
177106
177106
172524
164685
164685
164685
164685
1641...

output:

? 1 499997
? 1 306754
? 118558 306754
? 191294 306754
? 118558 191293
? 146670 191293
? 118558 146669
? 118558 135804
? 125224 135804
? 129314 135804
? 131823 135804
? 133362 135804
? 131823 133361
? 131823 132766
? 131823 132401
? 132402 132766
? 132402 132624
? 132625 132766
? 132625 132711
? 1327...

result:

ok Correct (2 test cases)

Test #28:

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

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: 89ms
memory: 3968kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #30:

score: 0
Accepted
time: 46ms
memory: 3984kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #31:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #32:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #33:

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

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: 44ms
memory: 3844kb

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

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: 48ms
memory: 3984kb

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: 52ms
memory: 3976kb

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

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: 69ms
memory: 3984kb

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: 64ms
memory: 3848kb

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: 40ms
memory: 4024kb

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: 59ms
memory: 3976kb

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: 56ms
memory: 3920kb

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: 43ms
memory: 3880kb

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: 56ms
memory: 3980kb

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

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: 52ms
memory: 3868kb

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-13 06:07:50 | OpenSource Project