QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#78611#4208. Flight to the Fordwlxhkk100 ✓259ms3788kbC++142.7kb2023-02-19 21:37:142023-02-19 21:37:17

詳細信息

Subtask #1:

score: 15
Accepted

Test #1:

score: 15
Accepted
time: 18ms
memory: 3784kb
Overall Time Limit: 500ms

input:

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

output:

510
849 1
849 0
347
510
849 0
849 0
347
510
849 1
849 0
347
510
849 1
849 0
347
510
849 1
849 0
347
510
849 0
849 0
347
510
849 1
849 0
347
510
849 1
849 0
347
510
849 1
849 0
347
510
849 0
849 0
347
510
849 1
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
...

input:

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

output:

510
849 1
849 0
347
510
849 0
849 0
347
510
849 1
849 0
347
510
849 1
849 0
347
510
849 0
849 1
347
510
849 0
849 0
347
510
849 1
849 0
347
510
849 0
849 1
347
510
849 1
849 0
347
510
849 0
849 0
347
510
849 1
849 0
347
510
849 1
849 0
347
510
849 1
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
...

input:

2
3
0
0
2
3
1
1
2
3
1
0
2
3
1
0
2
3
1
0
2
3
1
1
2
3
0
0
2
3
1
1
2
3
1
0
2
3
1
0
2
3
0
0
2
3
0
0
2
3
0
0
2
3
1
0
2
3
1
0
2
3
0
0
2
3
0
0
2
3
1
0
2
3
1
1
2
3
1
0
-1
-1

output:

510
410
410
167 2 3
510
410
410
167 3 1
510
410
410
167 1 2
510
410
410
167 1 2
510
410
410
167 1 2
510
410
410
167 3 1
510
410
410
167 2 3
510
410
410
167 3 1
510
410
410
167 1 2
510
410
410
167 1 2
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 1 2
510
410
410
167 1 2
...

input:

2
3
0
0
2
3
1
0
2
3
0
0
2
3
1
0
2
3
1
0
2
3
0
0
2
3
1
1
2
3
1
0
2
3
1
0
2
3
0
0
2
3
0
0
2
3
1
1
2
3
1
0
2
3
0
0
2
3
1
0
2
3
1
0
2
3
1
1
2
3
1
1
2
3
0
0
2
3
1
0
-1
-1

output:

510
410
410
167 2 3
510
410
410
167 1 2
510
410
410
167 2 3
510
410
410
167 1 2
510
410
410
167 1 2
510
410
410
167 2 3
510
410
410
167 3 1
510
410
410
167 1 2
510
410
410
167 1 2
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 3 1
510
410
410
167 1 2
510
410
410
167 2 3
510
410
410
167 1 2
...

result:

points 1.0

Test #2:

score: 15
Accepted
time: 9ms
memory: 3632kb
Overall Time Limit: 250ms

input:

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

output:

510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 1
849 0
347
510
849 1
849 0
347
510
849 0
849 1
347
510
849 0
849 0
347
510
849 1
849 0
347
510
849 0
849 1
347

input:

2
3
0
0
2
3
0
0
2
3
1
1
2
3
1
1
2
3
0
0
2
3
1
0
2
3
1
0
2
3
1
0
2
3
0
0
2
3
1
0
-1
-1

output:

510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 3 1
510
410
410
167 3 1
510
410
410
167 2 3
510
410
410
167 1 2
510
410
410
167 1 2
510
410
410
167 1 2
510
410
410
167 2 3
510
410
410
167 1 2

result:

points 1.0

Test #3:

score: 15
Accepted
time: 14ms
memory: 3624kb
Overall Time Limit: 375ms

input:

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

output:

510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 1
849 1
849 0
347
510
849 1
849 1
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 1
849 1
849 0
347
510
849 0
849 0
347
51...

input:

2
3
0
0
2
3
0
0
2
3
0
0
2
3
0
0
2
3
0
0
2
3
0
0
2
3
0
0
2
3
0
1
0
2
3
0
0
2
3
0
0
2
3
0
1
0
2
3
0
1
0
2
3
0
0
2
3
0
0
2
3
0
0
-1
-1

output:

510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
410
167 1 2
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
410
167 1 2
510
410
410
410
167 1 2
510
410
410
167 2 3
510
410
410
167 2 3
510
410
...

result:

points 1.0

Test #4:

score: 15
Accepted
time: 17ms
memory: 3684kb
Overall Time Limit: 500ms

input:

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

output:

510
849 1
849 1
849 0
347
510
849 1
849 0
347
510
849 1
849 1
849 0
347
510
849 0
849 1
347
510
849 0
849 0
347
510
849 1
849 1
849 0
347
510
849 1
849 1
849 0
347
510
849 1
849 0
347
510
849 1
849 0
347
510
849 1
849 0
347
510
849 0
849 0
849 1
347
510
849 0
849 0
347
510
849 0
849 1
347
510
849 1
...

input:

2
3
0
1
1
2
3
0
1
0
2
3
1
0
2
3
1
0
2
3
0
1
1
2
3
1
0
2
3
1
0
2
3
0
0
2
3
0
1
1
2
3
0
1
0
2
3
0
1
0
2
3
0
1
1
2
3
1
1
2
3
0
0
2
3
1
1
2
3
0
1
1
2
3
1
0
2
3
1
1
2
3
1
1
2
3
0
1
0
-1
-1

output:

510
410
410
410
167 3 1
510
410
410
410
167 1 2
510
410
410
167 1 2
510
410
410
167 1 2
510
410
410
410
167 3 1
510
410
410
167 1 2
510
410
410
167 1 2
510
410
410
167 2 3
510
410
410
410
167 3 1
510
410
410
410
167 1 2
510
410
410
410
167 1 2
510
410
410
410
167 3 1
510
410
410
167 3 1
510
410
410
...

result:

points 1.0

Test #5:

score: 15
Accepted
time: 65ms
memory: 3716kb
Overall Time Limit: 2000ms

input:

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

output:

510
849 1
849 1
849 0
347
510
849 0
849 0
347
510
849 1
849 1
849 0
347
510
849 1
849 1
849 0
347
510
849 1
849 1
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
...

input:

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

output:

510
410
410
167 2 3
510
410
410
410
167 1 2
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
410
167 1 2
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
...

result:

points 1.0

Test #6:

score: 15
Accepted
time: 9ms
memory: 3696kb
Overall Time Limit: 250ms

input:

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

output:

510
849 0
849 1
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 1
347
510
849 0
849 0
347
510
849 1
849 1
849 0
347
510
849 1
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 1
849 0
347

input:

2
3
1
0
2
3
1
0
2
3
1
1
2
3
1
0
2
3
1
0
2
3
1
1
2
3
0
1
1
2
3
1
1
2
3
1
0
2
3
1
0
-1
-1

output:

510
410
410
167 1 2
510
410
410
167 1 2
510
410
410
167 3 1
510
410
410
167 1 2
510
410
410
167 1 2
510
410
410
167 3 1
510
410
410
410
167 3 1
510
410
410
167 3 1
510
410
410
167 1 2
510
410
410
167 1 2

result:

points 1.0

Test #7:

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

input:

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

output:

510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347
510
849 0
849 0
347

input:

2
3
0
0
2
3
0
0
2
3
0
0
2
3
0
0
2
3
0
0
2
3
0
0
2
3
0
0
2
3
0
0
2
3
0
0
2
3
0
0
2
3
0
0
2
3
0
0
2
3
0
0
2
3
0
0
2
3
0
0
-1
-1

output:

510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3
510
410
410
167 2 3

result:

points 1.0

Subtask #2:

score: 85
Accepted

Test #8:

score: 85
Accepted
time: 128ms
memory: 3688kb
Overall Time Limit: 2210ms

input:

1
684392489
188482225
1
0
0
0
1
0
0
0
0
0
0
1
0
1
1
0
1
1
0
0
0
0
1
0
0
0
1
1
0
1
1
1
0
0
1
1
1
1
0
0
1
1
0
0
0
1
0
0
0
0
0
0
1
1
0
1
1
0
1
0
0
0
1
0
0
1
1
1
1
1
0
0
1
0
0
1
0
0
1
0
0
1
1
0
1
1
1
0
0
1
1
1
1
1
1
357033893
108863929
0
1
0
1
1
0
0
1
1
0
1
0
1
1
1
0
0
1
0
1
1
0
1
1
0
0
1
1
1
0
1
1
1
1
...

output:

510
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 1
849 1
849 1
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 1
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 0
849 0
849 1
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 0
84...

input:

2
890537277
1
1
1
1
1
0
0
0
0
1
1
0
0
0
0
0
0
1
1
1
0
0
0
1
0
0
0
1
0
1
1
0
0
0
0
0
1
0
0
0
1
0
0
0
1
0
0
1
0
1
0
1
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
1
1
0
1
0
1
1
1
0
1
0
0
1
1
0
1
1
0
0
0
1
0
0
0
0
0
1
1
2
733420435
1
1
0
1
1
0
1
0
0
1
0
1
1
1
0
0
0
1
1
0
0
1
1
0
1
0
1
1
1
0
0
1
0
0
0
0
1
0
0
1
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 #9:

score: 85
Accepted
time: 185ms
memory: 3704kb
Overall Time Limit: 2955ms

input:

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

output:

510
849 0
849 1
849 1
849 1
849 0
849 0
849 0
849 1
849 1
849 1
849 0
849 1
849 1
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 0
849 1
849 1
849 1
849 1
849 0
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 1
84...

input:

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

output:

510
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 0
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 1
849 1
849 1
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 1
84...

input:

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

output:

510
849 0
849 1
849 1
849 1
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 1
849 1
849 1
849 0
849 0
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
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
84...

input:

2
1000000000
0
0
1
0
1
1
1
1
1
1
0
1
0
1
1
0
0
0
1
0
1
1
1
0
1
0
1
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
0
0
2
1000000000
1
0
0
1
0
1
1
1
0
1
0
1
0
0
0
1
1
0
0
0
1
1
0
0
0
1
0
0
0
0
0
1
1
1
1
1
1
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
...

input:

2
1000000000
1
1
1
1
0
0
1
0
0
1
0
0
1
0
1
0
1
0
1
1
1
1
1
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
1
0
0
0
0
0
1
0
0
0
0
0
1
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
2
1000000000
1
1
1
0
1
1
1
1
1
0
0
1
0
0
1
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
...

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
0
0
1
1
0
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
0
0
0
0
0
1
1
1
1
1
1
0
1
1
1
0
1
0
1
1
1
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
1
1
1
0
1
0
0
0
1
1
1
0
0
0
1
1
1
0
1
0
0
0
0
0
1
0
1
1
1
1
1
0
2
1000000000
1
0
1
1
1
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
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 #10:

score: 85
Accepted
time: 133ms
memory: 3700kb
Overall Time Limit: 2020ms

input:

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

output:

510
849 1
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 1
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 0
849 1
849 1
849 1
849 0
849 1
849 0
849 0
849 0
849 1
849 1
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 0
849 1
84...

input:

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

output:

510
849 1
849 1
849 1
849 1
849 0
849 1
849 1
849 1
849 1
849 1
849 0
849 1
849 0
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 1
849 0
849 1
849 0
849 0
849 1
849 1
849 1
849 1
849 1
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 0
849 0
84...

input:

2
1000000000
1
0
1
0
1
1
0
1
0
0
1
0
1
1
1
1
1
1
0
1
1
1
0
0
1
1
1
0
0
1
0
1
1
0
1
0
0
1
1
1
0
1
1
1
1
1
1
1
0
0
1
1
1
0
0
1
0
0
1
0
0
1
1
1
1
1
0
0
1
1
1
1
0
1
0
1
0
1
0
0
1
0
1
0
1
0
1
0
0
0
1
0
0
1
1
0
2
1000000000
1
0
1
1
1
0
1
1
0
1
0
1
0
0
1
1
0
1
1
1
1
1
1
1
0
0
1
0
1
0
1
1
1
1
0
1
1
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
1
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
1
0
0
1
0
0
1
1
0
0
0
1
1
1
0
0
1
0
0
1
1
1
1
1
2
1000000000
1
1
1
1
1
0
0
1
1
1
1
0
1
1
0
1
1
1
0
0
1
1
1
0
1
0
1
0
1
0
1
1
1
0
0
1
1
1
1
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 #11:

score: 85
Accepted
time: 89ms
memory: 3760kb
Overall Time Limit: 1235ms

input:

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

output:

510
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 1
849 1
849 1
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 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 1
84...

input:

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

output:

510
849 1
849 0
849 1
849 1
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
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 1
849 0
849 1
849 0
849 1
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
84...

input:

2
1000000000
1
0
1
0
1
0
1
1
1
0
0
0
1
1
1
1
0
1
1
1
1
0
1
1
0
1
0
1
0
1
1
1
1
1
0
1
1
1
0
1
0
1
0
1
1
0
1
0
1
1
0
1
0
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
1
1
1
0
1
1
0
0
0
0
0
0
0
0
1
1
0
0
1
0
1
1
1
1
0
1
1
2
1000000000
1
0
1
0
1
0
1
1
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
1
1
1
0
0
1
1
1
0
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
...

input:

2
1000000000
1
0
1
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
1
1
1
0
0
1
1
1
1
1
0
1
0
0
1
1
1
1
1
0
0
0
0
1
1
1
0
0
0
0
1
1
1
1
0
1
0
1
1
0
0
0
0
0
0
1
1
0
0
1
1
1
1
1
0
1
1
1
1
1
1
0
0
0
1
0
1
0
1
1
1
0
0
1
1
0
2
1000000000
1
0
1
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
1
1
1
0
0
1
1
1
1
1
0
1
0
0
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 #12:

score: 85
Accepted
time: 143ms
memory: 3764kb
Overall Time Limit: 2500ms

input:

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

output:

510
849 1
849 1
849 1
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 1
849 1
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 1
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 1
849 1
849 0
849 1
849 1
84...

input:

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

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 1
849 0
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 1
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 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 0
84...

input:

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

output:

510
849 1
849 0
849 0
849 0
849 1
849 0
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 1
849 0
849 1
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 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
84...

input:

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

output:

510
849 0
849 1
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
849 0
849 1
849 1
849 0
849 0
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 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 1
849 1
849 0
849 0
84...

input:

2
1000000000
0
0
1
0
0
0
0
0
1
1
0
0
0
1
0
1
1
0
1
0
0
1
0
1
0
0
0
1
1
1
0
0
1
1
0
1
1
0
0
1
1
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
1
1
1
0
1
0
0
1
0
1
0
1
1
1
1
1
0
0
0
1
1
1
1
1
0
0
1
0
0
1
0
2
1000000000
1
1
0
1
0
0
1
1
0
1
0
1
1
1
1
1
0
1
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
1
1
0
1
0
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
...

input:

2
1000000000
1
1
1
0
0
1
1
0
0
0
1
1
1
0
1
1
0
1
1
1
1
1
1
1
0
0
0
0
1
1
1
0
0
0
0
0
1
0
0
1
1
0
1
0
1
0
0
1
1
1
0
1
1
1
0
0
0
0
1
0
1
1
0
1
0
0
0
1
1
1
0
1
1
0
0
0
1
1
0
1
0
0
1
1
0
0
1
1
1
0
1
1
0
1
0
2
1000000000
1
1
1
1
0
1
0
0
1
0
1
0
1
0
1
1
1
1
1
0
0
1
1
0
1
1
1
1
0
0
0
1
0
0
0
1
0
0
1
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
1
0
0
1
1
0
0
1
0
0
0
0
0
0
1
0
0
0
1
0
1
1
0
1
1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0
0
1
0
1
0
0
0
0
1
1
0
0
0
0
0
0
1
0
1
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
0
0
0
0
1
0
0
1
0
0
1
1
1
0
0
0
1
1
1
1
1
2
1000000000
0
0
1
0
0
0
1
0
0
1
0
0
1
1
1
0
0
1
0
1
0
1
0
1
0
0
1
0
1
0
1
0
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
...

input:

2
1000000000
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
1
1
1
1
1
1
0
1
1
0
0
1
0
1
0
1
0
0
1
0
1
0
1
0
0
1
0
0
1
0
1
0
1
1
1
1
0
1
1
1
0
1
1
0
0
0
1
0
0
1
0
1
1
0
1
1
0
0
1
0
1
1
1
0
1
1
1
1
1
0
2
1000000000
0
0
0
1
0
1
0
1
0
0
0
1
1
1
0
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
0
0
0
0
1
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 #13:

score: 85
Accepted
time: 172ms
memory: 3696kb
Overall Time Limit: 2965ms

input:

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

output:

510
849 0
849 1
849 1
849 1
849 0
849 0
849 0
849 1
849 1
849 1
849 0
849 1
849 1
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 0
849 1
849 1
849 1
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 1
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 1
84...

input:

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

output:

510
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 0
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 1
849 1
849 1
849 1
849 0
849 1
849 1
849 0
849 0
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
849 0
849 0
849 0
849 0
849 0
84...

input:

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

output:

510
849 0
849 1
849 1
849 1
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 1
849 1
849 1
849 0
849 0
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
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 1
849 0
84...

input:

2
1000000000
0
0
1
0
1
1
1
1
1
1
0
1
0
1
1
0
0
0
1
0
1
1
1
0
1
0
1
0
0
0
1
1
1
0
0
1
0
1
0
1
0
0
1
1
0
0
0
1
0
0
1
1
1
0
0
1
0
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
1
0
0
1
0
0
0
1
1
2
1000000000
1
0
0
1
0
0
1
0
1
0
0
1
0
0
0
0
0
1
0
1
0
1
0
1
0
0
1
0
0
0
1
1
1
1
1
1
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
...

input:

2
1000000000
1
1
1
1
0
0
1
0
0
1
0
0
1
0
1
0
1
0
1
1
1
1
1
1
0
0
1
0
1
0
1
0
0
1
0
0
1
0
0
1
1
1
0
0
1
0
1
0
0
0
0
1
0
0
1
0
0
1
0
1
0
1
0
0
0
0
0
1
0
0
0
0
1
0
1
0
1
0
1
0
0
1
1
1
1
1
0
0
1
0
0
0
0
2
1000000000
1
1
1
0
1
1
1
1
1
1
1
0
0
1
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
1
0
1
0
0
1
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
1
0
0
1
0
0
0
0
1
0
1
0
0
1
0
0
1
0
0
0
0
0
1
1
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
0
0
0
0
1
0
0
1
1
1
1
1
0
0
1
0
0
1
1
0
0
1
0
1
0
1
0
0
0
0
0
1
1
1
0
0
1
0
0
1
1
0
0
1
0
0
1
0
1
1
1
0
2
1000000000
1
0
1
1
1
0
1
1
0
0
0
0
0
0
1
1
0
1
1
1
1
1
1
1
1
1
0
0
1
0
1
1
1
1
1
1
1
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 #14:

score: 85
Accepted
time: 172ms
memory: 3760kb
Overall Time Limit: 2955ms

input:

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

output:

510
849 0
849 1
849 1
849 1
849 0
849 0
849 0
849 1
849 1
849 1
849 0
849 1
849 1
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 0
849 1
849 1
849 1
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 1
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 1
84...

input:

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

output:

510
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 0
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 1
849 1
849 1
849 1
849 0
849 1
849 1
849 0
849 0
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
849 0
849 0
849 0
849 0
849 0
84...

input:

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

output:

510
849 0
849 1
849 1
849 1
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 1
849 1
849 1
849 0
849 0
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
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 1
849 0
84...

input:

2
1000000000
0
0
1
0
1
1
1
1
1
1
0
1
0
1
1
0
0
0
1
0
1
1
1
0
1
0
1
0
0
0
1
1
1
0
0
1
0
1
0
1
0
0
1
1
0
0
0
1
0
0
1
1
1
0
0
1
0
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
1
0
0
1
0
0
0
1
1
2
1000000000
1
0
0
1
0
0
1
0
1
0
0
1
0
0
0
0
0
1
0
1
0
1
0
1
0
0
1
0
0
0
1
1
1
1
1
1
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
...

input:

2
1000000000
1
1
1
1
0
0
1
0
0
1
0
0
1
0
1
0
1
0
1
1
1
1
1
1
0
0
1
0
1
0
1
0
0
1
0
0
1
0
0
1
1
1
0
0
1
0
1
0
0
0
0
1
0
0
1
0
0
1
0
1
0
1
0
0
0
0
0
1
0
0
0
0
1
0
1
0
1
0
1
0
0
1
1
1
1
1
0
0
1
0
0
0
0
2
1000000000
1
1
1
0
1
1
1
1
1
1
1
0
0
1
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
1
0
1
0
0
1
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
1
0
0
1
0
0
0
0
1
0
1
0
0
1
0
0
1
0
0
0
0
0
1
1
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
0
0
0
0
1
0
0
1
1
1
1
1
0
0
1
0
0
1
1
0
0
1
0
1
0
1
0
0
0
0
0
1
1
1
0
0
1
0
0
1
1
0
0
1
0
0
1
0
1
1
1
0
2
1000000000
1
0
1
1
1
0
1
1
0
0
0
0
0
0
1
1
0
1
1
1
1
1
1
1
1
1
0
0
1
0
1
1
1
1
1
1
1
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 #15:

score: 85
Accepted
time: 193ms
memory: 3704kb
Overall Time Limit: 2960ms

input:

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

output:

510
849 0
849 1
849 1
849 1
849 0
849 0
849 0
849 1
849 1
849 1
849 0
849 1
849 1
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 0
849 1
849 1
849 1
849 1
849 0
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 1
84...

input:

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

output:

510
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 0
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 1
849 1
849 1
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 1
84...

input:

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

output:

510
849 0
849 1
849 1
849 1
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 1
849 1
849 1
849 0
849 0
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
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
84...

input:

2
1000000000
0
0
1
0
1
1
1
1
1
1
0
1
0
1
1
0
0
0
1
0
1
1
1
0
1
0
1
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
0
0
2
1000000000
1
0
0
1
0
1
1
1
0
1
0
1
0
0
0
1
1
0
0
0
1
1
0
0
0
1
0
0
0
0
0
1
1
1
1
1
1
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
...

input:

2
1000000000
1
1
1
1
0
0
1
0
0
1
0
0
1
0
1
0
1
0
1
1
1
1
1
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
1
0
0
0
0
0
1
0
0
0
0
0
1
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
2
1000000000
1
1
1
0
1
1
1
1
1
0
0
1
0
0
1
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
...

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
0
0
1
1
0
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
0
0
0
0
0
1
1
1
1
1
1
0
1
1
1
0
1
0
1
1
1
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
1
1
1
0
1
0
0
0
1
1
1
0
0
0
1
1
1
0
1
0
0
0
0
0
1
0
1
1
1
1
1
0
2
1000000000
1
0
1
1
1
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
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 #16:

score: 85
Accepted
time: 71ms
memory: 3760kb
Overall Time Limit: 1210ms

input:

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

output:

510
849 0
849 0
849 1
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 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 1
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 1
849 1
849 0
849 1
849 1
849 1
849 0
84...

input:

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

output:

510
849 0
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 1
849 1
849 0
849 1
849 1
849 1
849 0
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 1
849 1
849 1
849 0
849 1
849 1
84...

input:

2
1000000000
0
0
0
0
1
0
1
0
0
1
1
1
1
0
0
1
0
1
1
0
0
1
0
0
0
0
0
1
1
1
0
1
1
0
1
1
0
1
1
1
0
0
1
0
0
1
1
0
1
1
0
0
0
0
0
1
0
1
1
1
0
0
1
1
0
1
0
1
1
1
0
0
0
0
1
0
1
1
0
0
0
1
1
1
0
1
1
0
0
1
0
1
1
0
2
1000000000
0
0
0
0
1
0
1
0
0
1
0
0
1
0
0
0
0
0
1
1
1
1
0
0
0
1
0
0
1
1
1
0
0
1
1
0
1
0
1
1
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
0
0
1
1
1
1
1
1
1
1
1
0
0
1
0
1
1
0
1
0
1
0
0
0
1
0
1
1
1
0
1
0
0
0
1
0
0
1
0
1
0
0
0
1
1
0
0
0
1
0
0
0
0
1
1
0
1
1
1
0
0
0
1
0
0
0
1
0
1
0
1
1
1
0
0
1
1
0
0
0
0
1
1
1
1
0
0
0
1
0
0
0
1
0
2
1000000000
0
1
0
0
0
0
1
0
0
1
1
1
1
0
0
1
0
1
1
0
1
1
0
1
1
1
0
0
0
0
0
0
0
1
0
1
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: 69ms
memory: 3704kb
Overall Time Limit: 1050ms

input:

1
1000000000
295341091
0
1
0
0
0
0
0
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
0
0
0
1
0
0
1
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
1
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
1000000000
135439260
1
1
1
1
1
1
1
1
1
1
0
1
1
1
0
1
0
1
0
1
0
1
1
1
0
1
0
1
1
1
0
1
...

output:

510
849 1
849 1
849 0
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 1
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 1
849 1
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 1
84...

input:

2
1000000000
0
0
0
1
0
0
0
1
0
1
0
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
1
1
0
1
0
1
1
1
0
1
0
1
1
1
0
1
1
1
0
1
1
1
0
1
0
1
1
1
0
1
1
1
1
1
0
1
1
1
0
1
0
1
1
2
1000000000
1
0
0
1
0
1
1
0
0
1
0
1
1
1
0
1
0
0
1
0
0
1
0
0
1
0
0
1
1
0
1
0
0
1
1
0
1
0
1
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 #18:

score: 85
Accepted
time: 103ms
memory: 3656kb
Overall Time Limit: 2300ms

input:

1
1000000000
448772181
1
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
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
1
0
0
0
1
0
1
0
0
0
0
0
1
0
0
0
0
1
1000000000
183638812
0
0
0
0
1
0
0
1
1
0
0
0
0
1
0
1
0
0
1
1
0
0
0
1
0
1
0
1
0
0
1
1
...

output:

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

input:

2
1000000000
0
0
1
1
1
0
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
1
1
0
0
0
1
0
0
1
0
0
1
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
1
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
1
0
1
0
1
0
0
1
0
2
1000000000
0
1
1
1
0
1
0
1
1
1
0
1
0
1
1
1
0
1
1
1
0
1
1
1
0
1
0
1
1
1
1
1
1
1
1
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
...

result:

points 1.0

Test #19:

score: 85
Accepted
time: 91ms
memory: 3784kb
Overall Time Limit: 1255ms

input:

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

output:

510
849 1
849 1
849 1
849 1
849 1
849 0
849 0
849 1
849 0
849 1
849 1
849 1
849 1
849 1
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 1
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
84...

input:

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

output:

510
849 1
849 1
849 1
849 0
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 1
849 0
849 1
849 0
849 0
849 0
849 1
849 1
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 0
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 1
849 0
84...

input:

2
1000000000
1
1
1
1
1
0
1
1
0
1
1
1
1
0
0
1
1
0
1
1
0
0
1
1
0
0
0
0
0
0
1
1
1
1
0
1
1
1
0
1
1
0
0
0
0
1
0
0
1
1
0
0
0
1
0
0
1
1
0
0
0
0
1
0
1
1
1
0
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
0
0
0
1
1
0
1
1
1
1
2
1000000000
1
1
1
0
1
1
1
0
0
0
0
0
1
0
1
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
1
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
1
1
1
0
1
1
1
0
0
0
0
1
1
0
1
0
1
0
1
1
1
0
0
0
0
1
1
0
1
1
1
1
0
0
1
0
1
1
0
1
0
1
0
0
1
1
1
0
1
1
0
0
0
1
1
0
0
0
1
0
1
0
1
0
0
0
1
0
1
0
0
1
0
1
1
1
1
1
1
1
0
0
1
1
1
0
0
0
0
0
1
1
1
1
0
2
1000000000
1
1
1
0
1
1
1
0
0
0
0
0
1
0
1
0
0
1
0
0
0
0
1
0
1
0
0
1
0
0
1
0
1
1
1
0
1
0
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 #20:

score: 85
Accepted
time: 82ms
memory: 3692kb
Overall Time Limit: 1250ms

input:

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

output:

510
849 1
849 1
849 1
849 1
849 1
849 0
849 0
849 1
849 0
849 1
849 1
849 1
849 1
849 1
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 1
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
84...

input:

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

output:

510
849 1
849 1
849 1
849 0
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 1
849 0
849 1
849 0
849 0
849 0
849 1
849 1
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 0
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 1
849 0
849 0
849 1
849 0
84...

input:

2
1000000000
1
1
1
1
1
0
1
1
0
1
1
1
1
0
0
1
1
0
1
1
0
0
1
1
0
0
0
0
0
0
1
1
1
1
0
1
1
1
0
1
1
0
0
0
0
1
0
0
1
1
0
0
0
1
0
0
1
1
0
0
0
0
1
0
1
1
1
0
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
0
0
0
1
1
0
1
1
1
1
2
1000000000
1
1
1
0
1
1
1
0
0
0
0
0
1
0
1
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
1
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
1
1
1
0
1
1
1
0
0
0
0
1
1
0
1
0
1
0
1
1
1
0
0
0
0
1
1
0
1
1
1
1
0
0
1
0
1
1
0
1
0
1
0
0
1
1
1
0
1
1
0
0
0
1
1
0
0
0
1
0
1
0
1
0
0
0
1
0
1
0
0
1
0
1
1
1
1
1
1
1
0
0
1
1
1
0
0
0
0
0
1
1
1
1
0
2
1000000000
1
1
1
0
1
1
1
0
0
0
0
0
1
0
1
0
0
1
0
0
0
0
1
0
1
0
0
1
0
0
1
0
1
1
1
0
1
0
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 #21:

score: 85
Accepted
time: 17ms
memory: 3700kb
Overall Time Limit: 250ms

input:

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

output:

510
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 0
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 1
849 0
347
510
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 0
849 0
849 0
...

input:

2
1337
0
0
0
0
0
1
1
1
0
0
0
0
1
0
1
0
0
1
0
1
1
0
1
0
1
0
1
0
1
1
0
2
1337
0
0
0
0
0
1
1
1
0
0
0
0
1
0
1
0
0
1
0
1
1
0
1
0
1
0
1
0
1
1
0
2
1337
0
0
0
0
0
1
1
1
0
0
0
0
1
0
1
0
0
1
0
1
1
0
1
0
1
0
1
0
1
1
0
2
1337
0
0
0
0
0
1
1
1
0
0
0
0
1
0
1
0
0
1
0
1
1
0
1
0
1
0
1
0
1
1
0
2
1337
0
0
0
0
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
167 44 42
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
167 44 42
510
410
410
410
410
410
...

result:

points 1.0

Test #22:

score: 85
Accepted
time: 98ms
memory: 3780kb
Overall Time Limit: 1230ms

input:

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

output:

510
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 1
849 1
849 1
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 0
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 1
84...

input:

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

output:

510
849 1
849 0
849 1
849 1
849 1
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 0
849 0
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 1
849 0
849 1
849 0
849 1
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
84...

input:

2
1000000000
1
0
1
0
1
0
1
1
1
0
0
0
1
1
1
1
0
1
1
1
1
0
1
1
0
1
0
1
0
1
1
1
1
1
0
1
1
1
0
1
0
1
0
1
1
0
1
0
1
1
0
1
0
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
1
1
1
0
1
1
0
0
0
0
0
0
0
0
1
1
0
0
1
0
1
1
1
1
0
1
1
2
1000000000
1
0
1
0
1
0
1
1
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
1
1
1
0
0
1
1
1
0
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
...

input:

2
1000000000
1
0
1
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
1
1
1
0
0
1
1
1
1
1
0
1
0
0
1
1
1
1
1
0
0
0
0
1
1
1
0
0
0
0
1
1
1
1
0
1
0
1
1
0
0
0
0
0
0
1
1
0
0
1
1
1
1
1
0
1
1
1
1
1
1
0
0
0
1
0
1
0
1
1
1
0
0
1
1
0
2
1000000000
1
0
1
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
1
1
1
0
0
1
1
1
1
1
0
1
0
0
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 #23:

score: 85
Accepted
time: 176ms
memory: 3788kb
Overall Time Limit: 3210ms

input:

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

output:

510
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 1
849 1
849 1
849 1
849 1
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 1
849 0
849 0
849 0
849 0
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 1
849 0
849 1
849 1
849 1
84...

input:

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

output:

510
849 0
849 0
849 1
849 0
849 0
849 0
849 1
849 1
849 1
849 1
849 1
849 1
849 1
849 1
849 0
849 1
849 0
849 1
849 1
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 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 0
84...

input:

2
1000000000
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
1
0
1
0
0
1
0
0
1
1
1
0
0
1
0
0
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
2
1000000000
1
1
1
1
0
1
0
0
1
1
1
0
0
1
0
1
0
1
0
0
0
1
1
1
0
0
1
1
0
1
0
1
1
1
0
0
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
1
0
1
0
1
0
0
1
0
1
1
1
1
0
1
1
0
1
1
1
0
0
1
1
1
0
0
1
0
0
1
1
1
1
0
1
0
1
1
1
1
0
1
0
1
1
0
1
0
0
1
0
1
0
1
1
0
1
1
0
1
0
1
0
1
1
0
1
1
0
1
0
1
0
1
1
0
1
1
1
0
0
0
1
1
1
0
1
0
2
1000000000
1
0
1
0
1
0
1
0
1
1
1
1
0
1
1
1
0
0
1
1
0
0
1
0
0
1
0
1
0
1
1
1
0
1
0
0
1
0
1
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 #24:

score: 85
Accepted
time: 105ms
memory: 3764kb
Overall Time Limit: 1300ms

input:

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

output:

510
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 1
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 1
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 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
84...

input:

2
1000000000
1
1
0
1
1
0
0
0
0
1
0
0
1
1
0
1
1
0
0
0
0
1
1
0
1
1
0
1
1
0
0
0
1
1
0
0
1
1
1
0
1
1
0
1
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
0
1
1
1
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
2
1000000000
0
1
1
1
1
1
1
0
0
1
0
1
1
0
1
0
1
1
0
1
0
0
1
1
1
1
1
1
0
1
0
1
0
0
1
0
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 #25:

score: 85
Accepted
time: 259ms
memory: 3708kb
Overall Time Limit: 4995ms

input:

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

output:

510
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 1
849 0
849 1
849 1
849 0
849 1
849 1
849 1
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 1
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 1
849 0
849 1
849 1
849 1
849 0
849 0
849 0
849 1
849 0
84...

input:

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

output:

510
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 0
849 0
849 0
849 1
849 1
849 1
849 0
849 0
849 0
849 1
849 0
849 0
849 1
849 1
849 1
849 1
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 1
849 1
849 0
849 1
849 1
849 1
849 0
849 1
849 1
849 1
849 1
849 0
849 1
84...

input:

2
1000000000
1
0
0
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
1
0
1
1
0
1
1
1
1
0
1
1
0
0
1
1
0
0
1
1
1
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
1
0
1
1
1
0
0
1
1
1
1
1
0
0
1
0
1
1
1
1
0
0
0
1
1
0
0
0
0
0
1
1
1
1
1
1
1
0
2
1000000000
0
1
0
0
0
0
1
1
0
0
1
0
0
1
1
1
1
0
0
1
1
0
1
0
0
1
0
1
1
0
0
1
1
1
1
1
0
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
...

input:

2
1000000000
0
1
1
1
0
0
1
1
1
1
0
0
1
0
0
1
1
1
0
0
1
1
1
0
1
1
0
1
1
0
0
1
0
0
0
1
1
1
0
0
1
1
0
0
1
0
1
1
0
1
1
0
1
1
1
1
0
0
1
0
0
1
1
0
1
1
1
1
0
1
0
0
1
0
1
1
1
0
1
1
0
1
0
1
0
0
1
0
0
1
1
0
0
0
1
1
2
1000000000
1
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
0
1
1
0
1
1
0
0
1
0
1
1
0
0
1
1
0
0
0
1
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 #26:

score: 85
Accepted
time: 123ms
memory: 3648kb
Overall Time Limit: 2000ms

input:

1
1000000000
883386153
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
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
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
1000000000
278730866
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
...

output:

510
849 0
849 0
849 1
849 1
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 1
849 1
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 1
849 1
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 1
849 0
849 0
849 1
849 0
849 0
849 1
849 0
84...

input:

2
1000000000
0
0
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
0
0
0
1
0
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
0
0
2
1000000000
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
0
0
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 #27:

score: 85
Accepted
time: 81ms
memory: 3764kb
Overall Time Limit: 1220ms

input:

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

output:

510
849 0
849 0
849 1
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 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 1
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 1
849 1
849 0
849 1
849 1
849 1
849 0
84...

input:

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

output:

510
849 0
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 1
849 1
849 1
849 0
849 1
849 1
849 1
849 0
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 1
849 1
849 1
849 0
849 1
849 1
84...

input:

2
1000000000
0
0
0
0
1
0
1
0
0
1
1
1
1
0
0
1
0
1
1
0
0
1
0
0
0
0
0
1
1
1
0
1
1
0
1
1
0
1
1
1
0
0
1
0
0
1
1
0
1
1
0
0
0
0
0
1
0
1
1
1
0
0
1
1
0
1
0
1
1
1
0
0
0
0
1
0
1
1
0
0
0
1
1
1
0
1
1
0
0
1
0
1
1
0
2
1000000000
0
0
0
0
1
0
1
0
0
1
0
0
1
0
0
0
0
0
1
1
1
1
0
0
0
1
0
0
1
1
1
0
0
1
1
0
1
0
1
1
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
0
0
1
1
1
1
1
1
1
1
1
0
0
1
0
1
1
0
1
0
1
0
0
0
1
0
1
1
1
0
1
0
0
0
1
0
0
1
0
1
0
0
0
1
1
0
0
0
1
0
0
0
0
1
1
0
1
1
1
0
0
0
1
0
0
0
1
0
1
0
1
1
1
0
0
1
1
0
0
0
0
1
1
1
1
0
0
0
1
0
0
0
1
0
2
1000000000
0
1
0
0
0
0
1
0
0
1
1
1
1
0
0
1
0
1
1
0
1
1
0
1
1
1
0
0
0
0
0
0
0
1
0
1
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: 102ms
memory: 3700kb
Overall Time Limit: 1710ms

input:

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

output:

510
849 1
849 1
849 1
849 1
849 0
849 0
849 1
849 1
849 1
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 1
849 1
849 1
849 1
849 0
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 1
849 1
849 1
849 1
849 1
849 1
849 1
849 1
849 1
849 1
849 1
849 1
849 1
84...

input:

2
1000000000
0
0
1
1
0
1
1
1
1
1
1
1
0
0
1
0
0
1
0
1
1
1
0
1
1
0
1
0
0
0
1
1
1
0
1
0
0
1
1
1
0
1
0
1
1
1
0
1
1
1
1
1
1
0
1
0
1
1
0
1
0
1
1
1
0
1
1
1
1
1
1
1
0
1
0
1
1
1
0
0
0
1
0
0
1
1
1
0
0
0
1
1
1
0
1
1
2
1000000000
0
1
0
1
1
1
1
1
0
1
0
1
1
0
1
0
0
1
0
1
0
1
1
1
0
0
1
0
0
0
1
0
0
1
1
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
...

result:

points 1.0

Test #29:

score: 85
Accepted
time: 177ms
memory: 3724kb
Overall Time Limit: 2355ms

input:

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

output:

510
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 1
849 0
849 0
849 0
849 0
849 0
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 0
849 1
849 0
849 1
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 0
849 1
84...

input:

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

output:

510
849 0
849 0
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 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 1
849 0
849 0
849 1
849 1
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 1
849 1
849 1
849 1
849 1
84...

input:

2
1000000000
1
1
1
0
0
0
1
0
0
0
1
0
1
1
0
1
0
0
0
1
1
0
1
1
0
0
0
0
1
0
0
1
1
0
0
1
1
1
0
0
1
0
1
0
1
1
1
1
0
0
1
1
1
1
0
0
0
0
0
1
0
1
0
1
1
1
0
1
0
0
0
1
0
0
0
1
0
1
1
0
0
0
1
1
1
1
1
1
0
0
1
0
0
1
1
0
2
1000000000
0
0
1
0
0
0
0
1
0
1
0
0
1
0
1
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
1
0
1
0
1
1
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
1
1
0
0
0
0
0
1
0
1
0
0
1
0
1
0
0
0
1
0
0
1
0
1
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
1
1
0
0
0
1
0
1
0
1
1
0
1
0
0
1
1
0
0
1
1
0
1
1
1
1
1
1
1
1
0
1
0
0
1
1
0
2
1000000000
1
1
0
0
0
1
1
0
0
1
0
1
0
1
0
1
1
0
0
0
1
0
0
0
0
1
1
0
1
0
0
0
1
0
0
0
0
1
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 #30:

score: 85
Accepted
time: 198ms
memory: 3784kb
Overall Time Limit: 2960ms

input:

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

output:

510
849 0
849 1
849 1
849 1
849 0
849 0
849 0
849 1
849 1
849 1
849 0
849 1
849 1
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 0
849 1
849 1
849 1
849 1
849 0
849 0
849 1
849 0
849 0
849 1
849 1
849 1
849 0
849 1
849 1
849 0
849 0
849 0
849 1
84...

input:

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

output:

510
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 0
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 1
849 1
849 1
849 1
849 0
849 1
849 1
849 0
849 0
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
849 0
849 0
849 0
849 0
849 0
84...

input:

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

output:

510
849 0
849 1
849 1
849 1
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 1
849 1
849 1
849 0
849 0
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
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 1
849 0
84...

input:

2
1000000000
0
0
1
0
1
1
1
1
1
1
0
1
0
1
1
0
0
0
1
0
1
1
1
0
1
0
1
0
0
0
1
1
1
0
0
1
0
1
0
1
0
0
1
1
0
0
0
1
0
0
1
1
1
0
0
1
0
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
1
0
0
1
0
0
0
1
1
2
1000000000
1
0
0
1
0
0
1
0
1
0
0
1
0
0
0
0
0
1
0
1
0
1
0
1
0
0
1
0
0
0
1
1
1
1
1
1
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
...

input:

2
1000000000
1
1
1
1
0
0
1
0
0
1
0
0
1
0
1
0
1
0
1
1
1
1
1
1
0
0
1
0
1
0
1
0
0
1
0
0
1
0
0
1
1
1
0
0
1
0
1
0
0
0
0
1
0
0
1
0
0
1
0
1
0
1
0
0
0
0
0
1
0
0
0
0
1
0
1
0
1
0
1
0
0
1
1
1
1
1
0
0
1
0
0
0
0
2
1000000000
1
1
1
0
1
1
1
1
1
1
1
0
0
1
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
1
0
1
0
0
1
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
1
0
0
1
0
0
0
0
1
0
1
0
0
1
0
0
1
0
0
0
0
0
1
1
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
0
0
0
0
1
0
0
1
1
1
1
1
0
0
1
0
0
1
1
0
0
1
0
1
0
1
0
0
0
0
0
1
1
1
0
0
1
0
0
1
1
0
0
1
0
0
1
0
1
1
1
0
2
1000000000
1
0
1
1
1
0
1
1
0
0
0
0
0
0
1
1
0
1
1
1
1
1
1
1
1
1
0
0
1
0
1
1
1
1
1
1
1
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 #31:

score: 85
Accepted
time: 191ms
memory: 3712kb
Overall Time Limit: 2965ms

input:

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

output:

510
849 0
849 1
849 1
849 1
849 0
849 0
849 0
849 1
849 1
849 1
849 0
849 1
849 1
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 0
849 1
849 1
849 1
849 1
849 0
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 1
84...

input:

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

output:

510
849 0
849 0
849 0
849 0
849 1
849 0
849 1
849 1
849 0
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 1
849 1
849 1
849 1
849 0
849 1
849 1
849 0
849 0
849 1
849 1
849 1
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 1
849 1
849 0
849 1
84...

input:

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

output:

510
849 0
849 1
849 1
849 1
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 1
849 1
849 1
849 0
849 0
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
849 1
849 0
849 0
849 1
849 1
849 0
849 1
849 0
849 1
849 0
849 1
849 1
849 0
849 0
84...

input:

2
1000000000
0
0
1
0
1
1
1
1
1
1
0
1
0
1
1
0
0
0
1
0
1
1
1
0
1
0
1
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
0
0
2
1000000000
1
0
0
1
0
1
1
1
0
1
0
1
0
0
0
1
1
0
0
0
1
1
0
0
0
1
0
0
0
0
0
1
1
1
1
1
1
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
...

input:

2
1000000000
1
1
1
1
0
0
1
0
0
1
0
0
1
0
1
0
1
0
1
1
1
1
1
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
1
0
0
0
0
0
1
0
0
0
0
0
1
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
2
1000000000
1
1
1
0
1
1
1
1
1
0
0
1
0
0
1
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
...

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
0
0
1
1
0
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
0
0
0
0
0
1
1
1
1
1
1
0
1
1
1
0
1
0
1
1
1
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
1
1
1
0
1
0
0
0
1
1
1
0
0
0
1
1
1
0
1
0
0
0
0
0
1
0
1
1
1
1
1
0
2
1000000000
1
0
1
1
1
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
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