玛莎有 $$$n$$$ 种尺寸为 $$$2 \times 2$$$ 的瓷砖。图块的每个单元格包含一个整数。玛莎每种类型都有无限数量的瓷砖。
Masha 决定构建由给定图块组成的大小为 $$$m \times m$$$ 的正方形。该正方形还必须相对于主对角矩阵对称,并且该正方形的每个单元都必须恰好被一个瓦片单元覆盖,并且瓦片的边应与正方形的边平行。所有放置的图块不能相互交叉。此外,每块瓷砖都应该位于正方形内。请参阅注释部分中的图片以更好地理解。
相对于主对角矩阵对称的是这样一个方阵 $$$s$$$,对于每对 $$$(i, j)$$$,条件 $$$s[i][j] = s[j][i]$$$ 成立。 IE。确实,写入$$$i$$$行和$$$j$$$第列的元素等于写入$$$j$$$第行和$$$i$$$列的元素。
你的任务是确定 Masha 是否可以构造一个大小为 $$$m \times m$$$ 的正方形,这是一个对称矩阵,由她拥有的图块组成。玛莎可以使用任意数量的每种类型的瓷砖来构建正方形。请注意,她无法旋转图块,她只能将它们放置在输入中的方向上。
您必须回答 $$$t$$$ 独立测试用例。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 100$$$, $$$1 \le m \le 100$$$) — 瓷砖类型的数量以及 Masha 想要构造的正方形的大小。
测试用例的接下来的 $$$2n$$$ 行包含图块类型的描述。瓷砖的类型依次书写,每种类型写在两行上。
描述的第一行包含两个不超过$$$100$$$的正(大于零)整数——写在图块左上角的数字和写在当前类型图块右上角的数字。描述的第二行包含两个不超过$$$100$$$的正(大于零)整数——写在图块左下角的数字和写在当前类型图块右下角的数字。
禁止旋转图块,只允许将它们放置在输入中的方向上。
输出
对于每个测试用例,如果 Masha 可以构造大小为 $$$m \times m$$$ 的对称矩阵,则打印答案:“是”(不带引号)。否则,打印“NO”(不带引号)。
示例
输入 #1
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
输出 #1
YES NO YES NO YES YES
注意
输入的第一个测试用例有三种类型的图块,如下图所示。
例如,Masha 可以构造以下大小为 $$$4 \times 4$$$ 的正方形,它是一个对称矩阵: