Given an integer $n$, consider an $n \times n$ grid of light bulbs that are initially all turned off.

You are given a $2$D array of lamp positions lamps, where lamps[i] = [row_i, col_i] indicates that there is an active lamp at cell [row_i, col_i]. Each active lamp illuminates every cell in its row, its column, and both of its diagonals.

You are also given a $2$D array of query coordinates queries, where queries[j] = [row_j, col_j]. For the $j$th query:

1. Check whether cell [row_j, col_j] is currently illuminated. If it is illuminated, the answer is $1$; otherwise, the answer is $0$.

2. Turn off any lamp situated at [row_j, col_j] or in any of its $8$ neighboring cells (horizontal, vertical, and diagonal neighbors sharing a common vertex or edge with [row_j, col_j]).

Return an array of integers representing the answers to all queries in order.

Constraints:

• $1 \le n \le 10^9$

• $0 \le$ lamps.length $\le 20000$

• lamps[i].length $= 2$

• $0 \leq \text{row}_i, \text{col}_i < n$

• $0 \le$ queries.length $\le 20000$

• queries[j].length $= 2$

• $0 \leq \text{row}_j, \text{col}_j < n$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.