Masha has $n$ types of tiles of size $2 \times 2$. Each cell of the tile contains one integer. Masha has an infinite number of tiles of each type.

Masha decides to construct the square of size $m \times m$ consisting of the given tiles. This square also has to be a symmetric with respect to the main diagonal matrix, and each cell of this square has to be covered with exactly one tile cell, and also sides of tiles should be parallel to the sides of the square. All placed tiles cannot intersect with each other. Also, each tile should lie inside the square. See the picture in Notes section for better understanding.

Symmetric with respect to the main diagonal matrix is such a square $s$ that for each pair $(i, j)$ the condition $s[i][j] = s[j][i]$ holds. I.e. it is true that the element written in the $i$-row and $j$-th column equals to the element written in the $j$-th row and $i$-th column.

Your task is to determine if Masha can construct a square of size $m \times m$ which is a symmetric matrix and consists of tiles she has. Masha can use any number of tiles of each type she has to construct the square. Note that she can not rotate tiles, she can only place them in the orientation they have in the input.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 100$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains two integers $n$ and $m$ ($1 \le n \le 100$, $1 \le m \le 100$) — the number of types of tiles and the size of the square Masha wants to construct.

The next $2n$ lines of the test case contain descriptions of tiles types. Types of tiles are written one after another, each type is written on two lines. 

The first line of the description contains two positive (greater than zero) integers not exceeding $100$ — the number written in the top left corner of the tile and the number written in the top right corner of the tile of the current type. The second line of the description contains two positive (greater than zero) integers not exceeding $100$ — the number written in the bottom left corner of the tile and the number written in the bottom right corner of the tile of the current type.

It is forbidden to rotate tiles, it is only allowed to place them in the orientation they have in the input.


-----Output-----

For each test case print the answer: "YES" (without quotes) if Masha can construct the square of size $m \times m$ which is a symmetric matrix. Otherwise, print "NO" (withtout quotes).


-----Example-----
Input
6
3 4
1 2
5 6
5 7
7 4
8 9
9 8
2 5
1 1
1 1
2 2
2 2
1 100
10 10
10 10
1 2
4 5
8 4
2 2
1 1
1 1
1 2
3 4
1 2
1 1
1 1

Output
YES
NO
YES
NO
YES
YES



-----Note-----

The first test case of the input has three types of tiles, they are shown on the picture below. [Image] 

Masha can construct, for example, the following square of size $4 \times 4$ which is a symmetric matrix: $\left. \begin{array}{|c|c|c|c|} \hline 5 & {7} & {8} & {9} \\ \hline 7 & {4} & {9} & {8} \\ \hline 8 & {9} & {5} & {7} \\ \hline 9 & {8} & {7} & {4} \\ \hline \end{array} \right.$

Difficulty: introductory

Starter code:

Solutions:
def is_symmetric(a):
	return a[0][1]==a[1][0]
for _ in range(int(input())):
	def two_ints():
		return list(map(int,input().split()))
	n, m = map(int,input().split())
	tiles = [[two_ints(),two_ints()] for i in range(n)]
	print("YES" if m%2==0 and any([is_symmetric(tile) for tile in tiles]) else "NO")

import sys

    
def main():
    #n = iinput()
    #k = iinput() 
    #m = iinput() 
    #n = int(sys.stdin.readline().strip()) 
    #n, k = rinput()
    #n, m = rinput()
    #m, k = rinput()
    #n, k, m = rinput()
    #n, m, k = rinput()
    #k, n, m = rinput()
    #k, m, n = rinput() 
    #m, k, n = rinput()
    #m, n, k = rinput()
    #n, t = map(int, sys.stdin.readline().split())
    #q = list(map(int, sys.stdin.readline().split()))
    #q = linput()
    n, m = list(map(int, sys.stdin.readline().split()))
    q = []
    for i in range(n):
        q.append([list(map(int, sys.stdin.readline().split())), list(map(int, sys.stdin.readline().split()))])
    if m % 2:
        print("NO")
    else:
        fl = 0
        for i in range(n):
            if q[i][0][1] == q[i][1][0]:
                fl = 1
                break
        if fl:
            print("YES")
        else:
            print("NO")
    
    
           
        
            
    
    
    
    
    
    
            
                
        
    
            
        

            
        
    
                
    
    
    
            
    
        
    

for i in range(int(sys.stdin.readline().strip()) ):
    main()
    


def solve():
    n, m = list(map(int, input().split()))
    
    found = False
    for _ in range(n):
        a, b = list(map(int, input().split()))
        c, d = list(map(int, input().split()))
        if b==c:
            found = True
    
    if m%2==1:
        return False
    if found:
        return True
    return False
    

t = int(input())

for _ in range(t):
    if solve():
        print("YES")
    else:
        print("NO")


def solve():
    n, m = list(map(int, input().split()))
    sym = False
    for i in range(n):
        x, y = list(map(int, input().split()))
        z, w = list(map(int, input().split()))
        if y == z:
            sym = True
    if m % 2 == 0 and sym:
        print("YES")
    else:
        print("NO")
    return


def main():
    T = int(input())
    for i in range(T):
        solve()
    return


def __starting_point():
    main()


__starting_point()

from collections import *
from heapq import *
from math import *


t = int(input())
while t:
    t -= 1
    # n = int(input())
    flag= False
    n,m =[int(x) for x in input().split()]
    for i in range(n):
        a,b = [int(x) for x in input().split()]
        c,d = [int(x) for x in input().split()]
        if b == c:
            flag = True
    if m%2:
        print("NO")
    elif flag:
        print("YES")
    else:
        print("NO")

# for _ in range(1):
for _ in range(int(input())):
    n, m = map(int, input().split())
    flag = 0

    for i in range(n):
        a, b = map(int, input().split())
        c, d = map(int, input().split())
        if b == c:
            flag = 1
    if m % 2 == 1:
        flag = 0
    if flag:
        print('YES')
    else:
        print('NO')

for _ in range(int(input())):
    n, m = tuple(map(int, input().split()))
    res = False
    for i in range(n):
        a, b = tuple(map(int, input().split()))
        c, d = tuple(map(int, input().split()))
        if b == c:
            res = True

    if m % 2 == 0 and res:
        print('YES')
    else:
        print('NO')


t = int(input())
for j in range(t):
    n, m = list(map(int, input().split()))
    bol = False
    for i in range(n):
        a, b = list(map(int, input().split()))
        c, d = list(map(int, input().split()))
        if b == c:
            bol = True
    if m % 2 == 0 and bol:
        print("YES")
    else:
        print("NO")


for i in ' '*int(input()):
    n,m=map(int,input().split())
    L=[]
    state=False
    for i in ' '*n:
        a,b=map(int,input().split())
        c,d=map(int,input().split())
        if b==c:state=True
    if m%2:state=False
    print(['NO','YES'][state])

import sys
readline = sys.stdin.readline

T = int(readline())
Ans = [None]*T

for qu in range(T):
    N, M = map(int, readline().split())
    ans = 'NO'
    for _ in range(N):
        a, b = map(int, readline().split())
        c, d = map(int, readline().split())
        if b == c:
            ans = 'YES'
    
    if M&1:
        Ans[qu] = 'NO'
        continue
    Ans[qu] = ans
    
print('\n'.join(Ans))

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


for _ in range(val()):
    n, m = li()
    l = []
    middle = 0
    for i in range(n):
        a, b = li()
        c, d = li()
        l.append([a, b, c, d])
        if b == c:middle = 1
    
    if m & 1 or not middle:
        print('NO')
        continue
    
    done = 0
    for i in range(len(l)):
        for j in range(len(l)):
            if l[i][1] == l[j][2] and l[j][1] == l[i][2]:
                done = 1
    print('YES' if done else 'NO')

from sys import stdin, stdout
input = stdin.readline
from collections import defaultdict as dd
import math
def geti(): return list(map(int, input().strip().split()))
def getl(): return list(map(int, input().strip().split()))
def gets(): return input()
def geta(): return int(input())
def print_s(s): stdout.write(s+'\n')

def solve():
    for _ in range(geta()):
        n,m=geti()
        ok=False
        for i in range(n):
            a,b=geti()
            c,d=geti()
            if b==c:
                ok=True
        if ok and m&1==0:
            print("YES")
        else:
            print("NO")



def __starting_point():
    solve()

__starting_point()


from sys import stdin

tt = int(stdin.readline())

for loop in range(tt):

    n,m = map(int,stdin.readline().split())
    ans = "NO"

    for i in range(n):

        a,b = map(int,stdin.readline().split())
        c,d = map(int,stdin.readline().split())

        
        if b == c and m % 2 == 0:
            ans = "YES"

    print (ans)

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    diag = False
    for _ in range(n):
        a, b = map(int, input().split())
        c, d = map(int, input().split())
        if b == c:
            diag = True
    if m % 2 == 1:
        print("NO")
    else:
        print("YES" if diag else "NO")

import sys, math


input = lambda: sys.stdin.readline().rstrip()


def gcd(n, f):
    if n == 0 or f == 0:
        return max(n, f)
    if n > f:
        return gcd(n % f, f)
    else:
        return gcd(f % n, n)


def division_with_remainder_up(pp, ppp):
    return (pp + ppp - 1) // ppp


for _ in range(int(input())):
    n, m = list(map(int, input().split()))
    mas = []
    ans = "NO"
    for i in range(n):
        a, b = list(map(int, input().split()))
        v, c = list(map(int, input().split()))
        if  b == v:
            ans = "YES"
    if m % 2 == 0:
        print(ans)
    else:
        print("NO")


for tc in range(int(input())):
    mainFlag = False
    pairFlag = False
    n, m = map(int, input().split())
    tiles = set()
    for _ in range(n):
        a, b = map(int, input().split())
        c, d = map(int, input().split())
        tile = (a, b, c, d)
        tiles.add(tile)
        if b == c:
            mainFlag = True
            pairFlag = True
        if (a, c, b, d) in tiles:
            pairFlag = True
    if mainFlag and pairFlag and m % 2 == 0:
        print("YES")
    else:
        print("NO")

from math import *
for _ in range(int(input())):
    n, m = list(map(int, input().split()))
    yes = 0
    for i in range(n):
        b = [list(map(int, input().split())), list(map(int, input().split()))]
        if b[0][1] == b[1][0]:
            yes = 1
    if m % 2 == 1:
        print('NO')
    elif yes == 0:
        print('NO')
    else:
        print('YES')



for _ in range(int(input())):
    n, m = list(map(int, input().split()))
    sim = False
    for i in range(n):
        a, b = list(map(int, input().split()))
        c, d = list(map(int, input().split()))
        if c == b:
            sim = True
    if m % 2 == 1:
        print('NO')
    else:
        if sim:
            print('YES')
        else:
            print('NO')


for _ in range (int(input())):
    n,m=map(int,input().split())
    arr=[]
    for i in range(n):
        a,b=map(int,input().split())
        c,d=map(int,input().split())
        arr.append((a,b,c,d))
    if(m%2==1):print("NO")
    else:
        b,x=0,1
        for i in range(n):
            if(arr[i][1]==arr[i][2]):b=1
        if(b==0):x=0
        b=0
        if(m>=4):
            for i in range(n):
                for j in range(n):
                    if(arr[i][1]==arr[j][2] and arr[i][2]==arr[j][1] and arr[i][0]==arr[j][0] and arr[i][3]==arr[j][3]):b=1
            if(b==0):x=0
        if(x==0):print("NO")
        else:print("YES")

# cook your dish here
# code
#    ___________________________________
#   |                                   |
#   |                                   |
#   |        _,     _   _     ,_        |
#   |    .-'` /     \'-'/     \ `'-.    |
#   |   /    |      |   |      |    \   |
#   |  ;      \_  _/     \_  _/      ;  |
#   | |         ``         ``         | |
#   | |                               | |
#   |  ;    .-.   .-.   .-.   .-.    ;  |
#   |   \  (   '.'   \ /   '.'   )  /   |
#   |    '-.;         V         ;.-'    |
#   |        `                 `        |
#   |                                   |
#   |___________________________________|
#   |                                   |
#   |  Author      :   Ramzz            |
#   |  Created On  :   21-07-2020       |
#   |___________________________________|
#
#    _ __ __ _ _ __ ___  ________
#   | '__/ _` | '_ ` _ \|_  /_  /
#   | | | (_| | | | | | |/ / / / 
#   |_|  \__,_|_| |_| |_/___/___|
#

import math
import collections
from sys import stdin,stdout,setrecursionlimit
from bisect import bisect_left as bsl
from bisect import bisect_right as bsr
import heapq as hq
setrecursionlimit(2**20)

t = 1
t = int(stdin.readline())

for _ in range(t):
    #n = int(stdin.readline())
    #s = stdin.readline().strip('\n')
    n,m = list(map(int, stdin.readline().rstrip().split()))
    chk = False
    for i in range(n):
        r1 = list(map(int, stdin.readline().rstrip().split()))
        r2 = list(map(int, stdin.readline().rstrip().split()))
        
        if(r1[1]==r2[0]):
            chk = True
        
    if(m%2==1):
        print('NO')
        continue
    if(chk):
        print('YES')
    else:
        print('NO')
    
    


t = int(input())
for test in range(1, t+1):
    n, m = [int(i) for i in input().split()]
    flag = False
    for i in range(n):
        a, b = [int(j) for j in input().split()]
        c, d = [int(j) for j in input().split()]
        if b == c:
            flag = True
    if flag and m%2 == 0:
        print("YES")
    else:
        print("NO")

3
import sys
input = lambda: sys.stdin.readline().strip()
for _ in range(int(input())):
    n, m = [int(x) for x in input().split()]
    tiles = [[[int(x) for x in input().split()] for _ in range(2)] for i in range(n)]
    print('YES' if m % 2 == 0 and any(tile[0][1] == tile[1][0] for tile in tiles) else 'NO')


t=int(input())
for you in range(t):
    l=input().split()
    n=int(l[0])
    m=int(l[1])
    l=[]
    col=dict()
    row=dict()
    found=0
    done=0
    for i in range(n):
        lo=input().split()
        a=int(lo[0])
        b=int(lo[1])
        lo=input().split()
        c=int(lo[0])
        d=int(lo[1])
        if(b==c):
            found=1
    if(found==1 and m%2==0):
        print("YES")
    else:
        print("NO")


from functools import lru_cache
from sys import stdin, stdout
import sys
from math import *

# from collections import deque
# sys.setrecursionlimit(int(2e5+10))
input = stdin.readline
# print = stdout.write
# dp=[-1]*100000

for __ in range(int(input())):
	n,m=list(map(int,input().split()))
	ans="NO"
	for i in range(n):
		a,b=list(map(int,input().split()))
		x,y=list(map(int,input().split()))
		if(x==b):
			ans="YES"
	if(m%2==1):
		print("NO")
	else:
		print(ans)