A. Покраска рисунка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рисунок можно представить в виде таблицы $$$n\times m$$$ ($$$n$$$ строк, $$$m$$$ столбцов), при этом каждая из $$$n \cdot m$$$ клеток будет покрашена в один из цветов. У вас есть $$$k$$$ красок различных цветов. Количество каждой краски ограниченно, а именно, вы можете покрасить не более $$$a_i$$$ клеток в $$$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» (без кавычек), если можно создать красивый рисунок. Иначе выведите «No» (без кавычек).

Пример
Входные данные
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
Выходные данные
Yes
No
Yes
Yes
No
No
Примечание

В первом примере одно из возможных решений следующее:

В третьем примере можно покрасить все клетки в $$$1$$$-й цвет.