CF755D.PolandBall and Polygon

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.

PolandBall 拥有一个具有 $n$ 个顶点的凸多边形，且其任意三条对角线不交于同一点。PolandBall 决定改进该多边形，并绘制若干条红色线段。

他选定一个整数 $k$，满足 $\gcd(n,\,k) = 1$。多边形的顶点按顺时针方向编号为 $1$ 到 $n$。PolandBall 从顶点 $1$ 开始，重复以下操作 $n$ 次：

假设上一次操作结束于顶点 $x$（若为第一次操作，则令 $x = 1$）。从顶点 $x$ 向顺时针方向第 $k$ 个顶点引一条新线段。该目标顶点为 $x + k$ 或 $x + k - n$，具体取决于哪一个结果是多边形顶点的有效编号（即在 $1$ 到 $n$ 范围内）。

你的任务是：在每次绘制线段后，计算多边形被划分出的“区域”数量。所谓“区域”，是指由所绘制的对角线或多边形边所围成的、位于多边形内部的、互不重叠的清晰区域。

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

输入中仅有两个数：$n$ 和 $k$（$5 \leq n \leq 10^6$，$2 \leq k \leq 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.

你应该输出 n 个用空格分隔的数值。其中第 i 个数值表示画完前 i 条直线后，多边形被划分出的区域数量。

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.

两个整数 $a$ 和 $b$ 的最大公约数（gcd）是指能同时整除 $a$ 和 $b$ 的最大的正整数。

对于第一个样例测试用例，你应该输出 “2 3 5 8 11”。下方图片对应于画线之后的情形。