K. Uniform Dispersion
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
The universe is not required to be in perfect harmony with human fancy.
— Carl Sagan, Broca's Brain

OC likes the stars in the sky, which are scattered but are arranged in a certain pattern.

One day, OC encounters a map with $$$n$$$ points. The $$$i$$$-th point is located at $$$(x_i, y_i)$$$.

Just like the sky, he wants to make some partitions on it. But he is too busy, so he asks you for help.

Firstly, he chooses a lucky number $$$k$$$, which will be given to you.

Then, you need to draw $$$k$$$ vertical lines and $$$k$$$ horizontal lines, meeting with the following condition:

  1. Assume that the $$$i$$$-th vertical line is $$$x=a_i$$$, the $$$j$$$-th horizontal line is $$$y=b_j$$$;
  2. 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't go through the points in the map);
  3. The map is divided into $$$(k + 1) ^ 2$$$ regions by these lines. The number of points in each region is the same;
  4. $$$a_i$$$ and $$$b_i$$$ can be non-integers.
Determine whether it is possible.
Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10 ^ 4)$$$, denoting the number of test cases.

The 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)$$$.

The $$$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.

It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \times 10 ^ 5$$$.

Output

For each test case, print $$$\mathtt{Yes}$$$ if it is possible. Otherwise, print $$$\mathtt{No}$$$.

You may print each letter in any case. For example, YES, yes, Yes will all be recognized as positive answer, NO, no, nO will all be recognized as negative answer.

Example
Input
3
4 1
-2 -2
-1 2
1 3
2 -1
4 1
-2 -2
-2 2
1 3
-2 0
8 1
-2 -2
-2 -2
-1 2
-1 2
1 3
1 3
2 -1
2 -1
Output
Yes
No
Yes
Note

In the first test case, the points are $$$(-2, -2)$$$, $$$(-1, 2)$$$, $$$(1, 3)$$$, $$$(2, -1)$$$. You can draw $$$x=-0.39$$$ and $$$y=0.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.

Case 1Case 2

In the second test case, the points are $$$(-2, -2)$$$, $$$(-2, 2)$$$, $$$(1, 3)$$$, $$$(-2, 0)$$$. It can be shown that it is impossible.

In the third test case, note that the points can overlap.