PolandBall has such a convex polygon with n veritces that no three of its diagonals intersect at the same point. PolandBall decided to improve it and draw some red segments. 

He chose a number k such that gcd(n, k) = 1. Vertices of the polygon are numbered from 1 to n in a clockwise way. PolandBall repeats the following process n times, starting from the vertex 1: 

Assume you've ended last operation in vertex x (consider x = 1 if it is the first operation). Draw a new segment from vertex x to k-th next vertex in clockwise direction. This is a vertex x + k or x + k - n depending on which of these is a valid index of polygon's vertex.

Your task is to calculate number of polygon's sections after each drawing. A section is a clear area inside the polygon bounded with drawn diagonals or the polygon's sides.


-----Input-----

There are only two numbers in the input: n and k (5 ≤ n ≤ 10^6, 2 ≤ k ≤ n - 2, gcd(n, k) = 1).


-----Output-----

You should print n values separated by spaces. The i-th value should represent number of polygon's sections after drawing first i lines.


-----Examples-----
Input
5 2

Output
2 3 5 8 11 
Input
10 3

Output
2 3 4 6 9 12 16 21 26 31 


-----Note-----

The greatest common divisor (gcd) of two integers a and b is the largest positive integer that divides both a and b without a remainder.

For the first sample testcase, you should output "2 3 5 8 11". Pictures below correspond to situations after drawing lines. [Image] [Image] [Image] [Image] [Image] [Image]

Difficulty: HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
(n, k) = list(map(int, input().split()))
if n // 2 < k:
	k = n - k
i = 1
count = 1
ans = [1]
for _ in range(n):
	i += k
	if i > n + 1:
		count += 1
		ans.append(ans[-1] + count)
		count += 1
		i -= n
	else:
		ans.append(ans[-1] + count)
print(*ans[1:])


(n, m) = [int(i) for i in input().split()]
if m > n // 2:
	m = n - m
ans = [1]
count = 0
c = 1
for i in range(n):
	count += m
	if count > n:
		c += 1
		count -= n
		ans.append(ans[-1] + c)
		c += 1
	else:
		ans.append(ans[-1] + c)
ans = ans[1:]
print(*ans)


class Fen:

	def __init__(self, n):
		self.value = [0] * n

	def get(self, fro, to):
		return self.get1(to) - self.get1(fro - 1)

	def get1(self, to):
		to = min(to, len(self.value))
		result = 0
		while to >= 0:
			result += self.value[to]
			to = (to & to + 1) - 1
		return result

	def add(self, at, value):
		while at < len(self.value):
			self.value[at] += value
			at = at | at + 1

def solve():
	(n, k) = map(int, input().split())
	k = min(k, n - k)
	count = [0] * n
	res = [None] * n
	ans = 1
	cur = 0
	fen = Fen(n)
	for iteration in range(n):
		nxt = (cur + k) % n
		here = 0
		if cur < nxt:
			here = fen.get(cur + 1, nxt - 1)
		else:
			here = fen.get(0, nxt - 1) + fen.get(cur + 1, n - 1)
		fen.add(cur, 1)
		fen.add(nxt, 1)
		cur = nxt
		ans += here + 1
		res[iteration] = ans
	print(' '.join(map(str, res)))
solve()


import sys
inf = (1 << 31) - 1

def solve():
	(n, k) = map(int, input().split())
	if k > n - k:
		k = n - k
	s = 0
	res = 1
	a = 1
	ans = [0] * n
	for i in range(n):
		t = (s + k) % n
		if t < s and t > 0:
			res += a + 1
			a += 2
		else:
			res += a
		ans[i] = res
		s = t
	print(*ans)

def __starting_point():
	solve()
__starting_point()


l = input().split()
n = int(l[0])
k = int(l[1])
curr = 0
ans = 1
if k > n // 2:
	k = n - k
for i in range(n):
	curr += k
	if i == n - 1:
		ans = ans + 2 * (curr // n) - 1
	elif curr % n < k:
		ans = ans + 2 * (curr // n)
	else:
		ans = ans + 2 * (curr // n) + 1
	print(ans, end=' ')


import os
import sys
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()
C = [0] * n
k = min(k, n - k)
ans = 1
cur = 1
steps = 0
single = 1
series = []
while steps < n:
	while cur <= n:
		cur += k
		steps += 1
		ans += single
		series.append(ans)
	ans += 1
	series[-1] += 1
	single += 2
	cur = cur % n
series[-1] -= 1
print(*series)


(n, k) = list(map(int, input().strip().split()))
if k > n // 2:
	k = n - k
intersection = n * [0]
count = 1
done = False
i = 0
result = []
for i in range(1, n + 1):
	nn = i * k // n
	j = i * k % n
	if j < k:
		count += 2 * nn
	else:
		count += 2 * nn + 1
	result.append(count)
result[-1] -= 1
print(' '.join([str(r) for r in result]))


import sys
inf = (1 << 31) - 1

def solve():
	(n, k) = map(int, input().split())
	if k > n - k:
		k = n - k
	bit = BinaryIndexedTree([0] * n)
	s = 0
	res = 1
	ans = []
	for i in range(n):
		t = (s + k) % n
		if s < t:
			res += bit.get_sum(t) - bit.get_sum(s + 1) + 1
			ans.append(res)
		else:
			res += bit.get_sum(n) - bit.get_sum(s + 1)
			res += bit.get_sum(t) + 1
			ans.append(res)
		bit.add(s, 1)
		bit.add(t, 1)
		s = t
	print(*ans)

class BinaryIndexedTree:

	def __init__(self, a):
		self.n = len(a)
		self.bit = [0] * (self.n + 1)
		for i in range(1, self.n + 1):
			self.bit[i] += a[i - 1]
			if i + (i & -i) <= self.n:
				self.bit[i + (i & -i)] += self.bit[i]

	def add(self, i, x):
		i += 1
		while i <= self.n:
			self.bit[i] += x
			i += i & -i

	def get_sum(self, r):
		res = 0
		while r > 0:
			res += self.bit[r]
			r -= r & -r
		return res

def __starting_point():
	solve()
__starting_point()


def euclid(a, b):
	if b == 0:
		return [1, 0]
	if b > a:
		l = euclid(b, a)
		l.reverse()
		return l
	else:
		quo = a // b
		rem = a % b
		l = euclid(b, rem)
		m = l[0]
		n = l[1]
		return [n, m - n * quo]
s = input().split()
n = int(s[0])
k = int(s[1])
if 2 * k > n:
	k = n - k
a = [0 for i in range(n)]
t = 0
inv = euclid(n, k)[1] % n
for i in range(k - 1):
	t = (i + 1) * inv % n
	a[t] += 1
	a[n - t] += 1
for r in range(2):
	a[0] += 1
	for i in range(1, n):
		a[i] += a[i - 1]
print('\n'.join((str(a[i]) for i in range(n))))


(n, k) = map(int, input().split())
if k << 1 > n:
	k = n - k
s = 1
for i in range(n):
	s += 1 + i * k // n + (i * k + k - 1) // n
	print(s)