Lamps on a Huge Grid

On an n by n grid, some cells hold switched-on lamps, given as lamps, a list of [row, col] positions. A lamp lights every cell in its row, in its column and on both diagonal lines through it. The same lamp may be listed more than once; it is still one lamp.

Write check_cells(n, lamps, queries). Go through queries (a list of [row, col] cells) in order. For each one, record 1 if the cell is lit and 0 if it is dark, then switch off every lamp in the 3 by 3 block around that cell (the cell itself and its 8 neighbours). Return the list of recorded answers.

Examples

check_cells(5, [[0, 0], [4, 4]], [[1, 1], [1, 0]])
# returns [1, 0]

check_cells(5, [[0, 0], [4, 4]], [[1, 1], [1, 1]])
# returns [1, 1]

check_cells(5, [[0, 0], [0, 4]], [[0, 4], [0, 1], [1, 4]])
# returns [1, 1, 0]

In the first example [1, 1] is on the diagonal of both lamps, so it is lit, and then the lamp at [0, 0] is switched off. The cell [1, 0] shares no row, column or diagonal with the lamp at [4, 4], so it is dark.

Constraints

• 1 <= n <= 10**9
• 0 <= len(lamps) <= 20,000 and 0 <= len(queries) <= 20,000
• Every position is inside the grid