Taco Path Cost Challenge

You are given a grid with N rows and M columns, where each cell has a positive integer cost. You start from cell (1,1) and want to reach a destination cell (x,y) by only moving right or down. The cost of a path is the sum of the values of all visited cells.

The problem asks you to determine whether the minimum cost path from (1,1) to (x,y) is exactly equal to a given target cost C.

You can compute the minimum cost path by using the following dynamic programming recurrence: $$ \textbf{dp}[i][j] = \min(\textbf{dp}[i-1][j],\; \textbf{dp}[i][j-1]) + grid[i][j] $$ with appropriate boundary conditions:

• \(\textbf{dp}[0][0] = grid[0][0]\)
• For the first row: \(\textbf{dp}[0][j] = \textbf{dp}[0][j-1] + grid[0][j]\)
• For the first column: \(\textbf{dp}[i][0] = \textbf{dp}[i-1][0] + grid[i][0]\)

For each query, check if the computed minimum cost at cell (x, y) equals C. If they are equal, output POSSIBLE, otherwise output IMPOSSIBLE.

inputFormat

The first line contains two integers N and M, the number of rows and columns in the grid.

The next N lines each contain M integers, representing the grid's cell values.

The next line contains an integer Q, the number of queries.

Each of the following Q lines contains three integers: x, y (the destination cell, 1-indexed), and C (the target cost).

outputFormat

For each query, print a single line containing either POSSIBLE if the minimum path cost from cell (1,1) to cell (x,y) is exactly C, or IMPOSSIBLE otherwise.

## sample

3 3
1 2 3
4 5 6
7 8 9
2
3 3 21
2 2 6

POSSIBLE
IMPOSSIBLE

</p>