Notice:Don't output extra spaces at the end of one line.
Dodo bird is jogging on an infinite 2-d plane, starting from (x0,y0). For a point(x,y), it is regarded as good if and only if gcd(x,y)>1.
Dodo bird will walk infinite steps on the plane under the following strategy:
Assume he is currently at (x,y), let S be the set of good points among (x−1,y−1),(x−1,y),(x−1,y+1),(x,y−1),(x,y+1),(x+1,y−1),(x+1,y),(x+1,y+1), z be the size of S. He has a probability of 1z+1 to stay in (x,y), and he also has a probility of zz+1 to move to a point in S. If he chooses to move, the probility of going to any point in S is equal.
Define pt as the probability of coming back to (x0,y0) after walking t steps, please calculate limt→∞pt. It is guaranteed that the answer always exists.