QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#629542#6772. Spicy Restaurantucup-team4780#AC ✓315ms49324kbC++141.3kb2024-10-11 13:04:532024-10-11 13:04:54

详细

Test #1:

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

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: 67ms
memory: 47588kb

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

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: 58ms
memory: 47428kb

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

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

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: 45ms
memory: 47680kb

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: 169ms
memory: 47024kb

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: 172ms
memory: 47312kb

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: 168ms
memory: 47216kb

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: 263ms
memory: 47416kb

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: 224ms
memory: 47284kb

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: 232ms
memory: 47432kb

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: 224ms
memory: 47832kb

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: 231ms
memory: 47420kb

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: 268ms
memory: 49172kb

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: 274ms
memory: 49224kb

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: 235ms
memory: 49288kb

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: 262ms
memory: 49280kb

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: 240ms
memory: 49324kb

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: 299ms
memory: 48460kb

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: 309ms
memory: 48216kb

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: 315ms
memory: 48088kb

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: 300ms
memory: 47704kb

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: 302ms
memory: 48472kb

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