The king of Berland organizes a ball! $n$ pair are invited to the ball, they are numbered from $1$ to $n$. Each pair consists of one man and one woman. Each dancer (either man or woman) has a monochrome costume. The color of each costume is represented by an integer from $1$ to $k$, inclusive.

Let $b_i$ be the color of the man's costume and $g_i$ be the color of the woman's costume in the $i$-th pair. You have to choose a color for each dancer's costume (i.e. values $b_1, b_2, \dots, b_n$ and $g_1, g_2, \dots g_n$) in such a way that:  for every $i$: $b_i$ and $g_i$ are integers between $1$ and $k$, inclusive;  there are no two completely identical pairs, i.e. no two indices $i, j$ ($i \ne j$) such that $b_i = b_j$ and $g_i = g_j$ at the same time;  there is no pair such that the color of the man's costume is the same as the color of the woman's costume in this pair, i.e. $b_i \ne g_i$ for every $i$;  for each two consecutive (adjacent) pairs both man's costume colors and woman's costume colors differ, i.e. for every $i$ from $1$ to $n-1$ the conditions $b_i \ne b_{i + 1}$ and $g_i \ne g_{i + 1}$ hold. 

Let's take a look at the examples of bad and good color choosing (for $n=4$ and $k=3$, man is the first in a pair and woman is the second):

Bad color choosing:   $(1, 2)$, $(2, 3)$, $(3, 2)$, $(1, 2)$ — contradiction with the second rule (there are equal pairs);  $(2, 3)$, $(1, 1)$, $(3, 2)$, $(1, 3)$ — contradiction with the third rule (there is a pair with costumes of the same color);  $(1, 2)$, $(2, 3)$, $(1, 3)$, $(2, 1)$ — contradiction with the fourth rule (there are two consecutive pairs such that colors of costumes of men/women are the same). 

Good color choosing:   $(1, 2)$, $(2, 1)$, $(1, 3)$, $(3, 1)$;  $(1, 2)$, $(3, 1)$, $(2, 3)$, $(3, 2)$;  $(3, 1)$, $(1, 2)$, $(2, 3)$, $(3, 2)$. 

You have to find any suitable color choosing or say that no suitable choosing exists.


-----Input-----

The only line of the input contains two integers $n$ and $k$ ($2 \le n, k \le 2 \cdot 10^5$) — the number of pairs and the number of colors.


-----Output-----

If it is impossible to find any suitable colors choosing, print "NO".

Otherwise print "YES" and then the colors of the costumes of pairs in the next $n$ lines. The $i$-th line should contain two integers $b_i$ and $g_i$ — colors of costumes of man and woman in the $i$-th pair, respectively.

You can print each letter in any case (upper or lower). For example, "YeS", "no" and "yES" are all acceptable.


-----Examples-----
Input
4 3

Output
YES
3 1
1 3
3 2
2 3

Input
10 4

Output
YES
2 1
1 3
4 2
3 4
4 3
3 2
2 4
4 1
1 4
3 1

Input
13 4

Output
NO

Difficulty: introductory

Starter code:

Solutions:
n, k = list(map(int, input().split()))
if n > k*(k-1):
    print("NO")
else:
    print("YES")
    cnt = 0
    for delta in range(k):
        for c in range(1, k+1):
            if cnt < n:
                cnt +=1
                print(c, 1+(c+delta)%k)
            else:
                break


import sys

n,k=list(map(int,input().split()))

if n>k*(k-1):
    print("NO")
    return
else:
    print("YES")

count=0
for i in range(1,k):
    for j in range(1,k+1):
        print(j,(j+i-1)%k+1)
        count+=1

        if count==n:
            break
    if count==n:
        break


n,k=list(map(int,input().split()))
if n>k*(k-1):
	print("NO")
else:
	count=0
	diff=1
	i=0
	print("YES")
	while diff<k:
		while i<k and count<n:
			print("{} {}".format(i+1,(i+diff)%k+1))
			i+=1
			count+=1
		i=0
		diff+=1


import sys
n,k=list(map(int,input().split()))
c=0
if k*(k-1) < n:
 print('NO')
else:
 print('YES')
 for i in range(k-1):
  for j in range(k):
   c+=1
   if c>n:return
   print(1+j,1+(j+i+1)%k)


import sys
n,k=map(int,input().split())
c=0
if k*(k-1) < n:
 print('NO')
else:
 print('YES')
 for i in range(k-1):
  for j in range(k):
   c+=1
   if c>n:return
   print(1+j,1+(j+i+1)%k)

n, k = list(map(int, input().split()))

arr1 = [i for i in range(1, k + 1)]
arr2 = arr1[1:] + [arr1[0]]

if k*(k - 1) >= n:
	print('YES')
	for i in range(k - 1):
		for j in range(k):
			print(str(arr1[j]) + " " + str(arr2[j]))
			n -= 1
			if(n == 0):
				break
		if(n == 0):
			break
		arr2 = arr2[1:] + [arr2[0]]


else:
	print('NO')



import math

n, k = list(map(int, input().strip().split()))

if k <= 2:
    if n == 2:
        print("YES")
        print("1 2")
        print("2 1")
    else:
        print("NO")
    return

if k < 700:
    pairs = 2 * math.factorial(k)/(2*math.factorial(k-2))
    if pairs < n:
        print("NO")
        return

# Possible
print("YES")
shift = 1
written = 0
for _ in range(k-1):
    for v in range(k):
        print("{} {}".format(str(v+1), str(((v+shift)%k)+1)))
        written += 1
        if written == n:
            break
    if written == n:
        break
    shift = (shift + 1)%k



import sys
n , k = map(int,input().split())

if (k*(k-1)) < n:
    print('NO')
else:
    print('YES')
    c = 0
    d = 1
    for i in range(n):
        if c == k:
            d += 1
            c = 0
        if d == k:
            break
        print(c+1 , (c+d)%k + 1)
        c += 1