[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\times 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$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≤𝑥1,𝑥2≤𝑛$1\le x_1,x_2\le n$ and 1≤𝑦1,𝑦2≤𝑚$1\le y_1,y_2\le m$, the cell in the 𝑥1$x_1$-th row and 𝑦1$y_1$-th column is a toroidal neighbor of the cell in the 𝑥2$x_2$-th row and 𝑦2$y_2$-th column if one of following two conditions holds:

• 𝑥1−𝑥2≡±1(mod𝑛)$x_1-x_2\equiv \pm 1(\mathrm{mod}n)$ and 𝑦1=𝑦2$y_1=y_2$, or
• 𝑦1−𝑦2≡±1(mod𝑚)$y_1-y_2\equiv \pm 1(\mathrm{mod}m)$ and 𝑥1=𝑥2$x_1=x_2$.

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 on the image below:

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

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≤𝑡≤104$1\le t\le {10}^4$). The description of the test cases follows.

Perfect Permutation Codeforces Solution

Party Codeforces Solution

Color the Picture Codeforces Solution

Rain Codeforces Solution

XOR Triangle Codeforces Solution

The first line of each test case contains three integers 𝑛$n$, 𝑚$m$, and 𝑘$k$ (3≤𝑛,𝑚≤109$3\le n,m\le {10}^9$, 1≤𝑘≤105$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 𝑎1,𝑎2,…,𝑎𝑘$a_1,a_2,\dots ,a_k$ (1≤𝑎𝑖≤109$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 105${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).