QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#141848#6772. Spicy RestaurantsdoiAC ✓298ms49468kbC++23872b2023-08-18 02:50:122023-08-18 02:50:13

詳細信息

Test #1:

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

input:

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

output:

-1
2
1
1
0

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 204ms
memory: 47848kb

input:

50000 100000 100000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

0
8
6
5
-1
7
5
5
-1
7
7
6
6
4
6
6
8
5
7
6
8
5
6
7
5
8
7
6
7
6
6
7
5
6
-1
0
6
7
7
-1
7
7
8
-1
7
6
7
0
7
7
8
7
6
7
5
6
8
7
8
7
7
6
-1
6
6
7
7
9
7
6
6
7
6
6
7
7
7
7
7
8
7
-1
6
5
7
6
8
8
7
8
6
7
0
6
-1
7
7
8
8
-1
7
6
6
6
8
6
4
8
5
6
6
8
9
6
8
-1
5
-1
7
7
5
7
6
-1
8
-1
8
8
7
7
0
6
8
6
8
6
6
0
6
8
-1
6
8
...

result:

ok 100000 lines

Test #3:

score: 0
Accepted
time: 212ms
memory: 47488kb

input:

50000 100000 100000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

5
5
6
7
6
7
6
6
5
7
6
4
5
6
7
5
6
8
7
7
7
5
5
5
6
8
6
6
6
7
7
6
6
7
4
5
7
6
6
7
7
6
6
6
6
5
6
3
8
7
6
4
7
5
6
7
6
7
7
7
7
6
6
5
6
7
5
7
6
6
6
7
7
6
6
5
7
7
5
7
5
7
7
7
7
7
7
6
6
6
7
6
5
5
7
6
6
7
6
7
6
6
8
7
7
7
7
8
8
6
7
8
6
5
6
7
6
6
3
6
7
7
6
7
5
7
6
6
6
6
6
6
6
7
7
7
6
7
6
8
7
6
4
7
6
7
6
5
7
7
...

result:

ok 100000 lines

Test #4:

score: 0
Accepted
time: 198ms
memory: 48304kb

input:

50000 100000 100000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

7
8
7
8
5
5
-1
7
7
-1
6
-1
7
7
5
8
7
6
7
8
7
7
8
5
7
7
5
7
7
6
7
7
7
6
5
8
6
5
-1
7
7
6
8
6
-1
8
5
6
7
8
7
8
9
7
-1
7
7
7
5
8
8
7
6
8
6
8
8
6
-1
6
6
-1
6
7
6
7
8
5
5
7
8
8
6
7
-1
7
6
6
6
6
6
6
7
-1
9
6
6
8
9
7
6
7
8
7
7
7
8
7
6
8
8
7
7
-1
5
7
7
8
-1
6
5
6
7
7
8
8
9
7
7
7
-1
7
5
6
-1
6
-1
5
7
7
8
8
6...

result:

ok 100000 lines

Test #5:

score: 0
Accepted
time: 169ms
memory: 48088kb

input:

50000 100000 100000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

17230
17229
17231
17231
17233
17231
17231
17232
17229
17229
17229
17230
17230
17230
17230
17229
17230
17233
17229
17228
17233
17231
17229
17231
17229
17231
17228
17231
17231
17230
17230
17230
17230
17231
17230
-1
17232
17228
17230
17228
17231
17229
17230
17229
17229
17230
17233
17230
17231
17229
0
1...

result:

ok 100000 lines

Test #6:

score: 0
Accepted
time: 167ms
memory: 47900kb

input:

50000 100000 100000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

17230
17228
17230
17229
17229
17230
17229
17228
17230
17229
17230
17230
17229
17230
17230
17229
17229
17229
17230
17230
17229
17230
17230
17229
17228
17229
17231
17229
17230
17228
17230
17228
17231
17230
17230
17229
17230
17225
17228
17230
17229
17229
17228
17230
17230
17228
17230
17230
17229
17230
...

result:

ok 100000 lines

Test #7:

score: 0
Accepted
time: 164ms
memory: 47944kb

input:

50000 100000 100000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

17229
17228
17230
17228
17227
17228
17228
17229
17229
17227
17229
17229
17229
17226
17228
17228
17226
17228
17228
17229
17228
17229
17228
17229
17228
17227
17228
17229
17228
17226
17229
17228
17229
17228
17227
17228
17229
17229
17228
17228
17228
0
17228
17227
17229
17228
17227
17228
17229
17230
1722...

result:

ok 100000 lines

Test #8:

score: 0
Accepted
time: 171ms
memory: 47256kb

input:

50000 100000 100000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

16239
16241
16240
16240
16239
16240
16241
16239
16240
16237
16239
16239
16239
16240
16242
16239
16239
16239
16239
16238
16240
16242
16240
16240
16240
16237
16240
16240
16239
16239
0
16240
0
16238
16239
16238
16239
16240
16239
16239
16239
16238
16239
16240
16239
16240
16239
16239
16242
16238
16238
16...

result:

ok 100000 lines

Test #9:

score: 0
Accepted
time: 157ms
memory: 47456kb

input:

50000 100000 100000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

16239
16245
16239
16300
16239
16245
16303
16245
16244
16239
16245
16245
16245
16335
16239
16244
16240
16244
16240
16244
16246
16242
16244
16245
16245
16245
16246
16246
16245
16241
16238
16280
16240
16244
16243
16242
16238
16238
16244
16243
0
16244
16245
16239
16239
16245
16238
16240
16243
16238
1630...

result:

ok 100000 lines

Test #10:

score: 0
Accepted
time: 175ms
memory: 47976kb

input:

50000 100000 100000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

16238
16239
16239
16239
16240
16240
16239
16240
16240
16240
16241
16240
16294
16240
16255
16239
16240
16239
16239
16241
16240
16239
16240
16239
16281
16293
16240
16239
16238
16238
16239
16240
16240
16239
16238
16240
16240
16240
16295
16239
16238
16281
16239
16240
16240
16238
16240
16240
16237
16294
...

result:

ok 100000 lines

Test #11:

score: 0
Accepted
time: 296ms
memory: 47716kb

input:

50000 100000 500000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

2
3
5
4
5
5
5
4
4
4
5
5
3
3
4
4
4
2
4
5
4
3
1
4
6
3
4
6
3
4
5
4
5
3
4
4
2
5
5
4
4
3
2
3
4
4
3
5
5
4
5
5
4
4
5
3
2
4
5
4
3
3
7
4
2
2
4
4
5
3
4
6
5
5
4
5
4
4
4
4
5
3
4
3
3
4
3
5
4
4
6
3
5
5
5
5
4
6
3
4
4
5
4
5
4
0
4
5
4
3
4
4
4
5
4
4
4
2
4
3
4
2
3
4
5
2
4
5
4
4
1
5
3
0
4
4
5
5
4
4
5
3
3
4
3
5
3
5
4
3
...

result:

ok 500000 lines

Test #12:

score: 0
Accepted
time: 238ms
memory: 47332kb

input:

50000 100000 500000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

16240
16239
16240
16240
16240
16240
16240
16258
16238
16239
16239
16258
16240
16259
16238
16239
16240
16240
16240
16240
16240
16239
16241
16240
16239
16246
16240
16240
16240
16240
16248
16237
16240
16237
16239
16239
16246
16238
16241
16240
16239
16239
16238
16247
16259
16239
16260
16239
16246
16240
...

result:

ok 500000 lines

Test #13:

score: 0
Accepted
time: 271ms
memory: 47852kb

input:

50000 100000 500000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

16240
16243
16239
16238
16239
16238
0
16242
16243
16240
16244
16243
16243
16240
16239
16238
16237
16244
16239
16240
16237
16239
16239
16237
16240
16240
16240
16243
16244
16240
16240
16244
16239
16238
16243
16318
16240
16239
16239
16240
16239
16243
16238
16238
16240
16240
16238
16240
16241
16240
1624...

result:

ok 500000 lines

Test #14:

score: 0
Accepted
time: 267ms
memory: 48320kb

input:

50000 100000 500000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

16244
16237
16427
16239
16237
16240
16241
16241
16243
16240
16241
16242
16239
16239
16239
16240
16239
16240
16239
16245
16240
16242
16241
16239
16240
16244
16242
16244
16238
16240
16240
16428
16240
16240
16237
16240
16242
16239
16239
16238
16241
16239
0
16242
16241
16244
16245
16238
16240
16244
1623...

result:

ok 500000 lines

Test #15:

score: 0
Accepted
time: 254ms
memory: 48264kb

input:

50000 100000 500000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

16239
16241
16240
16240
16238
16240
16241
16239
16241
16241
16242
16241
16241
16241
16238
16241
16240
16241
16242
16242
16239
16240
16241
16240
16241
16242
16240
16241
16454
16240
16242
16242
16241
16264
16241
16242
16239
16240
16241
16241
16239
16241
16240
16241
16240
16240
16240
16241
16240
16239
...

result:

ok 500000 lines

Test #16:

score: 0
Accepted
time: 285ms
memory: 49452kb

input:

100000 100000 500000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100...

output:

5
12
2
9
3
5
1
5
1
1
2
3
4
3
4
5
2
2
2
3
3
2
3
3
2
2
2
2
4
1
4
4
2
8
5
4
1
5
6
3
4
3
6
4
1
5
2
2
4
4
2
6
1
5
5
5
2
5
5
1
3
5
6
6
1
7
0
7
6
1
2
3
5
3
5
4
4
4
0
6
2
6
3
2
5
1
6
4
3
3
1
2
3
1
5
5
3
3
5
2
4
8
3
6
1
4
6
3
5
5
8
1
2
1
5
3
6
1
12
6
10
1
1
3
4
2
1
4
4
2
5
3
1
4
4
8
1
1
6
6
5
3
3
4
2
2
4
6
3...

result:

ok 500000 lines

Test #17:

score: 0
Accepted
time: 273ms
memory: 49440kb

input:

100000 100000 500000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100...

output:

2
6
5
4
1
6
5
2
3
5
2
5
4
2
1
3
3
4
3
5
3
2
4
2
3
5
1
3
6
4
5
8
2
2
3
4
2
1
2
1
1
2
4
4
4
2
11
8
9
0
4
4
2
5
2
5
2
9
3
3
7
5
2
3
4
4
3
7
2
1
1
5
5
2
9
3
6
4
0
5
8
4
5
0
6
2
2
4
4
4
7
4
8
5
4
5
3
1
1
1
5
1
4
3
6
3
3
1
9
2
1
10
5
1
10
2
3
1
1
5
3
2
4
7
3
3
4
1
8
5
6
1
4
4
5
7
6
6
8
5
3
2
3
4
4
4
3
6
3...

result:

ok 500000 lines

Test #18:

score: 0
Accepted
time: 270ms
memory: 49468kb

input:

100000 100000 500000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100...

output:

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

result:

ok 500000 lines

Test #19:

score: 0
Accepted
time: 294ms
memory: 49448kb

input:

100000 100000 500000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100...

output:

10
12
4
7
6
4
7
7
6
4
4
3
2
5
4
1
4
3
3
7
6
3
6
4
2
2
5
2
3
2
6
2
4
2
2
4
6
3
6
4
3
4
3
1
4
3
2
2
3
2
3
2
2
2
5
3
3
3
1
4
4
2
2
3
3
3
2
1
4
4
3
2
2
2
2
2
1
3
3
2
3
1
4
1
6
3
3
2
1
1
4
2
2
1
5
1
1
2
0
8
5
7
10
10
5
7
3
5
6
4
6
5
6
5
8
7
4
6
4
8
7
6
4
3
4
4
3
6
8
6
2
1
5
3
7
3
3
2
3
1
1
2
5
2
4
3
1
6
...

result:

ok 500000 lines

Test #20:

score: 0
Accepted
time: 298ms
memory: 49376kb

input:

100000 100000 500000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100...

output:

9
9
6
6
5
8
4
6
9
7
6
5
3
4
8
3
2
5
4
5
5
3
4
5
4
4
3
7
5
5
5
5
6
2
2
4
1
3
5
3
2
6
3
4
7
2
2
3
2
4
4
3
3
4
4
1
3
4
3
7
3
2
4
3
2
4
3
1
4
4
3
1
3
2
2
3
4
3
3
1
3
1
3
2
2
1
2
2
2
3
2
4
3
2
3
1
1
3
0
11
11
8
5
5
10
6
4
6
4
7
8
5
5
3
1
4
3
6
5
7
6
1
6
6
3
7
9
4
4
4
5
3
2
5
4
3
2
8
5
5
1
2
6
4
6
1
2
3
3...

result:

ok 500000 lines

Test #21:

score: 0
Accepted
time: 275ms
memory: 48416kb

input:

60000 100000 500000
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 ...

output:

0
0
0
1
1
1
1
0
0
0
2
0
1
0
2
0
1
2
0
0
2
0
1
0
1
2
0
1
0
0
1
1
1
2
1
0
0
0
1
0
1
0
0
0
0
0
0
1
1
0
2
1
0
0
1
0
0
1
0
1
2
0
1
0
1
1
3
1
0
1
3
0
1
1
1
0
1
0
0
0
1
1
1
1
0
1
1
1
0
1
0
1
1
1
1
0
0
1
1
1
0
0
1
1
0
0
2
1
2
3
2
0
0
0
0
2
1
0
1
1
0
1
1
1
1
0
0
1
2
0
1
1
0
1
1
0
1
1
1
1
0
0
0
0
1
2
0
1
0
0
...

result:

ok 500000 lines

Test #22:

score: 0
Accepted
time: 260ms
memory: 48432kb

input:

60000 100000 500000
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 ...

output:

0
1
0
2
0
2
1
1
1
1
1
0
1
1
0
0
1
0
0
0
1
1
2
0
0
0
0
1
1
0
1
0
2
0
0
1
0
0
0
1
1
0
0
0
2
1
0
2
0
0
1
1
0
0
0
0
2
0
2
0
0
0
1
1
1
0
3
1
2
2
1
1
0
0
2
0
0
1
0
1
1
1
0
0
0
3
2
0
0
1
1
1
1
0
2
0
0
2
0
0
0
0
3
2
1
0
2
0
1
1
1
2
1
1
0
0
0
0
1
0
1
0
1
1
1
0
0
1
1
1
2
0
1
1
1
1
0
0
0
0
0
1
0
1
0
0
0
0
0
1
...

result:

ok 500000 lines

Test #23:

score: 0
Accepted
time: 274ms
memory: 48544kb

input:

60000 100000 500000
21 35 13 18 12 63 79 19 28 42 91 92 63 58 47 4 95 72 5 33 25 75 80 17 34 60 34 61 52 14 61 66 16 79 73 47 45 97 12 39 21 25 45 37 70 75 85 29 24 100 71 49 81 44 81 40 18 32 7 21 92 36 4 71 13 12 7 100 23 60 100 51 17 35 83 83 9 24 35 81 74 64 91 28 92 99 33 83 52 67 20 94 88 97 4...

output:

0
0
2
0
1
0
1
0
0
1
0
1
0
0
1
1
0
1
2
1
1
1
1
0
1
1
0
1
1
2
1
0
0
0
1
0
0
0
0
1
0
0
0
1
2
0
0
0
3
1
0
1
0
1
0
1
4
2
1
1
2
1
0
2
2
1
1
0
0
1
1
1
0
2
0
0
2
0
0
0
1
0
1
1
1
1
1
0
0
0
0
1
0
0
1
0
1
0
0
3
1
1
0
0
1
1
1
1
2
0
1
0
0
2
0
0
0
0
0
2
0
1
1
0
0
2
0
0
0
2
2
1
1
0
1
4
0
0
1
1
2
1
1
0
1
0
1
0
0
0
...

result:

ok 500000 lines

Test #24:

score: 0
Accepted
time: 283ms
memory: 47908kb

input:

60000 100000 500000
40 89 94 25 64 56 54 24 93 89 3 57 24 32 28 29 63 52 89 41 82 25 65 36 16 77 14 11 73 52 67 14 66 54 49 100 11 80 18 65 45 49 76 82 32 58 94 1 99 80 76 89 9 82 43 100 86 58 55 7 66 64 44 10 1 52 30 20 84 83 57 65 23 26 11 98 28 10 36 81 42 23 45 94 86 90 8 93 62 100 51 34 91 89 1...

output:

0
0
0
0
0
2
1
1
0
0
1
1
2
0
1
0
1
0
0
0
1
1
0
1
1
1
0
0
1
1
2
1
1
3
0
1
1
1
1
0
0
0
3
3
0
2
0
1
3
1
0
0
0
2
2
0
0
0
0
1
1
1
0
2
0
0
2
0
3
0
2
1
1
2
1
2
1
0
0
1
0
0
0
1
1
4
0
0
0
1
1
0
0
0
0
1
2
0
1
2
0
1
1
0
3
2
0
1
0
0
0
2
0
1
2
0
1
0
2
0
0
0
1
1
1
1
2
1
1
0
1
0
1
4
0
3
1
0
0
1
1
0
1
1
0
4
0
1
0
0
...

result:

ok 500000 lines

Test #25:

score: 0
Accepted
time: 284ms
memory: 48576kb

input:

60000 100000 500000
57 95 11 70 69 21 48 87 15 17 64 77 47 28 17 15 81 74 43 60 23 26 3 73 95 3 84 53 70 73 3 94 85 45 96 78 90 50 46 33 98 77 75 81 50 94 42 73 66 26 64 90 22 35 88 82 27 87 72 79 8 94 53 8 85 58 83 55 79 63 65 55 90 22 97 38 87 38 15 37 23 42 34 11 64 94 52 96 32 28 71 27 55 32 76 ...

output:

0
0
1
1
0
2
1
1
1
0
2
1
0
2
1
1
1
0
2
1
1
0
0
0
1
1
0
2
1
1
0
1
0
1
1
1
1
0
1
2
1
2
1
1
0
1
1
0
0
1
1
1
0
2
1
1
2
0
0
0
0
1
0
2
1
0
0
1
0
0
0
0
1
1
0
0
0
1
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
0
1
0
1
0
2
0
0
0
1
2
2
1
1
0
2
0
0
1
1
1
1
0
2
0
0
0
1
0
0
0
1
1
1
0
0
0
1
0
1
0
0
0
1
0
0
1
2
0
2
1
1
0
1
0
1
0
...

result:

ok 500000 lines