|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
There is a matrix $X$ with $ n \times m $ cells where each cell has an associated weight. A subset $S$ of cells is considered connected if, between every pair of cells in $S$, there is a path of neighboring cells, also in $S$, that joins them. Two cells are considered neighboring if they share a side. The weight of a subset $S$ is the sum of the weights of the cells that are in $S$.
You are asked to answer several queries, where each query has a weight of $k$. For each query, determine whether there is a connected subset whose weight is between $k$ and $ 2 \cdot k$ (inclusive).
Input
First line contains two integers $n$ and $m$ ($ 1 \leq n \times m \leq 10^5 $).
Then $n$ lines each with $m$ integers. The $j$-th number in the $i$-th line represents the weight of the cell $ X[i, j]$ ($ 1 \leq X [i, j] \leq 10^9 $).
Output
For each question, print "YES" if the solution exists, or "NO" otherwise.
Sample test(s)
Input
3 4
1 1 9 2
9 9 9 9
1 1 9 1
10
1
2
3
4
5
6
7
8
9
10
Output
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
Input
5 5
8 9 1 9 4
941 942 8 4 2
5 939 921 978 914
932 1 8 9 4
7 3 6 5 10
4
450
58
20
10
Output
NO
NO
YES
YES