The “square game” is a very popular game nowadays! The game is very simple: you are given a grid with **N** lines and **M** columns containing non-negative integer numbers. The following image shows a grid with 3 lines and 4 columns.

You are also given an integer **S**. You must then choose some square with **S** lines and **S** columns contained entirely in the grid. Your score is given by the product of all integers inside the square you chose. For example, if **S**=2 and you decided to choose the square shown in blue in the given image, your score will be equal to 2×3×2×1 = 12.

You just realized that, depending on the square you choose, your score may be equal to zero. You are given a grid and a list of queries. For each query, you are given an integer **S** and must decide whether it is possible to choose a **S**x**S** square such that your score is not equal to zero.

## Input

The first line contains two integers **N** and **M** (1 ≤ **N**, **M** ≤ 200) indicating the number of lines and columns of the grid. The next **N** lines contain **M** integers each, indicating the grid. Each integer in the grid is not greater than 10^{9}.

The next line contains an integer **Q** (1 ≤ **Q** ≤ 200) indicating the number of queries. Each of the next **Q** lines describes a query. Each line contains an integer **S** (1 ≤ **S** ≤ min(**N**,**M**)), the length of the square you must choose.

## Output

For each query, print a single line containing **yes** if it is possible to choose a square such that your score is not equal to zero, or **no** otherwise.

Input Sample | Output Sample |

3 4 3 4 0 3 0 2 3 1 4 2 1 0 3 2 3 1 |
yes no yes |

solution:

<br /> #include <bits/stdc++.h> #define ll long long using namespace std; int main() { int n, m, q; int grid[205][205]; int dp[205][205]; int maior = 0; memset(dp, 0, sizeof dp); cin >> n >> m; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> grid[i][j]; if(grid[i][j] == 0) { dp[i][j] = 0; } else { dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1; maior = max(maior, dp[i][j]); } } } cin >> q; while(q--) { int t; cin >> t; if(t <= maior) printf("yes\n"); else printf("no\n"); } return 0; }