QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#356856#6772. Spicy Restaurantezteam1#AC ✓224ms20076kbC++141006b2024-03-18 14:00:082024-03-18 14:00:09

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11132kb

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: 159ms
memory: 14168kb

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: 183ms
memory: 14048kb

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

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: 137ms
memory: 13844kb

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: 134ms
memory: 13828kb

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: 137ms
memory: 14164kb

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: 143ms
memory: 14024kb

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: 143ms
memory: 14116kb

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: 135ms
memory: 13936kb

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: 210ms
memory: 18776kb

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: 163ms
memory: 18588kb

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

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: 161ms
memory: 18544kb

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

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: 221ms
memory: 20076kb

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: 214ms
memory: 19840kb

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

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: 212ms
memory: 19708kb

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: 219ms
memory: 19504kb

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: 182ms
memory: 19072kb

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: 189ms
memory: 19248kb

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: 206ms
memory: 18880kb

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: 202ms
memory: 19252kb

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: 208ms
memory: 18960kb

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