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 1
000010000 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 s and all coordinates are -indexed. The value at the shelter and the rescue location must also be considered when working out the shortest path.
Input Specification
The first line of input has 3 integers: , , (representing the height and width of BinaryLand, and the number of bombs respectively)
The next line of input has 4 integers: , , , (representing the coordinates of the shelter and the rescue area respectively)
The next lines contain 4 integers each: , , , (representing the type of bomb, the coordinates of the centre of the bomb, and the bomb radius respectively)
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 to rescue zone is through (shelter) (rescue). The binary number is , which converts to .
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