## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Color the Picture Codeforces Solution

C. Color the Picture
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A picture can be represented as an $n×m$ grid ($n$ rows and $m$ columns) so that each of the $n\cdot m$ cells is colored with one color. You have $k$ pigments of different colors. You have a limited amount of each pigment, more precisely you can color at most ${a}_{i}$ cells with the $i$-th pigment.

A picture is considered beautiful if each cell has at least $3$ toroidal neighbors with the same color as itself.

Two cells are considered toroidal neighbors if they toroidally share an edge. In other words, for some integers $1\le {x}_{1},{x}_{2}\le n$ and $1\le {y}_{1},{y}_{2}\le m$, the cell in the ${x}_{1}$-th row and ${y}_{1}$-th column is a toroidal neighbor of the cell in the ${x}_{2}$-th row and ${y}_{2}$-th column if one of following two conditions holds:

• ${x}_{1}-{x}_{2}\equiv ±1\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n\right)$ and ${y}_{1}={y}_{2}$, or
• ${y}_{1}-{y}_{2}\equiv ±1\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}m\right)$ and ${x}_{1}={x}_{2}$.

Notice that each cell has exactly $4$ toroidal neighbors. For example, if $n=3$ and $m=4$, the toroidal neighbors of the cell $\left(1,2\right)$ (the cell on the first row and second column) are: $\left(3,2\right)$$\left(2,2\right)$$\left(1,3\right)$$\left(1,1\right)$. They are shown in gray

Solution Click Below:-  👉
👇👇👇👇👇

on the image below:

The gray cells show toroidal neighbors of $\left(1,2\right)$.

Is it possible to color all cells with the pigments provided and create a beautiful picture?

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le {10}^{4}$). The description of the test cases follows.

The first line of each test case contains three integers $n$$m$, and $k$ ($3\le n,m\le {10}^{9}$$1\le k\le {10}^{5}$) — the number of rows and columns of the picture and the number of pigments.

The next line contains $k$ integers ${a}_{1},{a}_{2},\dots ,{a}_{k}$ ($1\le {a}_{i}\le {10}^{9}$) — ${a}_{i}$ is the maximum number of cells that can be colored with the $i$-th pigment.

It is guaranteed that the sum of $k$ over all test cases does not exceed ${10}^{5}$.

Output

For each test case, print "Yes" (without quotes) if it is possible to color a beautiful picture. Otherwise, print "No" (without quotes).