QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#402293#4208. Flight to the FordQiuly100 ✓248ms6244kbC++234.0kb2024-04-30 11:10:362024-04-30 11:10:36

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 15
Accepted

Test #1:

score: 15
Accepted
time: 176ms
memory: 6240kb
Overall Time Limit: 500ms

input:

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

output:

510
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
84...

input:

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

output:

510
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #2:

score: 15
Accepted
time: 162ms
memory: 6228kb
Overall Time Limit: 250ms

input:

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

output:

510
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #3:

score: 15
Accepted
time: 140ms
memory: 6004kb
Overall Time Limit: 375ms

input:

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

output:

510
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #4:

score: 15
Accepted
time: 151ms
memory: 6012kb
Overall Time Limit: 500ms

input:

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

output:

510
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #5:

score: 15
Accepted
time: 146ms
memory: 6220kb
Overall Time Limit: 2000ms

input:

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

output:

510
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #6:

score: 15
Accepted
time: 138ms
memory: 5940kb
Overall Time Limit: 250ms

input:

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

output:

510
849 1
849 0
849 0
849 1
849 1
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 1
849 1
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 1
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #7:

score: 15
Accepted
time: 140ms
memory: 5932kb
Overall Time Limit: 375ms

input:

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

output:

510
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Subtask #2:

score: 85
Accepted

Test #8:

score: 85
Accepted
time: 157ms
memory: 6240kb
Overall Time Limit: 2210ms

input:

1
684392489
188482225
1
1
0
0
1
1
0
0
1
0
1
0
0
1
1
0
0
1
0
0
0
1
1
1
1
0
1
1
1
1
1
1
1
0
1
1
1
0
1
0
1
0
0
0
0
1
1
0
1
0
0
0
1
1
0
0
1
0
1
1
1
0
0
1
0
1
1
1
1
0
0
0
1
0
1
0
1
0
0
0
0
1
1
0
0
0
0
1
0
1
1
0
1
0
0
1
0
1
0
1
1
706261730
359904285
0
1
0
0
1
1
0
1
1
0
0
0
0
1
1
0
1
1
1
0
1
1
1
0
1
1
0
1
...

output:

510
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 1
849 1
84...

input:

2
79414403
1
0
1
1
0
1
0
1
1
1
1
0
0
0
1
0
0
0
1
1
1
1
1
0
1
1
1
1
0
1
0
1
1
0
0
1
1
1
1
0
0
1
0
1
1
1
0
1
0
1
0
0
0
0
0
0
1
1
0
1
0
1
1
1
1
1
1
0
0
1
1
0
0
0
1
0
1
1
0
1
0
1
1
0
1
1
1
0
1
1
1
1
0
0
1
1
0
0
1
0
2
508664236
1
0
1
0
0
1
1
1
0
1
1
0
1
1
0
0
0
0
1
1
0
1
0
0
1
1
1
1
0
0
1
1
0
1
0
1
1
0
1...

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #9:

score: 85
Accepted
time: 167ms
memory: 6232kb
Overall Time Limit: 2955ms

input:

1
1000000000
684392485
1
1
1
1
1
1
0
0
1
1
0
1
1
0
0
0
1
0
0
0
1
1
1
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
1
0
0
1
0
0
0
1
1
1
0
0
0
0
1
0
0
1
0
1
1
0
1
0
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
0
1
0
0
0
0
1
1
0
0
1
0
1
1
1
1
0
0
0
0
1
0
0
1
1000000000
235162311
0
0
0
1
0
0
0
0
1
0
0
1
1
1
0
1
0
1
1
1
0
0
1
0
1
1
0
...

output:

510
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
84...

input:

1
1000000000
872874714
1
1
1
1
1
1
0
0
1
1
0
1
1
0
0
0
1
0
0
0
1
1
1
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
1
0
0
1
0
0
0
1
1
1
0
0
0
0
1
0
0
1
0
1
1
0
1
0
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
0
1
0
0
0
0
1
1
0
0
1
0
1
1
1
1
0
0
0
0
1
0
0
1
1000000000
52798983
0
0
0
1
0
0
0
0
1
0
0
1
1
1
0
1
0
1
1
1
0
0
1
0
1
1
0
1...

output:

510
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
84...

input:

1
1000000000
694087436
1
1
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
0
1
1
0
1
1
0
1
1
1
1
0
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
0
1
1
0
1
1
1
1
0
1
1
1
0
1
0
1
0
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1000000000
737327485
0
0
0
1
0
0
0
0
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
0
1
1
...

output:

510
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 1
849 0
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #10:

score: 85
Accepted
time: 185ms
memory: 6240kb
Overall Time Limit: 2020ms

input:

1
1000000000
336586080
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
1
0
0
1
0
0
0
1
0
0
0
1
0
1
0
0
0
0
1
1
1
0
0
0
1
0
0
1
0
1
0
1
1
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
0
1
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
1
1000000000
995427135
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
...

output:

510
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 1
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 0
84...

input:

1
1000000000
174122621
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
1
0
0
1
0
0
0
1
0
0
0
1
0
1
0
0
0
0
1
1
1
0
0
0
1
0
0
1
0
1
0
1
1
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
0
1
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
1
1000000000
141969875
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
...

output:

510
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 1
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #11:

score: 85
Accepted
time: 177ms
memory: 6228kb
Overall Time Limit: 1235ms

input:

1
1000000000
458314021
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
0
1
0
0
1
1
1
1
1
1
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
1
1000000000
458314021
0
0
0
0
0
0
1
1
1
1
1
0
1
1
0
0
0
0
1
0
0
1
1
1
1
1
1
...

output:

510
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
84...

input:

1
1000000000
437207149
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
0
1
0
0
1
1
1
1
1
1
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
1
1000000000
437207149
0
0
0
0
0
0
1
1
1
1
1
0
1
1
0
0
0
0
1
0
0
1
1
1
1
1
1
...

output:

510
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 1
849 0
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #12:

score: 85
Accepted
time: 248ms
memory: 6008kb
Overall Time Limit: 2500ms

input:

1
1000000000
198638718
1
1
1
0
0
0
0
0
0
1
1
1
1
1
1
0
0
1
1
1
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
0
1
0
1
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
1
0
1
0
0
1
0
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
0
0
0
1
0
0
0
1
1
1
1000000000
227274056
1
0
1
0
1
1
1
0
1
1
0
1
0
0
0
1
0
1
1
1
1
1
1
1
1
1
0
...

output:

510
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 0
84...

input:

1
1000000000
615950227
1
1
1
0
0
0
0
0
0
1
1
1
1
1
1
0
0
1
1
1
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
0
1
0
1
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
1
0
1
0
0
1
0
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
0
0
0
1
0
0
0
1
1
1
1000000000
482427607
1
0
1
0
1
1
1
0
1
1
0
1
0
0
0
1
0
1
1
1
1
1
1
1
1
1
0
...

output:

510
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 1
84...

input:

1
1000000000
198638718
0
1
1
1
1
1
1
1
0
0
0
0
1
0
0
1
0
0
0
0
1
1
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
0
1
0
0
0
1
0
1
1
1
0
1
0
0
1
1
0
0
1
1
1
1
0
0
1
0
0
1
0
1
0
1
1
1
0
1
0
1
1
0
1
0
1
0
0
1
0
1
0
0
1
1
1
0
1
1000000000
227274056
1
0
0
1
0
0
0
1
0
1
0
1
1
1
0
1
0
0
1
1
1
0
1
0
0
0
1
...

output:

510
849 1
849 1
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 1
849 0
84...

input:

1
1000000000
615950227
0
1
1
1
1
1
1
1
0
0
0
0
1
0
0
1
0
0
0
0
1
1
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
0
1
0
0
0
1
0
1
1
1
0
1
0
0
1
1
0
0
1
1
1
1
0
0
1
0
0
1
0
1
0
1
1
1
0
1
0
1
1
0
1
0
1
0
0
1
0
1
0
0
1
1
1
0
1
1000000000
482427607
1
0
0
1
0
0
0
1
0
1
0
1
1
1
0
1
0
0
1
1
1
0
1
0
0
0
1
...

output:

510
849 0
849 0
849 1
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 1
849 0
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #13:

score: 85
Accepted
time: 213ms
memory: 6188kb
Overall Time Limit: 2965ms

input:

1
1000000000
684392485
1
1
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
0
0
0
1
0
0
1
0
1
1
1
0
0
0
1
0
0
0
1
1
1
0
0
0
0
0
1
0
0
1
1
1
0
0
0
1
0
0
0
1
0
0
0
0
1
0
1
1
1
1
1
1
0
1
0
1
1
0
0
1
1
0
1
1
0
0
0
0
0
0
1
0
1
1
1
1
1
1
1
1
1
0
0
1
1000000000
235162311
0
0
0
1
0
0
0
0
1
0
0
1
1
1
0
1
0
0
1
0
0
0
0
0
0
0
1
...

output:

510
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 1
84...

input:

1
1000000000
872874714
1
1
1
1
1
1
0
0
1
1
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
0
0
0
1
1
0
0
1
0
1
0
0
0
1
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
1000000000
52798983
0
0
0
1
0
0
0
0
1
0
0
1
1
1
0
1
0
0
1
0
0
0
0
0
0
0
1
0...

output:

510
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 1
849 0
849 1
849 0
84...

input:

1
1000000000
694087436
1
1
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
0
0
0
1
0
0
1
0
1
1
1
0
0
0
1
0
0
0
1
1
1
0
0
0
0
0
1
0
0
1
1
1
0
0
0
1
0
0
0
1
0
0
0
0
1
0
1
1
1
1
1
1
0
1
0
1
1
0
0
1
1
0
1
1
0
0
0
0
0
0
1
0
1
1
1
1
1
1
1
1
1
0
0
1
1000000000
737327485
0
0
0
1
0
0
0
0
1
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
...

output:

510
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 1
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #14:

score: 85
Accepted
time: 201ms
memory: 6240kb
Overall Time Limit: 2955ms

input:

1
1000000000
684392485
1
1
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
0
0
0
1
0
0
1
0
1
1
1
0
0
0
1
0
0
0
1
1
1
0
0
0
0
0
1
0
0
1
1
1
0
0
0
1
0
0
0
1
0
0
0
0
1
0
1
1
1
1
1
1
0
1
0
1
1
0
0
1
1
0
1
1
0
0
0
0
0
0
1
0
1
1
1
1
1
1
1
1
1
0
0
1
1000000000
235162311
0
0
0
1
0
0
0
0
1
0
0
1
1
1
0
1
0
0
1
0
0
0
0
0
0
0
1
...

output:

510
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 1
84...

input:

1
1000000000
872874714
1
1
1
1
1
1
0
0
1
1
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
0
0
0
1
1
0
0
1
0
1
0
0
0
1
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
1000000000
52798983
0
0
0
1
0
0
0
0
1
0
0
1
1
1
0
1
0
0
1
0
0
0
0
0
0
0
1
0...

output:

510
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 1
849 0
849 1
849 0
84...

input:

1
1000000000
694087436
1
1
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
0
0
0
1
0
0
1
0
1
1
1
0
0
0
1
0
0
0
1
1
1
0
0
0
0
0
1
0
0
1
1
1
0
0
0
1
0
0
0
1
0
0
0
0
1
0
1
1
1
1
1
1
0
1
0
1
1
0
0
1
1
0
1
1
0
0
0
0
0
0
1
0
1
1
1
1
1
1
1
1
1
0
0
1
1000000000
737327485
0
0
0
1
0
0
0
0
1
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
...

output:

510
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 1
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #15:

score: 85
Accepted
time: 219ms
memory: 6212kb
Overall Time Limit: 2960ms

input:

1
1000000000
684392485
1
1
1
1
1
1
0
0
1
1
0
1
1
0
0
0
1
0
0
0
1
1
1
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
1
0
0
1
0
0
0
1
1
1
0
0
0
0
1
0
0
1
0
1
1
0
1
0
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
0
1
0
0
0
0
1
1
0
0
1
0
1
1
1
1
0
0
0
0
1
0
0
1
1000000000
235162311
0
0
0
1
0
0
0
0
1
0
0
1
1
1
0
1
0
1
1
1
0
0
1
0
1
1
0
...

output:

510
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
84...

input:

1
1000000000
872874714
1
1
1
1
1
1
0
0
1
1
0
1
1
0
0
0
1
0
0
0
1
1
1
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
1
0
0
1
0
0
0
1
1
1
0
0
0
0
1
0
0
1
0
1
1
0
1
0
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
0
1
0
0
0
0
1
1
0
0
1
0
1
1
1
1
0
0
0
0
1
0
0
1
1000000000
52798983
0
0
0
1
0
0
0
0
1
0
0
1
1
1
0
1
0
1
1
1
0
0
1
0
1
1
0
1...

output:

510
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
84...

input:

1
1000000000
694087436
1
1
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
0
1
1
0
1
1
0
1
1
1
1
0
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
0
1
1
0
1
1
1
1
0
1
1
1
0
1
0
1
0
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1000000000
737327485
0
0
0
1
0
0
0
0
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
0
1
1
...

output:

510
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 1
849 0
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #16:

score: 85
Accepted
time: 152ms
memory: 6220kb
Overall Time Limit: 1210ms

input:

1
1000000000
755120568
1
1
1
1
1
1
0
1
1
1
0
1
0
1
0
1
1
0
0
0
0
1
1
1
1
1
1
1
0
0
1
0
1
1
1
1
1
1
1
0
1
0
1
0
0
1
0
0
1
1
0
0
0
1
0
0
1
0
1
0
1
0
0
0
0
1
0
1
0
1
1
1
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
1
0
1
1
1
0
1
1
1
1000000000
755120568
1
1
1
1
1
1
0
1
1
1
0
1
0
1
0
1
1
0
0
0
0
1
1
1
1
1
1
...

output:

510
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
84...

input:

1
1000000000
614457618
1
1
1
1
1
1
0
1
1
1
0
1
0
1
0
1
1
0
0
0
0
1
1
1
1
1
1
1
0
0
1
0
1
1
1
1
1
1
1
0
1
0
1
0
0
1
0
0
1
1
0
0
0
1
0
0
1
0
1
0
1
0
0
0
0
1
0
1
0
1
1
1
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
1
0
1
1
1
0
1
1
1
1000000000
614457618
1
1
1
1
1
1
0
1
1
1
0
1
0
1
0
1
1
0
0
0
0
1
1
1
1
1
1
...

output:

510
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #17:

score: 85
Accepted
time: 156ms
memory: 5968kb
Overall Time Limit: 1050ms

input:

1
1000000000
295341091
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
1
0
1
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1000000000
135439260
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
0
1
1
0
1
1
...

output:

510
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 1
849 0
849 1
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #18:

score: 85
Accepted
time: 160ms
memory: 6232kb
Overall Time Limit: 2300ms

input:

1
1000000000
448772181
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
1
1
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
1
1
0
0
1
0
1
1
0
0
0
1
1
1
0
0
0
0
1
1
0
0
0
0
1
0
0
0
0
0
1
0
1
0
1
0
1
0
0
0
1
0
1
1
0
1
0
1
1
0
0
0
0
0
1
0
0
0
1
1000000000
183638812
0
1
0
0
1
0
1
1
1
0
0
1
0
1
0
0
0
0
0
1
0
0
0
0
0
1
1
...

output:

510
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 1
849 1
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #19:

score: 85
Accepted
time: 163ms
memory: 6004kb
Overall Time Limit: 1255ms

input:

1
1000000000
143098526
0
0
1
1
1
1
0
0
0
0
1
1
1
0
0
0
0
1
0
0
1
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
1
1
1
0
0
1
1
1
1
1
1
1
0
0
1
0
1
0
0
0
0
0
1
0
1
0
1
1
0
0
1
1
1
0
0
1
1000000000
143098526
0
0
1
1
1
1
0
0
0
0
1
1
1
0
0
0
0
1
0
0
1
0
0
1
0
0
1
...

output:

510
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 1
84...

input:

1
1000000000
237847677
0
0
1
1
1
1
0
0
0
0
1
1
1
0
0
0
0
1
0
0
1
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
1
1
1
0
0
1
1
1
1
1
1
1
0
0
1
0
1
0
0
0
0
0
1
0
1
0
1
1
0
0
1
1
1
0
0
1
1000000000
237847677
0
0
1
1
1
1
0
0
0
0
1
1
1
0
0
0
0
1
0
0
1
0
0
1
0
0
1
...

output:

510
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 1
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #20:

score: 85
Accepted
time: 157ms
memory: 6236kb
Overall Time Limit: 1250ms

input:

1
1000000000
143098526
0
0
1
1
1
1
0
0
0
0
1
1
1
0
0
0
0
1
0
0
1
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
1
1
1
0
0
1
1
1
1
1
1
1
0
0
1
0
1
0
0
0
0
0
1
0
1
0
1
1
0
0
1
1
1
0
0
1
1000000000
143098526
0
0
1
1
1
1
0
0
0
0
1
1
1
0
0
0
0
1
0
0
1
0
0
1
0
0
1
...

output:

510
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 1
84...

input:

1
1000000000
237847677
0
0
1
1
1
1
0
0
0
0
1
1
1
0
0
0
0
1
0
0
1
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
1
1
1
0
0
1
1
1
1
1
1
1
0
0
1
0
1
0
0
0
0
0
1
0
1
0
1
1
0
0
1
1
1
0
0
1
1000000000
237847677
0
0
1
1
1
1
0
0
0
0
1
1
1
0
0
0
0
1
0
0
1
0
0
1
0
0
1
...

output:

510
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 1
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #21:

score: 85
Accepted
time: 138ms
memory: 5944kb
Overall Time Limit: 250ms

input:

1
1337
42
0
1
0
1
0
0
0
0
0
1
1
0
0
1
1
1
0
1
0
0
1
1
1
0
1
1
1
1
1
0
1
1
0
0
1
0
1
0
1
0
0
1
1
1
0
0
0
0
1
1
1
0
1
0
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
0
1
1
1
0
0
0
0
0
0
1
1
1
0
0
1
0
1
1
0
1
0
1
0
1
1
1
1
1
1
1
1337
42
0
1
0
1
0
0
0
0
0
1
1
0
0
1
1
1
0
1
0
0
1
1
1
0
1
1
1
1
1
0
1
1
0
0
1
0
1
0
1
0
...

output:

510
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 1
849 1
849 1
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #22:

score: 85
Accepted
time: 157ms
memory: 6012kb
Overall Time Limit: 1230ms

input:

1
1000000000
458314021
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
0
1
0
0
1
1
1
1
1
1
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
1
1000000000
458314021
0
0
0
0
0
0
1
1
1
1
1
0
1
1
0
0
0
0
1
0
0
1
1
1
1
1
1
...

output:

510
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
84...

input:

1
1000000000
437207149
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
0
1
0
0
1
1
1
1
1
1
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
1
1000000000
437207149
0
0
0
0
0
0
1
1
1
1
1
0
1
1
0
0
0
0
1
0
0
1
1
1
1
1
1
...

output:

510
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 1
849 0
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #23:

score: 85
Accepted
time: 204ms
memory: 6220kb
Overall Time Limit: 3210ms

input:

1
1000000000
993192100
1
1
0
1
0
1
1
1
0
1
0
1
1
0
0
0
0
1
0
1
1
0
1
0
1
1
0
1
1
0
0
0
0
1
1
0
0
1
0
0
0
0
1
1
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
1
1
0
1
0
0
0
0
0
0
0
1
0
1
0
1
0
1
1
1
0
0
0
0
1
0
1
1
0
0
0
0
1
0
0
0
1
1
0
1
1
1
1000000000
884727289
0
1
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
1
1
1
0
0
0
...

output:

510
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 1
84...

input:

1
1000000000
990822595
1
1
0
1
0
1
1
1
0
1
0
1
1
0
0
0
0
1
0
1
1
0
1
0
1
1
0
1
1
0
0
0
0
1
1
0
0
1
0
0
0
0
1
1
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
1
1
0
1
0
0
0
0
0
0
0
1
0
1
0
1
0
1
1
1
0
0
0
0
1
0
1
1
0
0
0
0
1
0
0
0
1
1
0
1
1
1
1000000000
751258761
0
1
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
1
1
1
0
0
0
...

output:

510
849 1
849 0
849 0
849 1
849 1
849 1
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 1
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #24:

score: 85
Accepted
time: 147ms
memory: 5928kb
Overall Time Limit: 1300ms

input:

1
1000000000
541788479
1
1
0
0
1
0
0
0
1
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
1
1
0
0
1
0
0
0
1
0
0
1
1
1
0
0
1
0
0
0
1
1
0
0
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
0
1
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
0
1
1
0
0
0
1
1000000000
871205524
0
1
0
0
0
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
0
...

output:

510
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #25:

score: 85
Accepted
time: 172ms
memory: 6172kb
Overall Time Limit: 4995ms

input:

1
1000000000
576564152
1
1
1
0
1
0
1
1
1
1
0
0
1
0
0
0
0
1
1
1
1
0
1
0
1
0
1
1
1
0
0
0
0
0
0
1
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
1
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
1
0
1
0
1
0
1
1
1
1
1
1
1
0
0
1
1000000000
576564152
1
1
1
0
1
0
0
1
1
1
0
0
0
1
1
0
0
1
1
1
1
1
1
0
0
0
0
...

output:

510
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
84...

input:

1
1000000000
484828360
1
1
1
0
1
0
1
1
1
1
0
0
1
0
0
0
0
1
1
1
1
0
1
0
1
0
1
1
1
0
0
0
0
0
0
1
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
1
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
1
0
1
0
1
0
1
1
1
1
1
1
1
0
0
1
1000000000
484828360
1
1
1
0
1
0
0
1
1
1
0
0
0
1
1
0
0
1
1
1
1
1
1
0
0
0
0
...

output:

510
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #26:

score: 85
Accepted
time: 182ms
memory: 5912kb
Overall Time Limit: 2000ms

input:

1
1000000000
883386153
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
1000000000
278730866
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
1
...

output:

510
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 1
849 0
849 1
849 0
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #27:

score: 85
Accepted
time: 200ms
memory: 6240kb
Overall Time Limit: 1220ms

input:

1
1000000000
755120568
1
1
1
1
1
1
0
1
1
1
0
1
0
1
0
1
1
0
0
0
0
1
1
1
1
1
1
1
0
0
1
0
1
1
1
1
1
1
1
0
1
0
1
0
0
1
0
0
1
1
0
0
0
1
0
0
1
0
1
0
1
0
0
0
0
1
0
1
0
1
1
1
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
1
0
1
1
1
0
1
1
1
1000000000
755120568
1
1
1
1
1
1
0
1
1
1
0
1
0
1
0
1
1
0
0
0
0
1
1
1
1
1
1
...

output:

510
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
84...

input:

1
1000000000
614457618
1
1
1
1
1
1
0
1
1
1
0
1
0
1
0
1
1
0
0
0
0
1
1
1
1
1
1
1
0
0
1
0
1
1
1
1
1
1
1
0
1
0
1
0
0
1
0
0
1
1
0
0
0
1
0
0
1
0
1
0
1
0
0
0
0
1
0
1
0
1
1
1
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
1
0
1
1
1
0
1
1
1
1000000000
614457618
1
1
1
1
1
1
0
1
1
1
0
1
0
1
0
1
1
0
0
0
0
1
1
1
1
1
1
...

output:

510
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #28:

score: 85
Accepted
time: 154ms
memory: 6192kb
Overall Time Limit: 1710ms

input:

1
1000000000
182158063
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
1
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
1
1000000000
854157332
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
...

output:

510
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #29:

score: 85
Accepted
time: 201ms
memory: 6228kb
Overall Time Limit: 2355ms

input:

1
1000000000
2321558
1
0
0
1
0
0
0
0
0
0
0
0
1
1
1
1
1
0
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
1
0
1
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
1
1
0
0
0
1
0
1
0
1
1
0
0
1
1
0
0
0
0
0
0
0
1
1
0
1
1
1
0
0
1
1
1
1
1
1
1
1
1
0
0
1
1000000000
2321558
1
0
0
1
0
0
0
0
0
0
0
0
1
1
1
1
1
0
1
1
1
1
1
0
0
0
0
0
0
...

output:

510
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 1
849 0
849 1
849 0
849 0
849 0
84...

input:

1
1000000000
821874523
1
0
0
1
0
0
0
0
0
0
0
0
1
1
1
1
1
0
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
1
0
1
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
1
1
0
0
0
1
0
1
0
1
1
0
0
1
1
0
0
0
0
0
0
0
1
1
0
1
1
1
0
0
1
1
1
1
1
1
1
1
1
0
0
1
1000000000
821874523
1
0
0
1
0
0
0
0
0
0
0
0
1
1
1
1
1
0
1
1
1
1
1
0
0
0
0
...

output:

510
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 0
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #30:

score: 85
Accepted
time: 234ms
memory: 6220kb
Overall Time Limit: 2960ms

input:

1
1000000000
684392485
1
1
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
0
0
0
1
0
0
1
0
1
1
1
0
0
0
1
0
0
0
1
1
1
0
0
0
0
0
1
0
0
1
1
1
0
0
0
1
0
0
0
1
0
0
0
0
1
0
1
1
1
1
1
1
0
1
0
1
1
0
0
1
1
0
1
1
0
0
0
0
0
0
1
0
1
1
1
1
1
1
1
1
1
0
0
1
1000000000
235162311
0
0
0
1
0
0
0
0
1
0
0
1
1
1
0
1
0
0
1
0
0
0
0
0
0
0
1
...

output:

510
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 1
84...

input:

1
1000000000
872874714
1
1
1
1
1
1
0
0
1
1
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
0
0
0
1
1
0
0
1
0
1
0
0
0
1
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
1000000000
52798983
0
0
0
1
0
0
0
0
1
0
0
1
1
1
0
1
0
0
1
0
0
0
0
0
0
0
1
0...

output:

510
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 1
849 0
849 1
849 0
84...

input:

1
1000000000
694087436
1
1
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
0
0
0
1
0
0
1
0
1
1
1
0
0
0
1
0
0
0
1
1
1
0
0
0
0
0
1
0
0
1
1
1
0
0
0
1
0
0
0
1
0
0
0
0
1
0
1
1
1
1
1
1
0
1
0
1
1
0
0
1
1
0
1
1
0
0
0
0
0
0
1
0
1
1
1
1
1
1
1
1
1
0
0
1
1000000000
737327485
0
0
0
1
0
0
0
0
1
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
...

output:

510
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 1
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0

Test #31:

score: 85
Accepted
time: 183ms
memory: 6244kb
Overall Time Limit: 2965ms

input:

1
1000000000
684392485
1
1
1
1
1
1
0
0
1
1
0
1
1
0
0
0
1
0
0
0
1
1
1
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
1
0
0
1
0
0
0
1
1
1
0
0
0
0
1
0
0
1
0
1
1
0
1
0
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
0
1
0
0
0
0
1
1
0
0
1
0
1
1
1
1
0
0
0
0
1
0
0
1
1000000000
235162311
0
0
0
1
0
0
0
0
1
0
0
1
1
1
0
1
0
1
1
1
0
0
1
0
1
1
0
...

output:

510
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
84...

input:

1
1000000000
872874714
1
1
1
1
1
1
0
0
1
1
0
1
1
0
0
0
1
0
0
0
1
1
1
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
1
0
0
1
0
0
0
1
1
1
0
0
0
0
1
0
0
1
0
1
1
0
1
0
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
0
1
0
0
0
0
1
1
0
0
1
0
1
1
1
1
0
0
0
0
1
0
0
1
1000000000
52798983
0
0
0
1
0
0
0
0
1
0
0
1
1
1
0
1
0
1
1
1
0
0
1
0
1
1
0
1...

output:

510
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
84...

input:

1
1000000000
694087436
1
1
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
0
1
1
0
1
1
0
1
1
1
1
0
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
0
1
1
0
1
1
1
1
0
1
1
1
0
1
0
1
0
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1000000000
737327485
0
0
0
1
0
0
0
0
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
0
1
1
...

output:

510
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 1
849 0
84...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

input:

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

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
...

result:

points 1.0