Even if you just leave them be, they will fall to pieces all by themselves. So, someone has to protect them, right?

You find yourself playing with Teucer again in the city of Liyue. As you take the eccentric little kid around, you notice something interesting about the structure of the city.

Liyue can be represented as a directed graph containing n nodes. Nodes are labeled from 1 to n. There is a directed edge from node a to node b if and only if a < b.

A path between nodes a and b is defined as a sequence of edges such that you can start at a, travel along all of these edges in the corresponding direction, and end at b. The length of a path is defined by the number of edges. A rainbow path of length x is defined as a path in the graph such that there exists at least 2 distinct colors among the set of x edges.

Teucer's favorite number is k. You are curious about the following scenario: If you were to label each edge with a color, what is the minimum number of colors needed to ensure that all paths of length k or longer are rainbow paths?

Teucer wants to surprise his older brother with a map of Liyue. He also wants to know a valid coloring of edges that uses the minimum number of colors. Please help him with this task!

Input

The only line of input contains two integers n and k (2 ≤ k < n ≤ 1000). 

Output

On the first line, output c, the minimum colors you need to satisfy the above requirements.

On the second line, print a valid edge coloring as an array of (n(n-1))/(2) integers ranging from 1 to c. Exactly c distinct colors should exist in the construction. Print the edges in increasing order by the start node first, then by the second node.

For example, if n=4, the edge colors will correspond to this order of edges: (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)

Examples

Input


5 3


Output


2
1 2 2 2 2 2 2 1 1 1


Input


5 2


Output


3
3 2 2 1 2 2 1 3 1 1 


Input


8 7


Output


2
2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1


Input


3 2


Output


2
1 2 2 

Note

The corresponding construction for the first test case looks like this: 

<image> It is impossible to satisfy the constraints with less than 2 colors.

The corresponding construction for the second test case looks like this: 

<image> One can show there exists no construction using less than 3 colors.

Difficulty: VERY_HARD
Tags: Bit manipulation

Graph algorithms

Constructive algorithms

Greedy algorithms

Divide and conquer

Mathematics
Skill types: Bit manipulation

Greedy algorithms

Starter code:

Solutions:
(n, k) = tuple(map(int, input().split()))
arr = [i for i in range(n)]
colors = [[0 for _ in range(n)] for _ in range(n)]
groups = []
group = []
for i in range(n):
	group.append(arr[i])
	if len(group) == k:
		groups.append(group[:])
		group = []
if group:
	groups.append(group[:])
	group = []
color = 1
while True:
	for group in groups:
		for i in range(len(group)):
			for j in range(i + 1, len(group)):
				if colors[group[i]][group[j]] == 0:
					colors[group[i]][group[j]] = color
	if len(groups) == 1:
		break
	group2 = []
	groups2 = []
	for group in groups:
		group2.append(group)
		if len(group2) == k:
			group3 = []
			for g in group2:
				for j in g:
					group3.append(j)
			groups2.append(group3[:])
			group2 = []
	if group2:
		group3 = []
		for g in group2:
			for j in g:
				group3.append(j)
		groups2.append(group3[:])
		group2 = []
	groups = groups2[:]
	color += 1
print(color)
for i in range(n):
	for j in range(i + 1, n):
		print(colors[i][j], end=' ')
print()


import sys
import math
inpu = sys.stdin.readline
prin = sys.stdout.write

def numberToBase(n, b):
	if n == 0:
		return [0]
	digits = []
	while n:
		digits.append(int(n % b))
		n //= b
	return digits[::-1]
(n, k) = map(int, inpu().split())
digits = math.ceil(math.log(n) / math.log(k))
prin(str(digits))
prin('\n')
for i in range(n):
	j = i + 1
	diff = 1
	while j < n:
		if i // k ** diff != j // k ** diff:
			diff += 1
			continue
		prin(str(diff))
		prin(' ')
		j += 1


(n, k) = map(int, input().split())
c = 0
nn = n
while nn > 0:
	nn //= k
	c += 1
curr = [0] * c
things = []
for i in range(n - 1):
	things.append(tuple(curr))
	curr[0] += 1
	for i in range(c):
		if curr[i] == k:
			curr[i] = 0
			curr[i + 1] += 1
		else:
			break
things.append(tuple(curr))
out = []
for i in range(n):
	for j in range(i + 1, n):
		for cc in range(c):
			if things[j][cc] > things[i][cc]:
				out.append(cc + 1)
				break
print(max(out))
print(' '.join(map(str, out)))


import sys
from sys import stdin
(n, k) = map(int, stdin.readline().split())
ans = []
for i in range(n):
	for j in range(i + 1, n):
		ibl = i
		jbl = j
		now = 0
		while ibl != jbl:
			ibl //= k
			jbl //= k
			now += 1
		ans.append(str(now))
s = set(ans)
print(len(s))
print(' '.join(ans))


(n, k) = map(int, input().split())
a = []
for i in range(n):
	for j in range(i + 1, n):
		(u, v, r) = (i, j, 0)
		while u ^ v:
			u //= k
			v //= k
			r += 1
		a.append(r)
print(max(a), *a)


(n, k) = map(int, input().split())
c = 0
m = 1
while m < n:
	m = m * k
	c = c + 1
print(c)
for i in range(0, n):
	for j in range(i + 1, n):
		u = i
		v = j
		r = 0
		while u != v:
			u //= k
			v //= k
			r = r + 1
		print(r, end=' ')


(n, k) = map(int, input().split())
basek = [[-1] * 20 for _ in range(1 + n)]
basek[0][0] = [0]
for x in range(n):
	cur = x
	i = 0
	while cur:
		basek[x][i] = cur % k
		cur //= k
		i += 1

def diff(x, y):
	for c in range(19, -1, -1):
		if basek[x][c] != basek[y][c]:
			return c
	raise 'wa'
ans = []
for x in range(n):
	for y in range(1 + x, n):
		d = diff(x, y)
		ans.append(1 + d)
print(len(set(ans)))
print(*ans)


(n, k) = map(int, input().split())
colors = [0 for j in range(n * n)]

def getgroup(arr, c):
	m = len(arr)
	if m <= 1:
		return
	sub = (m - 1) // k + 1
	group = []
	for i in range(k):
		front = i * sub
		rear = (i + 1) * sub
		if front >= m:
			break
		temp = arr[front:rear]
		group.append(temp)
		getgroup(temp, c + 1)
	for i in range(len(group)):
		for j in range(i + 1, len(group)):
			for p1 in group[i]:
				for p2 in group[j]:
					colors[p1 * n + p2] = c
getgroup([i for i in range(n)], 1)
ans = []
for i in range(n):
	ans += colors[i * n:(i + 1) * n][i + 1:]
print(max(ans))
print(' '.join(map(str, ans)))


import collections
import math
import itertools
import sys
import time
import random

def fast_input():
	return sys.stdin.readline().strip()
input = fast_input

def ints_input():
	return list((int(x) for x in input().split()))

def int_input():
	return int(input())

def is_prime(s):
	for i in range(2, s):
		if i * i > s:
			return True
		if s % i == 0:
			return False

def solve():
	(n, k) = ints_input()
	x = 1
	covered = k
	while covered < n:
		covered *= k
		x += 1
	print(x)
	colors = []
	for i in range(n):
		for j in range(i + 1, n):
			x = 0
			r = i
			while r != j:
				r = r // k
				j = j // k
				x += 1
			colors.append(str(x))
	print(' '.join(colors))
if False:
	for _ in range(int_input()):
		solve()
else:
	solve()