QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#47413#2228. Bread PittovarischRE 116ms43888kbC++1.5kb2022-09-09 10:38:002022-09-09 10:38:02

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-09 10:38:02]
  • 评测
  • 测评结果:RE
  • 用时:116ms
  • 内存:43888kb
  • [2022-09-09 10:38:00]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>

using namespace std;
/* *
 *
 * Too many mind, no mind.
 *
 * */
const int maxn = 3e5 + 10;
int children[maxn], order[maxn], par[maxn], ans[maxn];
long long freq[maxn];
vector <int> tree[maxn];
void dfs(int u, int prev = 0) {
	for (int& v : tree[u]) {
		if (v == prev) continue;
		freq[v] = 1ll * freq[u] * (tree[u].size() - (prev != u));
		dfs(v, u);
	}
}
void dfs2(int u, int prev = 0, long long pos = 0) {
	if (pos > maxn) return;
	if (children[u] == 0) {
		long long i = pos;
		while (i < maxn) {
			ans[i] = u;
			i += freq[u];
		}
	}
	for (int& v : tree[u]) {
		if (v == prev) continue;
		long long newpos = pos + 1ll * order[v] * freq[u];
		dfs2(v, u, newpos);
	}
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n, q; cin >> n >> q;
	for (int i = 1; i < n; i++) {
		cin >> par[i];
		order[i] = children[par[i]];
		children[par[i]]++;
		tree[i].push_back(par[i]);
		tree[par[i]].push_back(i);
	}
	freq[0] = 1;
	dfs(0);
	dfs2(0);
	for (int i = 0; i < q; i++) cout << ans[i] << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 11784kb

input:

1 1


output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 6ms
memory: 11832kb

input:

2 2
0

output:

1
1

result:

ok 2 lines

Test #3:

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

input:

3 3
0 1

output:

2
2
2

result:

ok 3 lines

Test #4:

score: 0
Accepted
time: 6ms
memory: 11832kb

input:

4 4
0 1 1

output:

2
3
2
3

result:

ok 4 lines

Test #5:

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

input:

5 5
0 0 0 1

output:

4
2
3
4
2

result:

ok 5 lines

Test #6:

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

input:

6 6
0 1 2 3 3

output:

4
5
4
5
4
5

result:

ok 6 lines

Test #7:

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

input:

7 7
0 0 0 0 1 5

output:

6
2
3
4
6
2
3

result:

ok 7 lines

Test #8:

score: 0
Accepted
time: 6ms
memory: 11872kb

input:

8 8
0 1 0 2 0 2 6

output:

4
3
5
7
3
5
4
3

result:

ok 8 lines

Test #9:

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

input:

9 9
0 1 2 2 2 0 3 7

output:

8
6
4
6
5
6
8
6
4

result:

ok 9 lines

Test #10:

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

input:

10 10
0 0 1 2 4 3 5 7 5

output:

6
8
6
9
6
8
6
9
6
8

result:

ok 10 lines

Test #11:

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

input:

11 11
0 0 2 3 0 5 5 3 8 6

output:

1
4
10
1
9
7
1
4
10
1
9

result:

ok 11 lines

Test #12:

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

input:

12 12
0 0 2 0 1 3 6 4 6 6 9

output:

5
7
8
5
11
8
5
10
8
5
7
8

result:

ok 12 lines

Test #13:

score: 0
Accepted
time: 6ms
memory: 11780kb

input:

13 13
0 1 1 1 4 3 2 1 2 7 1 8

output:

10
6
5
12
11
9
6
5
12
11
10
6
5

result:

ok 13 lines

Test #14:

score: 0
Accepted
time: 6ms
memory: 11712kb

input:

14 14
0 0 1 0 1 2 4 0 6 1 3 7 10

output:

11
9
12
8
5
9
12
8
13
9
12
8
11
9

result:

ok 14 lines

Test #15:

score: 0
Accepted
time: 6ms
memory: 11856kb

input:

15 15
0 0 0 3 2 4 6 6 2 5 3 2 2 1

output:

14
10
7
14
9
11
14
12
8
14
13
11
14
10
7

result:

ok 15 lines

Test #16:

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

input:

16 16
0 1 2 1 2 4 1 5 2 6 0 9 10 6 14

output:

3
11
13
11
7
11
8
11
15
11
7
11
12
11
13
11

result:

ok 16 lines

Test #17:

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

input:

17 17
0 1 0 1 2 5 3 3 0 7 10 4 0 5 6 5

output:

15
11
9
13
12
8
9
13
14
11
9
13
12
8
9
13
16

result:

ok 17 lines

Test #18:

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

input:

18 18
0 1 2 0 3 3 4 5 3 9 9 0 1 3 10 5 15

output:

8
7
12
13
7
12
6
7
12
13
7
12
17
7
12
13
7
12

result:

ok 18 lines

Test #19:

score: 0
Accepted
time: 6ms
memory: 11824kb

input:

19 19
0 0 1 2 1 1 0 3 7 4 8 1 9 7 10 10 0 6

output:

11
15
13
17
5
16
14
17
18
15
13
17
12
16
14
17
11
15
13

result:

ok 19 lines

Test #20:

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

input:

20 20
0 1 2 3 1 5 1 3 7 2 9 5 1 9 2 2 4 8 8

output:

17
6
11
13
10
12
14
13
15
6
11
13
16
12
14
13
18
6
11
13

result:

ok 20 lines

Test #21:

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

input:

100 100
0 1 0 1 3 2 5 3 6 9 9 4 1 9 8 10 3 16 1 18 0 0 15 21 17 14 20 7 25 23 21 11 13 11 34 6 2 5 8 26 27 26 3 4 7 39 16 4 32 11 2 48 14 21 1 8 7 30 42 10 27 31 22 2 23 59 9 36 43 56 38 17 40 72 57 18 70 27 27 24 45 72 80 71 84 66 41 15 46 71 89 78 37 62 65 51 9 5 2

output:

87
28
83
63
12
58
94
63
33
29
54
63
19
69
83
63
55
85
94
63
93
91
54
63
44
74
83
63
33
69
94
63
19
98
54
63
55
77
83
63
96
29
94
63
52
69
54
63
33
81
83
63
19
88
94
63
55
82
54
63
64
69
83
63
12
90
94
63
33
91
54
63
19
29
83
63
55
69
94
63
99
98
54
63
44
77
83
63
33
74
94
63
19
69
54
63
55
75
83
63

result:

ok 100 lines

Test #22:

score: 0
Accepted
time: 7ms
memory: 11932kb

input:

1000 1000
0 1 0 1 3 2 2 6 2 4 0 10 12 10 12 0 5 15 10 19 0 21 1 4 22 23 12 12 1 12 20 30 30 3 27 13 28 3 16 1 19 37 30 24 17 5 42 23 14 34 13 0 17 40 54 12 52 14 32 52 56 60 17 9 10 32 4 24 23 8 65 2 2 70 65 17 18 69 7 52 10 58 70 23 29 7 5 42 8 10 68 59 79 17 50 5 90 6 91 61 39 30 81 96 97 82 32 56...

output:

74
855
869
554
851
845
563
685
792
36
543
604
893
294
598
597
685
792
118
271
771
990
800
80
552
685
792
691
647
869
683
661
353
597
685
792
815
323
604
951
717
874
632
685
792
231
608
771
570
800
376
597
685
792
643
559
869
966
463
600
563
685
792
319
833
604
683
294
221
597
685
792
137
327
771
554...

result:

ok 1000 lines

Test #23:

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

input:

10000 10000
0 1 2 3 1 0 3 7 3 5 1 7 8 1 4 10 2 2 10 14 14 20 22 20 17 20 13 20 0 6 3 18 32 17 33 8 8 14 8 17 10 17 13 4 19 29 9 14 9 45 22 51 31 50 52 19 52 31 37 32 37 53 18 14 28 24 7 64 32 33 53 42 56 16 44 4 35 65 64 79 17 71 72 38 4 52 32 71 1 47 49 15 92 3 78 57 34 40 46 72 63 44 93 93 91 12 6...

output:

2900
763
2158
1739
5439
9265
5427
7984
4769
1621
3948
5439
9265
5427
705
6826
9518
7178
5439
9265
5427
1540
6552
6257
4031
5439
9265
5427
3776
3775
8991
5142
5439
9265
5427
9175
3149
7781
7178
5439
9265
5427
9243
6215
8620
4626
5439
9265
5427
4359
7313
4228
3948
5439
9265
5427
3856
6778
1404
7178
54...

result:

ok 10000 lines

Test #24:

score: 0
Accepted
time: 30ms
memory: 16988kb

input:

100000 100000
0 0 2 2 0 3 0 3 2 6 6 7 10 0 9 4 7 4 5 6 13 21 5 19 22 20 0 22 14 4 15 23 4 2 5 6 36 25 32 30 5 6 32 14 37 17 40 1 32 41 18 13 38 27 20 38 35 12 31 28 37 44 56 51 53 51 61 43 17 46 51 57 3 52 62 64 36 53 59 19 16 26 60 27 61 57 78 15 37 84 34 74 88 33 69 61 9 18 40 0 68 30 51 66 92 79 ...

output:

44115
48957
7723
56998
73666
8680
93406
46872
25232
78896
7762
38388
89978
87419
73493
87679
794
12691
57534
42565
28052
33217
81870
14705
99958
66096
78869
87419
85678
5519
70221
92048
33401
5609
37916
76716
53649
70798
94766
78960
89978
87419
74851
42910
99607
11265
17617
57217
61753
7399
92854
75...

result:

ok 100000 lines

Test #25:

score: 0
Accepted
time: 116ms
memory: 27264kb

input:

300000 300000
0 0 2 3 3 4 4 5 5 0 3 7 1 0 10 4 4 3 7 10 7 12 11 19 6 22 0 6 3 23 13 31 12 25 17 8 22 27 26 17 13 37 11 21 29 11 18 26 22 5 26 45 29 13 14 25 5 13 24 22 16 14 22 2 32 49 27 40 48 43 64 63 30 19 41 32 46 7 1 12 30 80 58 81 8 18 15 68 77 9 39 42 10 55 37 27 15 75 8 8 55 99 10 16 65 44 5...

output:

28949
113312
21382
135323
205446
108958
175649
15860
232437
71800
290114
130570
264475
115849
117739
152971
251884
15860
226973
71800
106114
78289
190620
200679
247494
196403
148207
15860
161291
71800
128315
42157
47827
11985
92502
19028
246711
15860
249745
71800
171813
262290
264444
208224
114458
3...

result:

ok 300000 lines

Test #26:

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

input:

300000 300000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok 300000 lines

Test #27:

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

input:

300000 300000
0 0 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18 20 20 22 22 24 24 26 26 28 28 30 30 32 32 34 34 36 36 38 38 40 40 42 42 44 44 46 46 48 48 50 50 52 52 54 54 56 56 58 58 60 60 62 62 64 64 66 66 68 68 70 70 72 72 74 74 76 76 78 78 80 80 82 82 84 84 86 86 88 88 90 90 92 92 94 94 96 96 98...

output:

1
3
1
5
1
3
1
7
1
3
1
5
1
3
1
9
1
3
1
5
1
3
1
7
1
3
1
5
1
3
1
11
1
3
1
5
1
3
1
7
1
3
1
5
1
3
1
9
1
3
1
5
1
3
1
7
1
3
1
5
1
3
1
13
1
3
1
5
1
3
1
7
1
3
1
5
1
3
1
9
1
3
1
5
1
3
1
7
1
3
1
5
1
3
1
11
1
3
1
5
1
3
1
7
1
3
1
5
1
3
1
9
1
3
1
5
1
3
1
7
1
3
1
5
1
3
1
15
1
3
1
5
1
3
1
7
1
3
1
5
1
3
1
9
1
3
1
5
...

result:

ok 300000 lines

Test #28:

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

input:

300000 300000
0 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 45 45 47 47 49 49 51 51 53 53 55 55 57 57 59 59 61 61 63 63 65 65 67 67 69 69 71 71 73 73 75 75 77 77 79 79 81 81 83 83 85 85 87 87 89 89 91 91 93 93 95 95 97 97 ...

output:

2
4
2
6
2
4
2
8
2
4
2
6
2
4
2
10
2
4
2
6
2
4
2
8
2
4
2
6
2
4
2
12
2
4
2
6
2
4
2
8
2
4
2
6
2
4
2
10
2
4
2
6
2
4
2
8
2
4
2
6
2
4
2
14
2
4
2
6
2
4
2
8
2
4
2
6
2
4
2
10
2
4
2
6
2
4
2
8
2
4
2
6
2
4
2
12
2
4
2
6
2
4
2
8
2
4
2
6
2
4
2
10
2
4
2
6
2
4
2
8
2
4
2
6
2
4
2
16
2
4
2
6
2
4
2
8
2
4
2
6
2
4
2
10
2
4...

result:

ok 300000 lines

Test #29:

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

input:

300000 300000
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 ...

output:

262143
196607
163839
229375
294911
212991
180223
245759
278527
204799
172031
237567
155647
221183
188415
253951
270335
200703
167935
233471
151551
217087
184319
249855
286719
208895
176127
241663
159743
225279
192511
258047
266239
198655
165887
231423
299007
215039
182271
247807
282623
206847
174079...

result:

ok 300000 lines

Test #30:

score: 0
Accepted
time: 59ms
memory: 26228kb

input:

300000 300000
0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 14 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 20 20 20 21 21 21 22 22 22 23 23 23 24 24 24 25 25 25 26 26 26 27 27 27 28 28 28 29 29 29 30 30 30 31 31 31 32 32 32 33 33 33 34 34 34 3...

output:

265720
147622
206671
108256
167305
226354
127939
186988
246037
285403
154183
213232
114817
173866
232915
134500
193549
252598
101695
160744
219793
121378
180427
239476
141061
200110
259159
272281
149809
208858
110443
169492
228541
130126
189175
248224
291964
156370
215419
117004
176053
235102
136687...

result:

ok 300000 lines

Test #31:

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

input:

300000 300000
0 1 1 3 4 5 5 7 7 8 10 11 12 12 14 14 16 16 17 19 19 21 22 23 23 24 25 26 28 29 29 30 32 33 33 35 36 37 38 38 40 40 41 43 44 45 45 47 47 48 50 51 51 52 54 55 56 56 58 59 59 60 61 62 63 65 66 66 67 69 70 70 71 72 73 75 75 77 78 79 79 80 82 82 84 85 85 87 87 88 90 91 92 93 94 94 96 97 98...

output:

2
6
2
13
2
6
2
9
2
6
2
15
2
6
2
9
2
6
2
13
2
6
2
9
2
6
2
20
2
6
2
9
2
6
2
13
2
6
2
9
2
6
2
15
2
6
2
9
2
6
2
13
2
6
2
9
2
6
2
18
2
6
2
9
2
6
2
13
2
6
2
9
2
6
2
15
2
6
2
9
2
6
2
13
2
6
2
9
2
6
2
34
2
6
2
9
2
6
2
13
2
6
2
9
2
6
2
15
2
6
2
9
2
6
2
13
2
6
2
9
2
6
2
18
2
6
2
9
2
6
2
13
2
6
2
9
2
6
2
15
2
...

result:

ok 300000 lines

Test #32:

score: 0
Accepted
time: 64ms
memory: 34060kb

input:

300000 300000
0 1 2 1 2 5 4 5 6 9 10 11 12 11 13 14 14 16 16 19 20 21 22 22 24 23 26 27 28 28 28 29 31 31 32 33 34 35 36 37 38 39 41 42 42 43 44 45 47 47 50 49 50 52 54 53 55 56 56 58 58 59 61 62 62 64 65 65 68 68 70 70 71 72 72 73 75 76 77 79 80 81 82 83 82 85 86 87 86 89 88 90 92 91 93 95 96 95 98...

output:

3
7
15
7
3
7
8
7
3
7
18
7
3
7
8
7
3
7
15
7
3
7
8
7
3
7
17
7
3
7
8
7
3
7
15
7
3
7
8
7
3
7
46
7
3
7
8
7
3
7
15
7
3
7
8
7
3
7
17
7
3
7
8
7
3
7
15
7
3
7
8
7
3
7
18
7
3
7
8
7
3
7
15
7
3
7
8
7
3
7
17
7
3
7
8
7
3
7
15
7
3
7
8
7
3
7
25
7
3
7
8
7
3
7
15
7
3
7
8
7
3
7
17
7
3
7
8
7
3
7
15
7
3
7
8
7
3
7
18
7
3
...

result:

ok 300000 lines

Test #33:

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

input:

300000 300000
0 0 0 3 1 3 4 5 8 9 8 9 9 11 13 15 14 16 18 18 20 21 18 21 20 23 22 23 27 29 30 30 29 30 31 33 33 34 34 39 37 38 40 42 41 41 43 45 48 48 47 49 51 49 53 53 55 54 55 55 57 57 60 61 60 64 62 65 64 69 67 67 68 73 71 71 75 76 77 75 78 80 79 83 84 85 84 84 85 88 87 90 90 91 94 94 96 93 97 95...

output:

10
2
7
17
2
6
12
2
7
17
2
6
19
2
7
17
2
6
10
2
7
17
2
6
12
2
7
17
2
6
35
2
7
17
2
6
10
2
7
17
2
6
12
2
7
17
2
6
26
2
7
17
2
6
10
2
7
17
2
6
12
2
7
17
2
6
19
2
7
17
2
6
10
2
7
17
2
6
12
2
7
17
2
6
25
2
7
17
2
6
10
2
7
17
2
6
12
2
7
17
2
6
28
2
7
17
2
6
10
2
7
17
2
6
12
2
7
17
2
6
19
2
7
17
2
6
10
2
7...

result:

ok 300000 lines

Test #34:

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

input:

300000 300000
0 0 0 0 2 0 6 0 1 0 2 3 12 12 11 8 7 11 16 10 14 14 22 21 17 25 25 27 24 26 30 30 24 30 25 35 35 28 29 39 40 33 42 43 35 39 38 39 46 47 41 51 43 53 50 47 54 50 58 53 59 60 55 54 60 58 57 60 60 60 61 62 65 73 65 67 70 68 70 79 79 74 80 82 75 78 85 86 84 87 82 84 89 86 88 86 90 91 89 94 ...

output:

9
5
13
4
31
19
20
9
15
52
4
63
19
20
9
5
13
4
36
19
20
9
18
23
4
32
19
20
9
5
13
4
56
19
20
9
15
44
4
37
19
20
9
5
13
4
34
19
20
9
18
23
4
71
19
20
9
5
13
4
45
19
20
9
15
49
4
31
19
20
9
5
13
4
56
19
20
9
18
23
4
36
19
20
9
5
13
4
32
19
20
9
15
76
4
63
19
20
9
5
13
4
37
19
20
9
18
23
4
34
19
20
9
5
...

result:

ok 300000 lines

Test #35:

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

input:

300000 300000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 7 0 0 0 0 15 0 0 6 0 15 0 0 0 0 24 0 0 0 10 0 15 27 0 0 0 30 0 0 37 0 0 0 44 45 26 42 4 22 27 14 15 35 0 28 2 0 0 46 0 64 8 19 5 0 4 0 63 41 39 7 75 33 65 22 80 0 63 35 64 0 45 74 16 78 45 61 53 72 47 81 22 92 83 62 45 20 78 86 38 93 69 40 52 58 33 54 72 ...

output:

1
192
3
230
107
357
168
133
9
121
21
12
13
56
279
118
179
116
337
23
25
135
60
29
109
32
90
34
36
77
128
276
43
49
66
95
48
151
134
225
207
231
94
82
136
1
119
3
186
232
287
76
133
9
165
51
12
13
56
162
118
196
116
172
23
25
55
60
29
109
32
111
34
36
77
128
149
43
49
167
95
48
151
290
99
281
141
181...

result:

ok 300000 lines

Test #36:

score: 0
Accepted
time: 96ms
memory: 27136kb

input:

300000 300000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

1
2982
11909
4604
771
6
8186
27582
9
843
15511
2052
825
1347
15
8885
1164
5436
20720
145
12239
22
54258
1271
2253
26
9139
3648
29
21730
22661
1886
5063
34
4893
36
8884
8848
3308
5916
8695
5383
2676
44
11512
46
3264
27203
15839
50
2254
9594
53
6382
55
56
57
7782
3137
60
61
62
63
8385
65
66
7608
68
15...

result:

ok 300000 lines

Test #37:

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

input:

300000 300000
0 1 2 2 3 4 5 6 8 8 10 10 11 13 13 15 15 17 17 18 19 20 22 22 24 24 25 26 27 29 30 31 32 33 33 35 36 36 37 38 39 41 41 42 44 44 45 47 48 48 49 50 51 53 53 55 56 56 58 59 59 61 62 63 63 65 65 67 68 68 70 70 71 73 73 75 76 76 77 79 79 80 82 83 84 85 85 86 88 88 89 91 92 93 93 95 95 97 97...

output:

7
9
7
14
7
9
7
12
7
9
7
16
7
9
7
12
7
9
7
14
7
9
7
12
7
9
7
23
7
9
7
12
7
9
7
14
7
9
7
12
7
9
7
16
7
9
7
12
7
9
7
14
7
9
7
12
7
9
7
21
7
9
7
12
7
9
7
14
7
9
7
12
7
9
7
16
7
9
7
12
7
9
7
14
7
9
7
12
7
9
7
34
7
9
7
12
7
9
7
14
7
9
7
12
7
9
7
16
7
9
7
12
7
9
7
14
7
9
7
12
7
9
7
21
7
9
7
12
7
9
7
14
7
9...

result:

ok 300000 lines

Test #38:

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

input:

300000 300000
0 1 2 3 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 22 23 24 25 26 27 27 29 30 31 32 32 33 35 36 36 37 39 40 41 42 43 44 44 46 46 48 49 50 51 51 53 54 55 55 57 57 59 60 61 62 63 64 65 65 66 68 69 70 71 72 73 73 75 76 76 77 79 79 81 82 82 84 85 86 86 88 89 90 91 92 93 94 95 96 97 98...

output:

4
21
4
28
4
21
4
45
4
21
4
28
4
21
4
34
4
21
4
28
4
21
4
38
4
21
4
28
4
21
4
34
4
21
4
28
4
21
4
47
4
21
4
28
4
21
4
34
4
21
4
28
4
21
4
38
4
21
4
28
4
21
4
34
4
21
4
28
4
21
4
45
4
21
4
28
4
21
4
34
4
21
4
28
4
21
4
38
4
21
4
28
4
21
4
34
4
21
4
28
4
21
4
52
4
21
4
28
4
21
4
34
4
21
4
28
4
21
4
38
...

result:

ok 300000 lines

Test #39:

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

input:

300000 300000
0 1 2 2 3 5 6 7 8 9 10 11 12 13 14 15 15 17 18 18 20 20 22 23 24 25 26 27 28 28 29 31 32 33 34 35 36 37 38 39 40 41 42 42 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 66 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 82 84 85 86 87 88 89 90 91 92 93 94 95 95 97 98...

output:

16
4
19
4
16
4
21
4
16
4
19
4
16
4
43
4
16
4
19
4
16
4
21
4
16
4
19
4
16
4
30
4
16
4
19
4
16
4
21
4
16
4
19
4
16
4
67
4
16
4
19
4
16
4
21
4
16
4
19
4
16
4
30
4
16
4
19
4
16
4
21
4
16
4
19
4
16
4
43
4
16
4
19
4
16
4
21
4
16
4
19
4
16
4
30
4
16
4
19
4
16
4
21
4
16
4
19
4
16
4
83
4
16
4
19
4
16
4
21
4
...

result:

ok 300000 lines

Test #40:

score: 0
Accepted
time: 77ms
memory: 41004kb

input:

300000 300000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 23 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

24
123
24
368
24
123
24
638
24
123
24
368
24
123
24
759
24
123
24
368
24
123
24
638
24
123
24
368
24
123
24
884
24
123
24
368
24
123
24
638
24
123
24
368
24
123
24
759
24
123
24
368
24
123
24
638
24
123
24
368
24
123
24
920
24
123
24
368
24
123
24
638
24
123
24
368
24
123
24
759
24
123
24
368
24
123...

result:

ok 300000 lines

Test #41:

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

input:

300000 300000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

3181
3353
3181
4328
3181
3353
3181
4512
3181
3353
3181
4328
3181
3353
3181
4675
3181
3353
3181
4328
3181
3353
3181
4512
3181
3353
3181
4328
3181
3353
3181
4946
3181
3353
3181
4328
3181
3353
3181
4512
3181
3353
3181
4328
3181
3353
3181
4675
3181
3353
3181
4328
3181
3353
3181
4512
3181
3353
3181
4328
...

result:

ok 300000 lines

Test #42:

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

input:

300000 300000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

117
15793
117
26498
117
15793
117
29826
117
15793
117
26498
117
15793
117
38524
117
15793
117
26498
117
15793
117
29826
117
15793
117
26498
117
15793
117
76621
117
15793
117
26498
117
15793
117
29826
117
15793
117
26498
117
15793
117
38524
117
15793
117
26498
117
15793
117
29826
117
15793
117
26498
...

result:

ok 300000 lines

Test #43:

score: 0
Accepted
time: 81ms
memory: 43888kb

input:

300000 300000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

1156
27460
1156
66664
1156
27460
1156
85611
1156
27460
1156
66664
1156
27460
1156
118513
1156
27460
1156
66664
1156
27460
1156
85611
1156
27460
1156
66664
1156
27460
1156
136084
1156
27460
1156
66664
1156
27460
1156
85611
1156
27460
1156
66664
1156
27460
1156
118513
1156
27460
1156
66664
1156
27460
...

result:

ok 300000 lines

Test #44:

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

input:

300000 300000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

119856
266829
222184
233011
132254
201969
184496
190519
271974
159889
198655
237831
210512
280922
142685
161922
216801
236250
167719
130794
137146
240412
159889
275997
195612
210512
156283
273271
213430
132345
203214
118182
142827
242020
255743
159889
190623
235172
210512
275918
294402
149244
229502...

result:

ok 300000 lines

Test #45:

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

input:

300000 300000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

136370
146156
171310
193114
215691
256168
163147
226279
119019
144329
264720
114535
260305
257306
211152
168710
259792
136535
221681
103279
175181
266842
156848
176711
117916
192887
186294
195280
148910
119917
112966
273334
162443
114900
278347
200812
136535
263172
294937
196204
239324
145773
153991...

result:

ok 300000 lines

Test #46:

score: 0
Accepted
time: 94ms
memory: 32900kb

input:

300000 300000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

228658
178141
183774
100100
112598
114578
132672
102208
134628
103033
171514
249719
255541
248218
224524
299750
298429
291146
152125
178880
234228
215396
295845
204834
132767
251764
121411
227158
285099
265592
260227
277628
178056
227326
298429
291146
274764
191040
119517
264927
163945
132502
141888...

result:

ok 300000 lines

Test #47:

score: 0
Accepted
time: 89ms
memory: 32856kb

input:

300000 300000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

284705
158376
211923
180128
183453
126828
207083
248004
258098
133945
107126
282258
219730
188790
131177
174732
101834
253518
116956
205827
254554
112233
242327
143227
296451
166525
160538
257379
167535
259865
131177
174732
204935
222273
112912
155753
153303
298879
288871
191532
238262
225958
208993...

result:

ok 300000 lines

Test #48:

score: 0
Accepted
time: 81ms
memory: 32996kb

input:

300000 300000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

186969
279039
173867
168758
157025
223510
105331
261604
255000
260291
204797
269579
144100
240800
205677
252699
241333
119773
242984
213685
146825
245356
253527
269579
218765
255832
247448
195500
233624
294182
288696
196814
228856
167032
235806
269579
171730
120441
100258
170730
268198
215664
272922...

result:

ok 300000 lines

Test #49:

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

input:

300000 300000
0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 9...

output:

100000
99998
99999
100001
200001
99999
100002
200002
99999
100003
200003
99999
100004
200004
99999
100005
200005
99999
100006
200006
99999
100007
200007
99999
100008
200008
99999
100009
200009
99999
100010
200010
99999
100011
200011
99999
100012
200012
99999
100013
200013
99999
100014
200014
99999
1...

result:

ok 300000 lines

Test #50:

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

input:

300000 300000
0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 9...

output:

299998
299999
299997
299998
299999
299997
299998
299999
299997
299998
299999
299997
299998
299999
299997
299998
299999
299997
299998
299999
299997
299998
299999
299997
299998
299999
299997
299998
299999
299997
299998
299999
299997
299998
299999
299997
299998
299999
299997
299998
299999
299997
299998...

result:

ok 300000 lines

Test #51:

score: -100
Runtime Error

input:

300000 300000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:


result: