An evil villain, Diamond Bomber, is attacking BinaryLand with bombs! Fortunately, of the 10 residents of BinaryLand, only one was killed and the other resident, Mr. B, managed to take shelter underground before the attack. When he emerged above ground, he found that BinaryLand was blown to bits (well, it was in bits before the attack but you get the idea).
It is your job as a member of the rescue team to code a program to work out the shortest path for Mr. B to take to get to the rescue zone from his shelter (he can only travel left, right, up or down). However, there are a few problems:
You do not know what the current layout of BinaryLand is, but you know about the bombs that have exploded.
There are three types of bombs:
Type 1: Changes all values caught in bomb's radius to
Type 2: Changes all values caught in bomb's radius to
Type 3: FLIPS all values caught in bomb's radius (
becomes , becomes )The Diamond Bomber's bombs explode in a diamond pattern (surprise!)
E.g. Bomb of Radius
Type 1Copy000010000 000111000 001111100 000111000 000010000
Distances in BinaryLand are calculated through binary, so the shortest path has the shortest distance when the path is converted from binary to a base
integer.E.g. If the path from the shelter to the rescue area is
, the binary number is (with the starting point as last digit) and the distance will be after converting to a base integer.
The fate of Mr. B lies in your hands, Good Luck!
Note: The default layout of BinaryLand is all
Input Specification
The first line of input has 3 integers:
The next line of input has 4 integers:
The next
Output Specification
A single integer stating the shortest distance from the shelter to the rescue area
This is because numbers may become too large to fit in an integer or a long long.
Constraints
Subtask 1 [30%]
Subtask 2 [70%]
Subtask 3 [0%]
Sample test cases.
Sample Input 1
5 5 2
0 0 4 4
1 2 2 2
2 2 2 1
Sample Output 1
68
Explanation
After the bombs exploded, this is the layout of BinaryLand:
00100
01010
10001
01010
00100
The shortest distance from shelter
Sample Input 2
25 25 5
3 8 24 24
1 15 17 6
3 6 24 4
3 23 11 7
2 18 20 4
1 22 17 5
Sample Output 2
0
Comments