[思维]Color the Picture Codeforces1711C

A picture can be represented as an n×mn×m grid (nn rows and mm columns) so that each of the n⋅mn⋅m cells is colored with one color. You have kk pigments of different colors. You have a limited amount of each pigment, more precisely you can color at most aiai cells with the ii-th pigment.

A picture is considered beautiful if each cell has at least 33 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≤x1,x2≤n1≤x1,x2≤n and 1≤y1,y2≤m1≤y1,y2≤m, the cell in the x1x1-th row and y1y1-th column is a toroidal neighbor of the cell in the x2x2-th row and y2y2-th column if one of following two conditions holds:

• x1−x2≡±1(modn)x1−x2≡±1(modn) and y1=y2y1=y2, or
• y1−y2≡±1(modm)y1−y2≡±1(modm) and x1=x2x1=x2.

Notice that each cell has exactly 44 toroidal neighbors. For example, if n=3n=3 and m=4m=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 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 tt (1≤t≤1041≤t≤104). The description of the test cases follows.

The first line of each test case contains three integers nn, mm, and kk (3≤n,m≤1093≤n,m≤109, 1≤k≤1051≤k≤105) — the number of rows and columns of the picture and the number of pigments.

The next line contains kk integers a1,a2,…,aka1,a2,…,ak (1≤ai≤1091≤ai≤109) — aiai is the maximum number of cells that can be colored with the ii-th pigment.

It is guaranteed that the sum of kk over all test cases does not exceed 105105.

Output

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

Example

input

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

output 

Yes

No

Yes

Yes

No

No

题意： 给出一张n*m的图片，用k种染料进行染色，要求每个格子至少有三个同色的相邻格子，每种染料能涂ai个格子，问是否存在一种染色方案。

分析： 比较显然的是符合题意的图片一定是横着涂或者是竖着涂，所以分别看下是否存在符合要求的方案。对于每种颜色可以求出能涂多少道，只有道数大于等于2的颜色才能参与涂色，否则就不符合题意了。如果所有颜色的道数加和大于等于n或m那就能够染色，不过这里有种特殊情况，也就是样例二那种情况，当n或m为奇数时要考虑最后一种颜色会不会被卡住，如果颜色的道数全是2，那显然会被卡，但只要出现一个大于2的颜色，就不会被卡住。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#define int long long
using namespace std;
 
int h[100005], l[100005];
 
signed main()
{
	int T;
	cin >> T;
	while(T--){
		int n, m, k;
		scanf("%lld%lld%lld", &n, &m, &k);
		for(int i = 1; i <= k; i++){
			int t;
			scanf("%lld", &t);
			h[i] = t/m;
			l[i] = t/n;
		}
		bool sh, sl;
		sh = sl = false;
		int hsum = 0;
		for(int i = 1; i <= k; i++){
			if(h[i] >= 2) hsum += h[i];
			if(h[i] > 2) sh = true;  
		}
		int lsum = 0; 
		for(int i = 1; i <= k; i++){
			if(l[i] >= 2) lsum += l[i];
			if(l[i] > 2) sl = true;
		}
		bool flag = false;
		if(hsum >= n){
			if(n&1){
				if(sh) flag = true;
			}
			else flag = true;
		}
		if(lsum >= m){
			if(m&1){
				if(sl) flag = true;
			}
			else flag = true;
		}
		if(flag) puts("Yes");
		else puts("No");
	}
	return 0;
}