There is a 2D grid of size n x n where each cell of this grid has a lamp that is initially turned off.

You are given a 2D array of lamp positions lamps, where lamps[i] = [rowi, coli] indicates that the lamp at grid[rowi][coli] is turned on. Even if the same lamp is listed more than once, it is turned on.

When a lamp is turned on, it illuminates its cell and all other cells in the same row, column, or diagonal.

You are also given another 2D array queries, where queries[j] = [rowj, colj]. For the jth query, determine whether grid[rowj][colj] is illuminated or not. After answering the jth query, turn off the lamp at grid[rowj][colj] and its 8 adjacent lamps if they exist. A lamp is adjacent if its cell shares either a side or corner with grid[rowj][colj].

Return an array of integers ans, where ans[j] should be 1 if the cell in the jth query was illuminated, or 0 if the lamp was not.

&nbsp;
Example 1:

Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
Explanation: We have the initial grid with all lamps turned off. In the above picture we see the grid after turning on the lamp at grid[0][0] then turning on the lamp at grid[4][4].
The 0th&nbsp;query asks if the lamp at grid[1][1] is illuminated or not (the blue square). It is illuminated, so set ans[0] = 1. Then, we turn off all lamps in the red square.

The 1st&nbsp;query asks if the lamp at grid[1][0] is illuminated or not (the blue square). It is not illuminated, so set ans[1] = 0. Then, we turn off all lamps in the red rectangle.



Example 2:

Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]
Output: [1,1]


Example 3:

Input: n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]
Output: [1,1,0]


&nbsp;
Constraints:


	1 &lt;= n &lt;= 109
	0 &lt;= lamps.length &lt;= 20000
	0 &lt;= queries.length &lt;= 20000
	lamps[i].length == 2
	0 &lt;= rowi, coli &lt; n
	queries[j].length == 2
	0 &lt;= rowj, colj &lt; n


class Solution:
    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
        rows = collections.Counter()
        cols = collections.Counter()
        diags1 = collections.Counter()
        diags2 = collections.Counter()
        lamps = {tuple(lamp) for lamp in lamps}
        
        for i, j in lamps:
            rows[i] += 1
            cols[j] += 1
            diags1[i + j] += 1
            diags2[i - j] += 1
        
        ans = []
        directions = ((-1, -1), (-1, 0), (-1, 1),
                      (0, -1), (0, 0), (0, 1),
                      (1, -1), (1, 0), (1, 1))
        
        for i, j in queries:
            if rows[i] or cols[j] or diags1[i + j] or diags2[i - j]:
                ans.append(1)
            else:
                ans.append(0)
            
            for di, dj in directions:
                newI, newJ = i + di, j + dj
                if (newI, newJ) not in lamps:
                    continue
                lamps.remove((newI, newJ))
                rows[newI] -= 1
                cols[newJ] -= 1
                diags1[newI + newJ] -= 1
                diags2[newI - newJ] -= 1
        
        return ans
class Solution {
    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        //we take 5 hashmap
        //1st hashmap for row
        HashMap<Integer, Integer> row = new HashMap<>();
        //2nd hashmap for column
        HashMap<Integer, Integer> col = new HashMap<>();
        //3rd hashmap for lower diagonal
        HashMap<Integer, Integer> d1 = new HashMap<>();
        //4th diagonal for upper diagonal
        HashMap<Integer, Integer> d2 = new HashMap<>();
        //5th diagonal for cell no meaning lamp is present at this spot
        HashMap<Integer, Integer> cellno = new HashMap<>();
        
        for(int i = 0;i<lamps.length;i++){
            //get row and column from lamps array
            int row1 = lamps[i][0];
            int col1 = lamps[i][1];
            //place row in row hashmap
            row.put(row1, row.getOrDefault(row1, 0) + 1);
            //place column in col hashmap
            col.put(col1, col.getOrDefault(col1, 0) + 1);
            //place d1 dia in d1
            d1.put((row1+col1), d1.getOrDefault((row1+col1), 0) + 1);
            //place d2 diagonal
            d2.put((row1-col1), d2.getOrDefault((row1-col1), 0) + 1);
            //place cellno in cell no hashmap
            int cell = row1*n+col1;
            cellno.put(cell, cellno.getOrDefault(cell, 0) + 1);
        }
        //direction array which travels in 8 adjacent direction
        int[][] dir = {{-1, 0},{-1, 1},{0, 1},{1, 1},{1, 0},{1, -1},{0, -1},{-1, -1}};
        int[] ans = new int[queries.length];
        //process all queries
        for(int i = 0;i<queries.length;i++){
            int row1 = queries[i][0];
            int col1 = queries[i][1];
            int cell = row1 * n + col1;
            ans[i] = (row.containsKey(row1) || col.containsKey(col1) || d1.containsKey(row1 + col1) || d2.containsKey(row1-col1) || cellno.containsKey(cell))? 1:0;
            //if query has a bulb
            if(cellno.containsKey(cell)){
                
                    int val = cellno.get(cell);
                    
                        cellno.remove(cell);
                    
                    //for row 
                    if(row.containsKey(row1)){
                        int rowval = row.get(row1);
                        rowval-=val;
                        if(rowval == 0){
                            row.remove(row1);
                        }else{
                            row.put(row1, rowval);
                        }    
                    }
                    
                    //for col
                    if(col.containsKey(col1)){
                        int colval = col.get(col1);
                        colval-=val;
                        if(colval == 0){
                            col.remove(col1);
                        }else{
                            col.put(col1, colval);
                        }    
                    }
                    
                    //for d1
                    if(d1.containsKey(row1+col1)){
                        int d1val = d1.get(row1+col1);
                        d1val-=val;
                        if(d1val == 0){
                            d1.remove(row1+col1);
                        }else{
                            row.put((row1+col1), d1val);
                        }    
                    }
                    
                    //for d2
                    if(d2.containsKey(row1 - col1)){
                        int d2val = d2.get(row1-col1);
                        d2val-=val;
                        if(d2val == 0){
                            d2.remove(row1-col1);
                        }else{
                            d2.put((row1-col1), d2val);
                        }    
                    }
            }
            //moves all 8 direction and remove the illumination 
            for(int j = 0;j<dir.length;j++){
                int rowdash = row1 + dir[j][0];
                int coldash = col1 + dir[j][1];
                int cellno1 = rowdash * n + coldash;
                if(cellno.containsKey(cellno1)){
                    int val = cellno.get(cellno1);
                    
                        cellno.remove(cellno1);
                    
                    //for row
                    if(row.containsKey(rowdash)){
                        int rowval = row.get(rowdash);
                        rowval -= val;
                        if(rowval == 0){
                            row.remove(rowdash);
                        }else{
                            row.put(rowdash, rowval);
                        }    
                    }
                    
                    //for col
                    if(col.containsKey(coldash)){
                        int colval = col.get(coldash);
                        colval-=val;
                        if(colval == 0){
                            col.remove(coldash);
                        }else{
                            col.put(coldash, colval);
                        }    
                    }
                    
                    //for d1
                    if(d1.containsKey(rowdash+coldash)){
                        int d1val = d1.get(rowdash+coldash);
                        d1val-=val;
                        if(d1val == 0){
                            d1.remove(rowdash+coldash);
                        }else{
                            row.put((rowdash+coldash), d1val);
                        }    
                    }
                    
                    //for d2
                    if(d2.containsKey(rowdash - coldash)){
                        int d2val = d2.get(rowdash-coldash);
                        d2val-=val;
                        if(d2val == 0){
                            d2.remove(rowdash-coldash);
                        }else{
                            d2.put((rowdash-coldash), d2val);
                        }    
                    }
                    
                    
                }
            }
        }
        
        return ans;
    }
}
class Solution {
public:

    // store info about rows , coulms and diagonal that is illuminated
    // if (i,j) is lamp , then every cell (x,y) is illuminated if
    // x==i (row) || y==j (column) || x+y == i+j (anti diagonal) || x-y == i-j (main diagonal)
    vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {

        vector<int>ans;
        unordered_map<int,int>row,col,mainDiag,antiDiag;
        set<pair<int,int>>s;

        for(auto &l : lamps){
            int x = l[0],y=l[1];
            // Even if the same lamp is listed more than once, it is turned on.
            // To prevent duplicate entries
            if(s.find({x,y}) == s.end())
            {
                row[x]++;
                col[y]++;
                antiDiag[x+y]++;
                mainDiag[x-y]++;
                s.insert({x,y}); // This helps us to get the lamp in O(1)
            }
        }

        for(auto &q : queries)
        {
            // For every query {x,y} do 2 things :
            // 1. Check whether grid[x][y] is illuminated or not, accordingly set answer either to '1' OR '0'
            // 2. if grid is illuminated, turn off the lamps at {x,y} and 8 adjacent lamps = 9 lamps

            int x = q[0],y = q[1];
            if(row[x]>0 or col[y]>0 or antiDiag[x+y]>0 or mainDiag[x-y]>0)
            {
                // illumination
                ans.push_back(1);

                // Turn off the 9 lamps = 1 center and 8 adjacent lamps
                for(int i=-1;i<=1;i++){
                    for(int j=-1;j<=1;j++){

                        int nx = x+i;
                        int ny = y+j;
                        // NxN board, check boundaries condition
                        if(nx >= 0 and nx < n and ny >=0 and ny < n and s.find({nx,ny})!=s.end())
                        {
                            row[nx]--;
                            col[ny]--;
                            antiDiag[nx+ny]--;
                            mainDiag[nx-ny]--;
                            s.erase({nx,ny});
                        }
                    }
                }
            }
            else // No illumination
                ans.push_back(0);
        }
        return ans;
    }
};
var gridIllumination = function(n, lamps, queries) {
    const directions = [[0,0], [-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1]];
    const lampCoord = new Map();    
    const rowHash = {}, colHash = {}, leftDiag = {}, rightDiag = {};
    
    // First, illuminate the lamps
    for (let [r, c] of lamps) {
        if (lampCoord.has(`${r}-${c}`)) continue;
        lampCoord.set(`${r}-${c}`);
        rowHash[r] = rowHash[r] + 1 || 1;
        colHash[c] = colHash[c] + 1 || 1;
        leftDiag[r + c] = leftDiag[r + c] + 1 || 1;
        rightDiag[c - r] = rightDiag[c - r] + 1 || 1;
    }
    
    // Second, query the lamps
    let output = [];
    for (let [row, col] of queries) query(row, col);
    return output;

    function query(row, col) {
        if (rowHash[row] || colHash[col] || leftDiag[row + col] || rightDiag[col - row]) {
            output.push(1);
			// Check 8 adjacent cells
            for (let [r, c] of directions) {
                let newR = row + r, newC = col + c;
                if (newR < 0 || newC < 0 || newR >= n || newC >= n) continue;
                // If the coordinate is a lamp, un-illuminate the lamp
                if (lampCoord.has(`${newR}-${newC}`)) {
                    rowHash[newR]--, colHash[newC]--, leftDiag[newR + newC]--, rightDiag[newC - newR]--;
                    lampCoord.delete(`${newR}-${newC}`);
                }
            }        
        } else output.push(0);
    }    
};
Grid Illumination