You are playing Touhou Impershiable Night, a bullet curtain shooting game, and are fighting against Kirisame Marisa, the boss in stage 4B, who launchs master sparks to attack players. Following is a illustration of this scene.

输入描述:

The first line contains one integer , denoting the number of test cases.

For each test case:

The first line contatins three integers , denoting the size of the game region and the number of sparks.

Following  lines each contains four integers , denoting the parameters of given sparks.

It's guaranteed that .

输出描述:

Output one -string  of length  in one line where  iff such autowinning point exists in case  while  iff no such points.

2
1 1 2
1 -1 -1 0
2 -1 0 2
1 1 2
1 -1 -1 0
1 -2 0 1

01

Following are the illustrations of two sample cases.