{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"epigraph\"\u003e\u003cdiv class\u003d\"epigraph-text\"\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eThe universe is not required to be in perfect harmony with human fancy.\u003c/span\u003e\u003c/div\u003e\u003cdiv class\u003d\"epigraph-source\"\u003e— Carl Sagan, \u003cspan class\u003d\"tex-font-style-it\"\u003eBroca\u0027s Brain\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eOC\u003c/span\u003e likes the stars in the sky, which are scattered but are arranged in a certain pattern.\u003c/p\u003e\u003cp\u003eOne day, \u003cspan class\u003d\"tex-font-style-it\"\u003eOC\u003c/span\u003e encounters a map with $$$n$$$ points. The $$$i$$$-th point is located at $$$(x_i, y_i)$$$.\u003c/p\u003e\u003cp\u003eJust like the sky, he wants to make some partitions on it. But he is too busy, so he asks you for help.\u003c/p\u003e\u003cp\u003eFirstly, he chooses a lucky number $$$k$$$, which will be given to you.\u003c/p\u003e\u003cp\u003eThen, you need to draw $$$k$$$ vertical lines and $$$k$$$ horizontal lines, meeting with the following condition:\u003c/p\u003e\u003col\u003e \u003cli\u003e Assume that the $$$i$$$-th vertical line is $$$x\u003da_i$$$, the $$$j$$$-th horizontal line is $$$y\u003db_j$$$; \u003c/li\u003e\u003cli\u003e For all $$$(x_i, y_i)$$$, $$$1 \\leq i \\leq n$$$, such that $$$x_i \\notin a$$$ and $$$y_i \\notin b$$$ (In other words, all the lines don\u0027t go through the points in the map); \u003c/li\u003e\u003cli\u003e The map is divided into $$$(k + 1) ^ 2$$$ regions by these lines. The number of points in each region is \u003cspan class\u003d\"tex-font-style-bf\"\u003ethe same\u003c/span\u003e; \u003c/li\u003e\u003cli\u003e $$$a_i$$$ and $$$b_i$$$ can be \u003cspan class\u003d\"tex-font-style-bf\"\u003enon-integers\u003c/span\u003e. \u003c/li\u003e\u003c/ol\u003e Determine whether it is possible."}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains a single integer $$$t$$$ $$$(1 \\leq t \\leq 10 ^ 4)$$$, denoting the number of test cases.\u003c/p\u003e\u003cp\u003eThe first line of each test case contains two integers $$$n$$$, $$$k$$$ $$$(4 \\leq n \\leq 2 \\times 10 ^ 5, 0 \\leq k \\leq 10 ^ 9)$$$.\u003c/p\u003e\u003cp\u003eThe $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$, $$$y_i$$$ $$$(-10^9 \\leq x_i, y_i \\leq 10^9)$$$, denoting the $$$i$$$-th point on the map.\u003c/p\u003e\u003cp\u003eIt\u0027s guaranteed that the sum of $$$n$$$ over all test cases doesn\u0027t exceed $$$2 \\times 10 ^ 5$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, print $$$\\mathtt{Yes}$$$ if it is possible. Otherwise, print $$$\\mathtt{No}$$$.\u003c/p\u003e\u003cp\u003eYou may print each letter in any case. For example, \u003cspan class\u003d\"tex-font-style-tt\"\u003eYES\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003eyes\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003eYes\u003c/span\u003e will all be recognized as positive answer, \u003cspan class\u003d\"tex-font-style-tt\"\u003eNO\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003eno\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003enO\u003c/span\u003e will all be recognized as negative answer.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n4 1\n-2 -2\n-1 2\n1 3\n2 -1\n4 1\n-2 -2\n-2 2\n1 3\n-2 0\n8 1\n-2 -2\n-2 -2\n-1 2\n-1 2\n1 3\n1 3\n2 -1\n2 -1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYes\nNo\nYes\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first test case, the points are $$$(-2, -2)$$$, $$$(-1, 2)$$$, $$$(1, 3)$$$, $$$(2, -1)$$$. You can draw $$$x\u003d-0.39$$$ and $$$y\u003d0.39$$$ to divide the map into $$$4$$$ regions. It can be shown that the number of points in each region is $$$1$$$. So it is possible.\u003c/p\u003e\u003ccenter\u003e \u003ctable class\u003d\"tex-tabular\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"tex-tabular-text-align-center\"\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/f9a30fbde8a243e0b6c743e129a14d64?v\u003d1726273188\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"302px\"\u003e\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-text-align-center\"\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/c0ae90aa17fb69acc073653ea7fabd13?v\u003d1726273188\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"302px\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"tex-tabular-text-align-center\"\u003e\u003cspan class\u003d\"tex-font-size-small\"\u003eCase 1\u003c/span\u003e\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-text-align-center\"\u003e\u003cspan class\u003d\"tex-font-size-small\"\u003eCase 2\u003c/span\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e \u003c/center\u003e\u003cp\u003eIn the second test case, the points are $$$(-2, -2)$$$, $$$(-2, 2)$$$, $$$(1, 3)$$$, $$$(-2, 0)$$$. It can be shown that it is impossible.\u003c/p\u003e\u003cp\u003eIn the third test case, note that the points \u003cspan class\u003d\"tex-font-style-bf\"\u003ecan overlap\u003c/span\u003e.\u003c/p\u003e"}}]}