PolandBall and Polygon

题意翻译

给出一个n边形，和距离k。 第一次连接1和 k+1，第二次连接k+1和(k+1+k)%n，依次进行n次，每次结束后输出n边形被分割成了几个区域。

题目描述

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.

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

5 2

输出样例 #1

2 3 5 8 11 

输入样例 #2

10 3

输出样例 #2

2 3 4 6 9 12 16 21 26 31 

说明

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.