Migrated from Lutece 2686 F_know's Binary Matrix

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

F_know invites you to play an interesting game on a binary matrix with $10^6$ rows and $10^6$ columns, consisting of either $0$ or $1$. Initially, the number of $1$ is $n$.

Now he gives you an integer $k$ and you can do the following operation on the matrix any number (possibly zero) of times you want.

• Choose a contiguous submatrix of size $k\times 1$ or $1\times k$.
• Flip every number in the submatrix. That is, if it is $0$, change it to $1$, and vice versa.

Your goal is to make all numbers in the matrix become $0$. Determine whether you can do it or not.

Input

The first line contains two integers $n$ and $k$ ($0\le n \le 10^5,1\le k \le 10^3$), denoting the initial number of $1$ and the size of the submatrix.

For the next $n$ lines, each line contains two integers $x$ and $y$ ($1\le x,y\le 10^6$), denoting that a number $1$ locates at $x$-th row and $y$-th column. It's guaranteed that all the positions in the input are distinct.

Output

If you can make all numbers become $0$, output $\texttt{YES}$. Otherwise, output $\texttt{NO}$.

Samples

4 2
1 1
1 3
1 4
2 2

YES

4 3
2 2
1 3
3 3
3 1

NO

Note

In the first example, you can make it by the following steps.

In the second example, it's impossible to achieve the goal.

Resources

电子科技大学第十二届 ACM 趣味程序设计竞赛