Dreamoon likes to play with sets, integers and $gcd$. $\operatorname{gcd}(a, b)$ is defined as the largest positive integer that divides both a and b.

Let S be a set of exactly four distinct integers greater than 0. Define S to be of rank k if and only if for all pairs of distinct elements s_{i}, s_{j} from S, $\operatorname{gcd}(s_{i}, s_{j}) = k$.

Given k and n, Dreamoon wants to make up n sets of rank k using integers from 1 to m such that no integer is used in two different sets (of course you can leave some integers without use). Calculate the minimum m that makes it possible and print one possible solution.


-----Input-----

The single line of the input contains two space separated integers n, k (1 ≤ n ≤ 10 000, 1 ≤ k ≤ 100).


-----Output-----

On the first line print a single integer — the minimal possible m. 

On each of the next n lines print four space separated integers representing the i-th set.

Neither the order of the sets nor the order of integers within a set is important. If there are multiple possible solutions with minimal m, print any one of them.


-----Examples-----
Input
1 1

Output
5
1 2 3 5

Input
2 2

Output
22
2 4 6 22
14 18 10 16



-----Note-----

For the first example it's easy to see that set {1, 2, 3, 4} isn't a valid set of rank 1 since $\operatorname{gcd}(2,4) = 2 \neq 1$.

Difficulty: HARD
Tags: Greedy algorithms

Mathematics

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
l = input().split(' ')
n = int(l[0])
k = int(l[1])
print((6 * n - 1) * k)
for i in range(n):
	print(str((6 * i + 1) * k) + ' ' + str((6 * i + 2) * k) + ' ' + str((6 * i + 3) * k) + ' ' + str((6 * i + 5) * k))


(n, k) = list(map(int, input().split()))
print((6 * n - 1) * k)
for i in range(0, n):
	print((6 * i + 1) * k, (6 * i + 2) * k, (6 * i + 3) * k, (6 * i + 5) * k)


(a, b) = map(int, input().split(' '))
print((6 * a - 1) * b)
for i in range(a):
	print((6 * i + 1) * b, (6 * i + 2) * b, (6 * i + 3) * b, (6 * i + 5) * b)


(n, k) = map(int, input().split())
print((6 * n - 1) * k)
for i in range(n):
	print(str((6 * i + 1) * k) + ' ' + str((6 * i + 2) * k) + ' ' + str((6 * i + 3) * k) + ' ' + str((6 * i + 5) * k))


__author__ = 'neki'
import sys
global primes, primeDiv

def gcdPrime(a, b):
	if b == 0 or a == 0:
		return 0
	if b == 1 or a == 1:
		return 1
	if b > a:
		return gcdPrime(a, b % a)
	return gcdPrime(b, a % b)

def gcdPrimeSet(set, a):
	result = []
	if len(set) >= 4:
		return [x for x in set]
	for i in set:
		if gcdPrime(i, a) == 0:
			result.append(i)
	return result
words = str(input()).split()
n = int(words[0])
k = int(words[1])
sets = []
for i in range(n):
	sets.append(set())
el = -1
for i in range(len(sets)):
	el += 2
	while len(sets[i]) < 4:
		if el % 2 == 0:
			el += 1
		sets[i].add(el)
		sets[i].add(el + 1)
		sets[i].add(el + 2)
		el += 4
		while len(gcdPrimeSet(sets[i], el)) > 0:
			el += 2
		sets[i].add(el)
print(k * el)
for s in sets:
	for i in range(4):
		print(k * s.pop(), end=' ')
	print()


(n, k) = [int(x) for x in input().split()]
print(k * ((n - 1) * 6 + 5))
for i in range(n):
	print(k * (6 * i + 1), k * (6 * i + 3), k * (6 * i + 5), k * (6 * i + 2))


(a, k) = map(int, input().split())
print(k * (a * 6 - 1))
i = int(1)
while True:
	x = i * 6 - 5
	print(x * k, x * k + k, x * k + 2 * k, x * k + 4 * k)
	i += 1
	if i > a:
		break


(n, k) = [int(i) for i in input().split()]
print((6 * n - 1) * k)
for a in range(n):
	val = 6 * a
	print((val + 1) * k, (val + 2) * k, (val + 3) * k, (val + 5) * k)


(x, y) = map(int, input().split())
z = []
print((6 * x - 1) * y)
for i in range(0, x):
	z.append((6 * i + 1) * y)
	z.append((6 * i + 3) * y)
	z.append((6 * i + 4) * y)
	z.append((6 * i + 5) * y)
	print(*z)
	z.clear()


inp = input().split(' ')

def result(sets, maximum_divisor):
	output = list()
	output.append(str(int(maximum_divisor) * (6 * int(sets) - 1)))
	for i in range(int(sets)):
		output.append(str(int(maximum_divisor) * (6 * int(i) + 1)) + ' ' + str(int(maximum_divisor) * (6 * int(i) + 3)) + ' ' + str(int(maximum_divisor) * (6 * int(i) + 4)) + ' ' + str(int(maximum_divisor) * (6 * int(i) + 5)))
	return output
for i in result(inp[0], inp[1]):
	print(i)


from fractions import gcd

def checkSet(setK, newVal):
	for v in setK:
		if gcd(v, newVal) != 1:
			return False
	return True

def solve(n, k):
	j = 1
	sets = []
	for _ in range(n):
		setK = set()
		while len(setK) < 4:
			if checkSet(setK, j) and (not (len(setK) == 0 and j % 3 == 0)):
				setK.add(j)
			j += 1
		sets.append(setK)
	maxV = 0
	for setK in sets:
		maxV = max(maxV, max(setK))
	print(maxV * k)
	for setK in sets:
		print(' '.join([str(x * k) for x in setK]))
(n, k) = list(map(int, input().split()))
solve(n, k)


(n, k) = map(int, input().split())
print(k * (2 * (3 * n) - 1))
now = 1
m = 2
for i in range(n):
	print(k * m, end=' ')
	for j in range(3):
		print(k * now, end=' ')
		now += 2
	m += 6
	print()


(n, k) = map(int, input().split())
print(k * (6 * n - 1))
for i in range(n):
	print(k * (6 * i + 1), k * (6 * i + 3), k * (6 * i + 4), k * (6 * i + 5))


(n, k) = map(int, input().split())
print(k * (6 * (n - 1) + 5))
for i in range(0, n):
	t = [6 * i + 1, 6 * i + 2, 6 * i + 3, 6 * i + 5]
	print(' '.join(map(lambda m: str(m * k), t)))


(n, k) = map(int, input().split())
print(k * (6 * n - 1))
for i in range(1, n + 1):
	x = (i - 1) * 6 + 1
	print(k * x, end=' ')
	print(k * (x + 1), end=' ')
	print(k * (x + 2), end=' ')
	print(k * (x + 4))


import sys
INF = 10 ** 20
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br
(n, k) = I()
ans = [[1, 2, 3, 5]]
cur = 4
add = 7
for i in range(1, n):
	ok = [add, add + 2, add + 4]
	while True:
		r = True
		for i in ok:
			if gcd(i, cur) > 1:
				r = False
		if r:
			break
		cur += 2
	ok.append(cur)
	add += 6
	cur += 2
	ans.append(ok)
print((add - 2) * k)
for i in ans:
	print(*[j * k for j in i])


(n, k) = map(int, input().split())
print((6 * n - 1) * k)
print('\n'.join(('%i %i %i %i' % tuple((k * (6 * i + j) for j in (1, 2, 3, 5))) for i in range(n))))


(n, k) = map(int, input().split())
l = [1, 2, 3, 5]
print((6 * n - 1) * k)
for i in range(n):
	for j in l:
		print((6 * i + j) * k, end=' ')
	print()


import sys

def solve():
	(n, k) = rv()
	res = list()
	cur = 1
	for i in range(n):
		while cur % 2 == 0:
			cur += 1
		res.append((cur * k, (cur + 1) * k, (cur + 2) * k, (cur + 4) * k))
		cur += 5
	print(res[-1][-1])
	print('\n'.join((' '.join(map(str, l)) for l in res)))

def prt(l):
	return print(' '.join(l))

def rv():
	return map(int, input().split())

def rl(n):
	return [list(map(int, input().split())) for _ in range(n)]
if sys.hexversion == 50594544:
	sys.stdin = open('test.txt')
solve()


(n, k) = map(int, input().split())
print((6 * n - 1) * k)
maxx = -1
for i in range(0, n):
	(a, b, c, d) = (k * (6 * i + 1), k * (6 * i + 2), k * (6 * i + 3), k * (6 * i + 5))
	print(a, b, c, d)


(n, k) = map(int, input().split())
print((6 * n - 1) * k)
for i in range(1, n + 1):
	m = i * 6 - 5
	print(k * m, k * (m + 1), k * (m + 2), k * (m + 4))


k = 0
i = 1
a = []
while k < 10000:
	b = []
	b.append(i)
	b.append(i + 1)
	b.append(i + 2)
	b.append(i + 4)
	i += 6
	a.append(b)
	k += 1
(n, k) = tuple(map(int, input().split()))
print(a[n - 1][3] * k)
for i in range(0, n):
	print(a[i][0] * k, a[i][1] * k, a[i][2] * k, a[i][3] * k)


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz/'
M = 998244353
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
(n, k) = value()
ans = []
for i in range(1, 2 * n * 4, 6):
	ans.append(i)
	ans.append(i + 1)
	ans.append(i + 2)
	ans.append(i + 4)
print(k * max(ans[:4 * n]))
for i in range(n):
	for j in range(4):
		print(k * ans[4 * i + j], end=' ')
	print()


(n, k) = map(int, input().split())
ans = [[3 * i + 1, 3 * i + 2, 3 * i + 3, 3 * i + 5] for i in range(0, 2 * n, 2)]
print(ans[-1][-1] * k)
s = ''
for arr in ans:
	s += ' '.join([str(x * k) for x in arr])
	s += '\n'
print(s)