Challenge 3D Tetris

Time Limit: 1 Second    Memory Limit: 32768 KB

Tetris is one of the few games that achieve ultimate popularity. It is remarkably simple, yet remarkably difficult. It's been ported to every computer and game console known to man, and has sold millions of copies across the land.

Today we are talking about a 3D Tetris game. The game goes on pretty much the same with conventional Tetris game, but you have more freedom with the pieces in that you can rotate in x-y plane, y-z plane or z-x plane. Flipping is also allowed. All the pieces descend along the z-axis, until any block of the descending piece encounters another block or the bottom of the space. A fully filled x-y plane will be removed and some points will be granted.

The pieces are constructed with cubic blocks of the same size. Two blocks are connected if they share a same face. A valid piece should have all the blocks in one component. Since we are free to rotate and flip the pieces, some of them are in fact equivalent to each other. Observing such rules, we can calculate the number of distinct valid pieces of n blocks. For instance, we have two distinct pieces constructed with three blocks, and seven distinct pieces constructed with four blocks.

Some times in order to make some extra fun, the game can generate a random configuration at start. Some layers of blocks will appear on the bottom of the space. As the game goes on, at the moment you reduce all the blocks (both the originally generated ones and the ones later filled into the space), you win a special bonus.

As the designer of such rules, I am well aware of the fact that some random generated configuration will never lead to the special bonus. That is why I need a program to verify it. And after some tedious case study, I believe the possibility is only related to the number of blocks generated, the area of the x-y plane and the piece types used. Now here goes your job.

Input

The first line of the input is an integer N (N <= 10000), which is the total number of test cases.

Each test case occupies one line in the input. The first integer is the area of the x-y place, the next integer is the number of generated blocks. The third integer is n (n <= 10), which is the number of piece types. We do allow mixed piece types in one game. The last n integers are the number of blocks in each type. These n integers are distinct.

During the game, the pieces are generated randomly, but all valid according to the rules above.

All the numbers in the input will fit into a 64-bit unsigned integer, unless declared otherwise.

Output

Print one line for each test case, either the word YES when a special bonus is achievable, or NO otherwise.

Sample Input

2
4 2 1 2
4 1 2 1 2

Sample Output

YES
YES

Submit

Source: Zhejiang University Local Contest 2003