I - Weighted components

Languages: C, C++, Java, Python, ... (details)

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$).

Then a line with an integer $q$ $(1 \leq q \leq 10^5)$, the number of queries and then $q$ lines with an integer $k$ ($1\leq k \leq 10^{14}$), indicating the weight of each query

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