You are playing a simple tower defense game.
The game is played on an infinite square grid. At the beginning of the game the entire grid is empty, except for
two cells. The cell
Before the invaders arrive you may build up to
The invaders can move in four cardinal directions and always follow the shortest path from the entrance to your
home. For your master plan, you require that distance to be exactly
Input
The first line of input contains two integers: the coordinates
The second line of input contains two integers: the coordinates
The third line of input contains one integer: the desired distance
The cells
Output
If there is no solution, output a single line with the text impossible
.
If there are multiple solutions, you may output any one of them. The first line of output should contain the number
All coordinates of all turrets must be between
The checker for this task will also accept solutions that output additional and/or different whitespace between the numbers in the output.
Scoring
Subtask
Subtask
Subtask
Sample Input 1
10 10
20 20
14
Sample Output 1
impossible
Explanation Of Sample 1
In the first example the current distance from the entrance to your home is already
Sample Input 2
10 20
10 50
32
Sample Output 2
2
10 47
-1000000003 -5
Explanation Of Sample 2
In the second example the invaders have to go around the turret at
Sample Input 3
0 0
4 0
8
Sample Output 3
6
1 0
1 1
1 2
3 0
3 -1
4 -2
Explanation Of Sample 3
The third example output is shown below, using E
for the entrance, H
for the home and asterisks for turrets.
.......
..*....
..*....
.E*.*H.
....*..
.....*.
.......
Comments