QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557828#8939. PermutationsynonymAC ✓146ms3732kbC++171.5kb2024-09-11 11:34:202024-09-11 11:34:21

Judging History

This is the latest submission verdict.

  • [2024-09-11 11:34:21]
  • Judged
  • Verdict: AC
  • Time: 146ms
  • Memory: 3732kb
Show
  • [2024-09-11 11:34:20]
  • Submitted

answer

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define fnt long double
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

map<array<int,2>,int> answers;

int get_second(int l, int r) {
	if (answers.count({l,r})) {
		return answers[{l,r}];
	}
	cout<<"? "<<l<<" "<<r<<endl;
	int res; cin>>res;
	answers[{l,r}] = res;
	return res;
}

void output_answer(int k) {
	cout<<"! "<<k<<endl;
}

const fnt V = .618;
const fnt V1 = .5;

void solve() {
	int n; cin>>n;
	answers.clear();
	int l=1,r=n;
	int iter = 0;
	while (l != r) {
		assert(iter<100);
		iter++;
		int p = get_second(l,r);
		if (l+2==r) {
			if (p==l+1) {
				int pp = get_second(l,l+1);
				if (pp == p) {
					output_answer(l);
					return;
				} else {
					output_answer(r);
					return;
				}
			}
			if (p==l) {
				l++;
			} else {
				r--;
			}
			continue;
		}
		if (l+1==r) {
			output_answer(l+r-p);
			return;
		}
		
		int lrp, rrp;
		
		if (r-l+1 <= 8) {
			lrp = l+V1*(r-l+1);
			rrp = r-V1*(r-l);
		} else {
			lrp = l+V*(r-l+1);
			rrp = r-V*(r-l);
		}
		int p2 = -1;
		if (p <= lrp) {
			p2 = get_second(l,lrp);
			if (p2 == p) {
				r = lrp;
			} else {
				l = lrp+1;
			}
		} else {
			assert(p >= rrp);
			p2 = get_second(rrp,r);
			if (p2 == p) {
				l = rrp;
			} else {
				r = rrp-1;
			}
		}
	}
	output_answer(l);
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int t; cin>>t;
	while (t--) {
		solve();
	}
	
	return 0;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok Correct (3 test cases)

Test #2:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #3:

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

input:

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

output:

? 1 3
? 2 3
! 3
? 1 11
? 1 7
? 4 7
? 4 6
? 4 5
! 6
? 1 2
! 1
? 1 19
? 1 12
? 1 8
? 9 12
? 10 12
? 10 11
! 10
? 1 7
? 4 7
? 1 3
? 2 3
! 3
? 1 3
? 1 2
! 2
? 1 19
? 1 12
? 1 8
? 4 8
? 1 3
? 2 3
! 3
? 1 2
! 1
? 1 15
? 6 15
? 6 12
? 9 12
? 9 11
? 9 10
! 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: 96ms
memory: 3656kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #5:

score: 0
Accepted
time: 106ms
memory: 3712kb

input:

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

output:

? 1 100
? 1 62
? 63 100
? 77 100
? 63 76
? 63 71
? 66 71
? 68 71
? 69 71
? 69 70
! 70
? 1 9
? 1 6
? 1 4
? 1 3
? 1 2
! 3
? 1 53
? 20 53
? 1 19
? 1 12
? 1 8
? 4 8
? 4 6
? 4 5
! 5
? 1 33
? 1 21
? 22 33
? 26 33
? 29 33
? 29 31
? 32 33
! 33
? 1 82
? 31 82
? 1 30
? 12 30
? 18 30
? 22 30
? 25 30
? 27 30
? ...

result:

ok Correct (10000 test cases)

Test #6:

score: 0
Accepted
time: 110ms
memory: 3652kb

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
21
25
23
50
24
14
45
45
40
49
49
48
50
50
50
50
50
50
50
49
44
45
50
36
23
17
17
18
8
8
7
50
29
29
20
3
3
3
1
50
30
30
22
1
1
1
1
2
50
25
25
25
25
21
30
30
29
50
18
20
49
49
47
39
39
39
50
9
9
9
9
5
13
13
11
50
26
26
26
28
17
18
...

output:

? 1 50
? 1 31
? 1 20
? 1 13
? 5 13
? 1 4
? 1 3
! 4
? 1 50
? 1 31
? 1 20
? 21 31
? 24 31
? 27 31
? 24 26
? 24 25
! 24
? 1 50
? 19 50
? 30 50
? 19 29
? 19 25
? 19 22
? 23 25
? 23 24
! 24
? 1 50
? 1 31
? 32 50
? 38 50
? 38 46
? 47 50
? 47 49
? 47 48
! 47
? 1 50
? 19 50
? 30 50
? 37 50
? 41 50
? 44 50
?...

result:

ok Correct (10000 test cases)

Test #7:

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

input:

10000
100
76
49
35
34
5
3
11
11
11
100
29
29
29
29
29
29
29
30
24
23
100
64
64
38
88
88
88
88
86
84
83
100
51
57
98
98
92
79
81
84
83
100
44
44
50
13
13
13
12
6
7
100
64
64
64
62
41
41
41
41
40
100
93
93
86
56
56
59
49
50
47
100
37
2
97
81
76
76
74
68
67
100
76
76
58
94
95
80
79
83
82
100
32
32
11
5...

output:

? 1 100
? 38 100
? 1 37
? 14 37
? 1 13
? 1 9
? 10 13
? 10 12
? 10 11
! 10
? 1 100
? 1 62
? 1 39
? 15 39
? 15 30
? 20 30
? 23 30
? 26 30
? 23 25
? 23 24
! 25
? 1 100
? 38 100
? 38 76
? 77 100
? 77 91
? 82 91
? 82 88
? 85 88
? 82 84
? 82 83
! 82
? 1 100
? 1 62
? 63 100
? 77 100
? 85 100
? 77 84
? 77 8...

result:

ok Correct (10000 test cases)

Test #8:

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

input:

1000
1000
475
426
728
728
747
831
831
828
841
841
837
844
844
845
1000
278
17
974
811
757
751
637
637
628
652
647
641
642
1000
75
128
871
985
644
686
713
713
712
732
735
742
742
741
1000
239
239
45
577
607
432
429
442
458
460
460
460
462
463
1000
978
978
978
978
978
978
997
914
914
920
923
923
923
9...

output:

? 1 1000
? 1 618
? 619 1000
? 619 855
? 619 765
? 766 855
? 799 855
? 799 834
? 835 855
? 835 847
? 835 843
? 844 847
? 844 846
? 845 846
! 846
? 1 1000
? 1 618
? 619 1000
? 764 1000
? 619 763
? 674 763
? 619 673
? 619 652
? 619 640
? 641 652
? 645 652
? 641 644
? 641 643
! 644
? 1 1000
? 1 618
? 61...

result:

ok Correct (1000 test cases)

Test #9:

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

input:

1017
272
246
111
27
52
73
73
73
73
73
73
71
114
105
91
2
2
2
2
2
2
2
2
910
173
173
173
173
127
14
14
29
35
37
51
51
51
50
726
229
229
229
201
63
63
63
44
28
28
28
28
27
861
315
104
671
671
688
593
593
593
593
593
593
593
590
594
1984
133
133
133
406
571
571
512
583
608
634
633
643
645
647
649
1145
9...

output:

? 1 272
? 104 272
? 1 103
? 1 64
? 65 103
? 65 89
? 65 80
? 65 74
? 68 74
? 71 74
? 71 73
! 74
? 1 114
? 44 114
? 1 43
? 1 27
? 1 17
? 1 11
? 1 7
? 1 4
? 1 3
? 1 2
! 1
? 1 910
? 1 563
? 1 348
? 1 216
? 83 216
? 1 82
? 1 51
? 1 32
? 33 51
? 33 44
? 45 51
? 48 51
? 49 51
? 49 50
! 49
? 1 726
? 1 449
?...

result:

ok Correct (1017 test cases)

Test #10:

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

input:

10
100000
3893
3893
30673
43582
43582
43582
43582
43582
43582
43582
43582
43582
43470
43385
43446
43289
43289
43289
43279
43268
43263
43270
43269
100000
32066
54928
68197
71764
88585
88585
85554
93282
94213
91599
91599
91599
91599
91474
91410
91410
91398
91339
91339
91337
91348
91349
91353
100000
50...

output:

? 1 100000
? 1 61800
? 1 38193
? 38194 61800
? 38194 52783
? 38194 47210
? 38194 43766
? 40322 43766
? 41637 43766
? 42450 43766
? 42952 43766
? 43262 43766
? 43454 43766
? 43262 43453
? 43334 43453
? 43262 43333
? 43262 43306
? 43262 43289
? 43272 43289
? 43262 43271
? 43262 43268
? 43269 43271
? 4...

result:

ok Correct (10 test cases)

Test #11:

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

input:

21
84335
47947
47947
22445
9296
1509
19830
19830
19830
19815
17079
17079
17079
17084
17352
17352
17352
17346
17316
17308
17320
17320
17321
17323
159962
128177
145530
35270
7423
54814
49869
40850
38954
43550
43550
43550
43550
43550
43489
43765
43765
43753
43675
43670
43695
43695
43695
43695
43695
436...

output:

? 1 84335
? 1 52120
? 19910 52120
? 1 19909
? 1 12304
? 12305 19909
? 15209 19909
? 17004 19909
? 18113 19909
? 17004 18112
? 17004 17689
? 17004 17427
? 17004 17266
? 17267 17427
? 17267 17366
? 17304 17366
? 17327 17366
? 17304 17326
? 17304 17318
? 17319 17326
? 17319 17323
? 17319 17321
? 17322 ...

result:

ok Correct (21 test cases)

Test #12:

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

input:

1
1000000
641602
641602
418256
783270
783270
783270
783270
783270
778242
786055
785504
794273
794682
797591
797591
797004
796734
796734
796788
796850
796790
796864
796864
796864
796864
796864
796864
796864
796863

output:

? 1 1000000
? 382000 1000000
? 382000 763924
? 763925 1000000
? 763925 909819
? 763925 854088
? 763925 819646
? 763925 798361
? 763925 785207
? 785208 798361
? 785208 793337
? 793338 798361
? 793338 796442
? 796443 798361
? 796443 797628
? 796895 797628
? 796443 796894
? 796615 796894
? 796615 79678...

result:

ok Correct (1 test case)

Test #13:

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

input:

16
232936
229707
229707
229707
229707
229707
229707
229707
229707
229707
227478
225790
225790
225790
225790
225611
225474
225483
225375
225395
225407
225409
225417
225419
225423
225422
8676
6498
6498
6498
6498
5867
4978
4978
5022
4731
4731
4731
4731
4717
4692
4692
4692
4692
4691
221085
172303
209705...

output:

? 1 232936
? 88982 232936
? 143972 232936
? 177956 232936
? 198958 232936
? 211937 232936
? 219958 232936
? 224915 232936
? 224915 229872
? 226808 229872
? 224915 226807
? 224915 226084
? 225361 226084
? 225361 225808
? 225531 225808
? 225361 225530
? 225425 225530
? 225361 225424
? 225361 225400
? ...

result:

ok Correct (16 test cases)

Test #14:

score: 0
Accepted
time: 34ms
memory: 3720kb

input:

1994
667
666
667
254
253
96
95
36
35
13
12
4
3
374
373
374
142
141
53
52
19
18
6
5
2
488
486
488
186
185
70
69
26
25
9
8
3
2
922
921
922
351
350
133
132
50
49
18
17
6
5
2
639
637
639
243
242
92
91
34
33
12
11
4
3
353
350
353
134
133
50
49
18
17
6
5
2
71
66
71
26
25
9
8
3
2
24
21
24
8
7
3
2
567
562
5...

output:

? 1 667
? 255 667
? 1 254
? 97 254
? 1 96
? 37 96
? 1 36
? 14 36
? 1 13
? 5 13
? 1 4
? 2 4
! 1
? 1 374
? 143 374
? 1 142
? 54 142
? 1 53
? 20 53
? 1 19
? 7 19
? 1 6
? 3 6
? 1 2
! 1
? 1 488
? 187 488
? 1 186
? 71 186
? 1 70
? 27 70
? 1 26
? 10 26
? 1 9
? 4 9
? 1 3
? 1 2
! 1
? 1 922
? 352 922
? 1 351
...

result:

ok Correct (1994 test cases)

Test #15:

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

input:

18
153667
153667
153666
58700
58699
22423
22422
8565
8564
3271
3270
1249
1248
476
475
181
180
68
67
25
24
9
8
3
2
211376
211374
211376
80745
80744
30844
30843
11782
11781
4500
4499
1718
1717
655
654
249
248
94
93
35
34
12
11
4
3
195330
195326
195330
74615
74614
28502
28501
10887
10886
4158
4157
1587...

output:

? 1 153667
? 58701 153667
? 1 58700
? 22424 58700
? 1 22423
? 8566 22423
? 1 8565
? 3272 8565
? 1 3271
? 1250 3271
? 1 1249
? 477 1249
? 1 476
? 182 476
? 1 181
? 69 181
? 1 68
? 26 68
? 1 25
? 10 25
? 1 9
? 4 9
? 1 3
? 1 2
! 1
? 1 211376
? 80746 211376
? 1 80745
? 30845 80745
? 1 30844
? 11783 3084...

result:

ok Correct (18 test cases)

Test #16:

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

input:

1
1000000
999998
1000000
381999
381998
145923
145922
55742
55741
21293
21292
8133
8132
3106
3105
1186
1185
452
451
172
171
65
64
24
23
8
7
3
2

output:

? 1 1000000
? 382000 1000000
? 1 381999
? 145924 381999
? 1 145923
? 55743 145923
? 1 55742
? 21294 55742
? 1 21293
? 8134 21293
? 1 8133
? 3107 8133
? 1 3106
? 1187 3106
? 1 1186
? 453 1186
? 1 452
? 173 452
? 1 172
? 66 172
? 1 65
? 25 65
? 1 24
? 9 24
? 1 8
? 4 8
? 1 3
? 1 2
! 1

result:

ok Correct (1 test case)

Test #17:

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

input:

1994
667
666
454
27
27
27
27
27
28
2
2
2
2
2
2
374
372
224
91
96
29
29
16
12
8
3
3
2
488
485
370
161
156
44
44
43
15
14
3
3
2
922
921
662
40
40
40
40
40
51
18
12
3
3
3
2
639
639
421
215
147
68
72
2
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
4
2
2
567
563
332...

output:

? 1 667
? 255 667
? 1 254
? 1 157
? 1 98
? 1 61
? 1 38
? 15 38
? 1 14
? 1 9
? 1 6
? 1 4
? 1 3
? 1 2
! 1
? 1 374
? 143 374
? 1 142
? 54 142
? 1 53
? 1 33
? 13 33
? 1 12
? 5 12
? 1 4
? 1 3
? 1 2
! 1
? 1 488
? 187 488
? 1 186
? 71 186
? 1 70
? 1 44
? 17 44
? 1 16
? 6 16
? 1 5
? 1 3
? 1 2
! 1
? 1 922
? ...

result:

ok Correct (1994 test cases)

Test #18:

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

input:

18
153667
153667
65961
50668
47562
8350
8350
8350
5820
1644
1644
1499
306
306
477
24
24
24
24
24
16
7
7
5
3
2
211376
211375
91641
67652
36438
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
1568
281
281...

output:

? 1 153667
? 58701 153667
? 1 58700
? 22424 58700
? 1 22423
? 1 13858
? 1 8565
? 3272 8565
? 1 3271
? 1 2022
? 773 2022
? 1 772
? 1 478
? 183 478
? 1 182
? 1 113
? 1 70
? 1 44
? 1 28
? 11 28
? 1 10
? 1 7
? 4 7
? 1 3
? 1 2
! 1
? 1 211376
? 80746 211376
? 1 80745
? 30845 80745
? 1 30844
? 1 19062
? 1 ...

result:

ok Correct (18 test cases)

Test #19:

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

input:

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

output:

? 1 1000000
? 382000 1000000
? 1 381999
? 1 236076
? 90181 236076
? 1 90180
? 1 55732
? 1 34443
? 1 21286
? 1 13155
? 1 8130
? 3106 8130
? 1 3105
? 1 1919
? 733 1919
? 1 732
? 1 453
? 1 280
? 1 174
? 1 108
? 1 67
? 1 42
? 16 42
? 1 15
? 6 15
? 1 5
? 3 5
? 1 2
! 1

result:

ok Correct (1 test case)

Test #20:

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

input:

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

output:

? 1 999999
? 1 618000
? 618001 999999
? 763924 999999
? 618001 763923
? 673743 763923
? 708191 763923
? 673743 708190
? 686901 708190
? 695033 708190
? 700058 708190
? 703164 708190
? 700058 703163
? 700058 701977
? 700058 701244
? 701245 701977
? 701524 701977
? 701245 701523
? 701351 701523
? 7014...

result:

ok Correct (1 test case)

Test #21:

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

input:

1
999998
295598
295598
73514
537464
537464
537464
537464
537464
537464
537464
537464
537464
537464
537464
536777
536636
536275
536097
536002
536162
536156
536229
536219
536208
536209
536201
536201
536200

output:

? 1 999998
? 1 617999
? 1 381924
? 381925 617999
? 472105 617999
? 472105 562268
? 506547 562268
? 506547 540983
? 519701 540983
? 527830 540983
? 532854 540983
? 532854 537878
? 534773 537878
? 535959 537878
? 536692 537878
? 535959 536691
? 536238 536691
? 535959 536237
? 535959 536131
? 536132 53...

result:

ok Correct (1 test case)

Test #22:

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

input:

1
999997
339297
339297
355318
613666
489939
413343
417456
471212
471212
468570
453304
453304
453304
453304
453304
453304
453059
452873
452842
452945
452950
453013
453013
453013
453013
453013
453010
453007
453006

output:

? 1 999997
? 1 617999
? 1 381924
? 381925 617999
? 472105 617999
? 381925 472104
? 381925 437656
? 437657 472104
? 450815 472104
? 458947 472104
? 450815 458946
? 450815 455840
? 450815 453921
? 452001 453921
? 452734 453921
? 452734 453468
? 453014 453468
? 452734 453013
? 452734 452907
? 452908 45...

result:

ok Correct (1 test case)

Test #23:

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

input:

1
999996
578161
472988
665875
726172
958644
966123
888583
907890
865390
865390
865390
864247
859775
859775
859775
859775
859584
859300
859300
859300
859303
859239
859239
859239
859239
859239
859239
859237
859235

output:

? 1 999996
? 1 617998
? 617999 999996
? 617999 854073
? 854074 999996
? 909816 999996
? 854074 909815
? 875367 909815
? 854074 875366
? 854074 867233
? 859100 867233
? 862206 867233
? 859100 862205
? 859100 861019
? 859100 860286
? 859100 859833
? 859380 859833
? 859100 859379
? 859206 859379
? 8592...

result:

ok Correct (1 test case)

Test #24:

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

input:

2
500000
114103
114103
98381
290103
281943
220637
220637
222630
226042
226042
226042
226042
226042
226074
226572
226450
226893
226930
226739
226739
226759
226770
226770
226770
226769
226777
226776
500000
313297
313297
313297
285097
246160
246160
246160
238712
228136
228136
229362
223239
223495
22511...

output:

? 1 500000
? 1 309000
? 1 190962
? 190963 309000
? 236053 309000
? 190963 236052
? 208186 236052
? 208186 225407
? 225408 236052
? 225408 231986
? 225408 229473
? 225408 227920
? 225408 226961
? 225408 226368
? 226369 226961
? 226369 226735
? 226736 226961
? 226821 226961
? 226736 226820
? 226736 22...

result:

ok Correct (2 test cases)

Test #25:

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

input:

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

output:

? 1 499999
? 191000 499999
? 309037 499999
? 381984 499999
? 427065 499999
? 454925 499999
? 472143 499999
? 454925 472142
? 461501 472142
? 465565 472142
? 468077 472142
? 465565 468076
? 465565 467117
? 467118 468076
? 467118 467710
? 467118 467484
? 467118 467344
? 467204 467344
? 467257 467344
?...

result:

ok Correct (2 test cases)

Test #26:

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

input:

2
499998
367462
193038
152483
183238
53076
53076
53076
53076
49244
42856
42864
39670
39405
40342
40342
40342
40342
40342
40342
40331
40280
40275
40285
40284
40290
40289
499998
122343
122343
3768
201785
201785
209196
246144
244788
259205
259205
258709
254417
254417
254748
253733
253610
253302
253389
...

output:

? 1 499998
? 190999 499998
? 1 190998
? 72961 190998
? 1 72960
? 27871 72960
? 27871 55736
? 38515 55736
? 45093 55736
? 38515 45092
? 41027 45092
? 38515 41026
? 38515 40067
? 40068 41026
? 40068 40660
? 40068 40434
? 40207 40434
? 40207 40347
? 40260 40347
? 40293 40347
? 40260 40292
? 40260 40280...

result:

ok Correct (2 test cases)

Test #27:

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

input:

2
499997
274071
274071
274071
302688
167121
159831
135636
135636
135636
135636
135636
136187
133612
133612
133655
133080
132896
132781
132781
132781
132768
132750
132750
132750
132750
132750
132748
499997
242708
242708
242708
248273
160791
143467
177106
177106
172524
164685
164685
164685
164155
1635...

output:

? 1 499997
? 1 308999
? 118038 308999
? 190985 308999
? 118038 190984
? 145903 190984
? 118038 145902
? 128682 145902
? 128682 139324
? 132747 139324
? 132747 136812
? 134299 136812
? 132747 134298
? 132747 133706
? 133113 133706
? 132747 133112
? 132886 133112
? 132747 132885
? 132747 132832
? 1327...

result:

ok Correct (2 test cases)

Test #28:

score: 0
Accepted
time: 52ms
memory: 3648kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #29:

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

input:

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

output:

? 1 8
? 1 5
? 6 8
? 7 8
! 8
? 1 8
? 1 5
? 6 8
? 7 8
! 7
? 1 8
? 1 5
? 6 8
? 6 7
! 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
? 6 7
! 7
? 1 8
? 1 5
? 6 8
? 7 8
! 8
? 1 8
? 1 5
? 6 8
? 7 8
! 7
? 1 8
? 1 5
? 6 8
? 6 7
! 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: 52ms
memory: 3592kb

input:

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

result:

ok Correct (10000 test cases)

Test #31:

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

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
? 6 7
! 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: 70ms
memory: 3656kb

input:

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

output:

? 1 8
? 1 5
? 6 8
? 7 8
! 8
? 1 8
? 1 5
? 6 8
? 7 8
! 7
? 1 8
? 1 5
? 6 8
? 6 7
! 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
? 6 7
! 7
? 1 8
? 1 5
? 6 8
? 7 8
! 8
? 1 8
? 1 5
? 6 8
? 7 8
! 7
? 1 8
? 1 5
? 6 8
? 6 7
! 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: 46ms
memory: 3600kb

input:

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

result:

ok Correct (10000 test cases)

Test #34:

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

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
? 7 8
! 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: 65ms
memory: 3712kb

input:

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

output:

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

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

input:

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

output:

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

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #39:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #40:

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

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
? 7 8
! 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: 41ms
memory: 3712kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #42:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #43:

score: 0
Accepted
time: 50ms
memory: 3552kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #44:

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

input:

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

output:

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

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

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

result:

ok Correct (10000 test cases)

Test #46:

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

input:

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

output:

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

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Extra Test:

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

Server Time: 2025-02-08 17:44:49 | OpenSource Project