/**

public int[] hitBricks(int[][] grid, int[][] hits) {

int R = grid.length, C = grid[0].length;

int[] dr = {1, 0, -1, 0};

int[] dc = {0, 1, 0, -1};

int[][] A = new int[R][C];

for (int r = 0; r < R; ++r)

A[r] = grid[r].clone();

for (int[] hit: hits)

A[hit[0]][hit[1]] = 0;

DSU dsu = new DSU(R*C + 1);

for (int r = 0; r < R; ++r) {

for (int c = 0; c < C; ++c) {

if (A[r][c] == 1) {

int i = r * C + c;

if (r == 0)

dsu.union(i, R*C);

if (r > 0 && A[r-1][c] == 1)

dsu.union(i, (r-1) *C + c);

if (c > 0 && A[r][c-1] == 1)

dsu.union(i, r * C + c-1);

}

}

}

int t = hits.length;

int[] ans = new int[t--];

while (t >= 0) {

int r = hits[t][0];

int c = hits[t][1];

int preRoof = dsu.top();

if (grid[r][c] == 0) {

t--;

} else {

int i = r * C + c;

for (int k = 0; k < 4; ++k) {

int nr = r + dr[k];

int nc = c + dc[k];

if (0 <= nr && nr < R && 0 <= nc && nc < C && A[nr][nc] == 1)

dsu.union(i, nr * C + nc);

}

if (r == 0)

dsu.union(i, R*C);

A[r][c] = 1;

ans[t--] = Math.max(0, dsu.top() - preRoof - 1);

}

}

return ans;

}

class DSU {

int[] parent;

int[] rank;

int[] sz;

public DSU(int N) {

parent = new int[N];

for (int i = 0; i < N; ++i)

parent[i] = i;

rank = new int[N];

sz = new int[N];

Arrays.fill(sz, 1);

}

public int find(int x) {

if (parent[x] != x) parent[x] = find(parent[x]);

return parent[x];

}

public void union(int x, int y) {

int xr = find(x), yr = find(y);

if (xr == yr) return;

if (rank[xr] < rank[yr]) {

parent[xr] = yr;

sz[yr] += sz[xr];

} else if (rank[xr] > rank[yr]) {

parent[yr] = xr;

sz[xr] += sz[yr];

} else {

rank[xr]++;

parent[yr] = xr;

sz[xr] += sz[yr];

}

}

public int size(int x) {

return sz[find(x)];

}

public int top() {

return sz[find(sz.length - 1)] - 1;

}

}

/**

public int[] hitBricks2(int[][] grid, int[][] hits) {

if (hits.length == 0 || hits[0].length == 0) return null;

removeHitBrick(grid, hits);

markRemainBricks(grid);

return searchFallingBrick(grid, hits);

}

private void markRemainBricks(int[][] grid) {

for (int i = 0; i < grid[0].length; i++) {

deepSearch(grid, 0, i);

}

}

private void removeHitBrick(int[][] grid, int[][] hits) {

for (int i = 0; i < hits.length; i++) {

grid[hits[i][0]][hits[i][1]] = grid[hits[i][0]][hits[i][1]] - 1;

}

}

private int[] searchFallingBrick(int[][] grid, int[][] hits) {

int[] result = new int[hits.length];

for (int i = hits.length - 1; i >= 0; i--) {

if (grid[hits[i][0]][hits[i][1]] == 0) {

grid[hits[i][0]][hits[i][1]] = 1;

if (isConnectToTop(grid, hits[i][0], hits[i][1])) {

result[i] = deepSearch(grid, hits[i][0], hits[i][1]) - 1;

} else {

result[i] = 0;

}

}

}

return result;

}

private boolean isConnectToTop(int[][] grid, int i, int j) {

if(i == 0) return true;

if (i - 1 >= 0 && grid[i - 1][j] == 2) {

return true;

}

if (i + 1 < grid.length && grid[i + 1][j] == 2) {

return true;

}

if (j - 1 >= 0 && grid[i][j - 1] == 2) {

return true;

}

if (j + 1 < grid[0].length && grid[i][j + 1] == 2) {

return true;

}

return false;

}

private int deepSearch(int[][] data, int row, int column) {

int arrayRow = data.length;

int arrayLine = data[0].length;

int effectBricks = 0;

if (row < 0 || row >= arrayRow) return effectBricks;

if (column < 0 || column >= arrayLine) return effectBricks;

if (data[row][column] == 1) {

data[row][column] = 2;

effectBricks = 1;

effectBricks += deepSearch(data, row + 1, column);

effectBricks += deepSearch(data, row - 1, column);

effectBricks += deepSearch(data, row, column + 1);

effectBricks += deepSearch(data, row, column - 1);

}

return effectBricks;

}