← 返回题目列表

Codeforces · 1710/A

A. 给图片上色

中文机器翻译题面 查看原题

一张图片可以表示为 $$$n\times m$$$ 网格($$$n$$$ 行和 $$$m$$$ 列),以便每个 $$$n \cdot m$$$ 单元格都用一种颜色着色。你有 $$$k$$$ 不同颜色的颜料。每种颜料的数量有限,更准确地说,您最多可以使用第 $$$i$$$ 个颜料为 $$$a_i$$$ 单元格着色。

如果每个单元格至少有 $$$3$$$ 与其颜色相同的环形邻居,则图片被认为是漂亮的。

如果两个单元环形共享边缘,则它们被视为环形邻居。换句话说,对于某些整数 $$$1 \leq x_1,x_2 \leq n$$$ 和 $$$1 \leq y_1,y_2 \leq m$$$,第 $$$x_1$$$ 行和 $$$y_1$$$ 列中的单元是第 $$$x_2$$$ 行和 $$$y_2$$$ 中单元的环形邻居如果满足以下两个条件之一,则列:

- $$$x_1-x_2 \equiv \pm1 \pmod{n}$$$ 和 $$$y_1=y_2$$$,或
- $$$y_1-y_2 \equiv \pm1 \pmod{m}$$$ 和 $$$x_1=x_2$$$。

请注意,每个单元格恰好有 $$$4$$$ 环形邻居。例如,如果 $$$n=3$$$ 且 $$$m=4$$$,则单元格 $$$(1, 2)$$$(第一行第二列的单元格)的环形邻居为:$$$(3, 2)$$$、$$$(2, 2)$$$、$$$(1, 3)$$$、$$$(1, 1)$$$。它们在下图中以灰色显示:

灰色单元格显示 $$$(1, 2)$$$ 的环形邻居。

是否可以使用提供的颜料为所有细胞着色并创作出美丽的图画?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$3 \leq n,m \leq 10^9$$$, $$$1 \leq k \leq 10^5$$$) — 图片的行数和列数以及颜料的数量。

下一行包含 $$$k$$$ 整数 $$$a_1,a_2,\dots, a_k$$$ ($$$1 \leq a_i \leq 10^9$$$) — $$$a_i$$$ 是可以使用第 $$$i$$$ 颜料着色的最大单元数。

保证所有测试用例的 $$$k$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,如果可以为美丽的图片着色,请打印“Yes”(不带引号)。否则,打印“否”(不带引号)。

示例

输入 #1

6
4 6 3
12 9 8
3 3 2
8 8
3 3 2
9 5
4 5 2
10 11
5 4 2
9 11
10 10 3
11 45 14

输出 #1

Yes
No
Yes
Yes
No
No

注意

在第一个测试用例中,一个可能的解决方案如下:

在第三个测试用例中,我们可以使用颜料 $$$1$$$ 为所有单元格着色。