Life on an Endless Board

In the Game of Life, every square of an endless grid holds a cell that is alive or dead, and the whole grid changes in steps called generations. A cell's neighbours are the 8 squares around it. To go from one generation to the next, all at the same moment:

• a live cell with 2 or 3 live neighbours stays alive, and every other live cell dies;
• a dead cell with exactly 3 live neighbours comes alive.

cells lists the live cells as (x, y) pairs, with no repeats; every other cell is dead. Write life_after(cells, n) that returns the live cells after n generations, as a sorted list of (x, y) tuples.

n can be enormous, up to 10**15. That is only possible because every pattern you will get settles down: within its first 300 generations it reaches a generation that is an exact copy of an earlier generation, possibly moved to another place on the grid. Some patterns die out completely, and an empty grid stays empty.

Examples

life_after([(0, 1), (1, 1), (2, 1)], 1)   # returns [(1, 0), (1, 1), (1, 2)]
life_after([(0, 1), (1, 1), (2, 1)], 2)   # returns [(0, 1), (1, 1), (2, 1)]

glider = [(1, 0), (2, 1), (0, 2), (1, 2), (2, 2)]
life_after(glider, 4)
# returns [(1, 3), (2, 1), (2, 3), (3, 2), (3, 3)]
life_after(glider, 10**12)
# returns [(250000000000, 250000000002), (250000000001, 250000000000), (250000000001, 250000000002), (250000000002, 250000000001), (250000000002, 250000000002)]

The first pattern, a blinker, flips between a row and a column of three cells. The glider turns into a copy of itself moved one square diagonally every 4 generations, so after a trillion generations it has travelled 250 billion squares.

Constraints

• cells has 0 to 100 live cells; 0 <= n <= 10**15.