CF2206L.Onion

Onions are widely used in cuisines around the world. This problem is about an "onion peeling" process in geometry.

A set of points in a two-dimensional plane is convex if, for any pair of points $p$ and $q$ in the set, the line segment connecting $p$ and $q$ is entirely contained in the set. For a set of points $S$, its convex hull is the smallest convex set containing all points in $S$.

You are given four integers $n$, $a$, $b$, and $k$. You have a set $S$ of $n$ points, initialized as follows: $$ S = \{ (x, (ax + b) \bmod n) \mid x = 0, 1, \ldots, n-1 \}. $$

You apply the following operation $k$ times: let $H$ be the convex hull of the set $S$, and then remove from $S$ all points that lie on the boundary of the convex hull $H$.

Note that $S$ can become empty. In that case, its convex hull is also empty, and its area is zero.

For each operation, determine the doubled area of the convex hull $H$. It can be shown that this value is always an integer.

洋葱在世界各地的烹饪中被广泛使用。本题涉及几何学中的一种“剥洋葱”过程。

若平面上某点集满足：对其中任意两点 $p$ 和 $q$，连接 $p$ 与 $q$ 的线段完全包含于该点集中，则称该点集为凸集。对于一个点集 $S$，其凸包是指包含 $S$ 中所有点的最小凸集。

给定四个整数 $n$、$a$、$b$ 和 $k$。初始时，你有一个包含 $n$ 个点的集合 $S$，定义如下：

$$S = \{ (x, (ax + b) \bmod n) \mid x = 0, 1, \ldots, n-1 \}.$$

你将执行以下操作共 $k$ 次：令 $H$ 为当前点集 $S$ 的凸包，然后从 $S$ 中移除所有位于凸包 $H$ 边界上的点。

注意：$S$ 可能变为空集。此时其凸包也为空，面积为零。

对每次操作，请计算凸包 $H$ 的两倍面积。可以证明该值恒为整数。

The input consists of a single line containing four integers $n$, $a$, $b$, and $k$ ($1 \le n \le 10^9$; $0 \le a, b \lt n$; $1 \le k \le 300$).

输入包含一行，其中为四个整数 $n$、$a$、$b$ 和 $k$（$1 \le n \le 10^9$；$0 \le a, b \lt n$；$1 \le k \le 300$）。

Output $k$ lines. The $i$-th line should contain an integer representing the doubled area of the convex hull in the $i$-th operation.

输出 $k$ 行。第 $i$ 行应包含一个整数，表示第 $i$ 次操作中凸包的面积的两倍。

Explanation for the sample input/output #1

Figure L.1 illustrates the points in $S$ and the boundary of the convex hull in the first operation. The area of the convex hull is $4$, and thus the doubled area is $8$.

Figure L.1: Illustration of Sample Input #1.

Explanation for the sample input/output #2

Figure L.2 illustrates the boundaries in the first four operations. The set $S$ becomes empty after the fourth operation. The area for the fifth operation is $0$.

Figure L.2: Illustration of Sample Input #2.

样例输入/输出 #1 的说明

图 L.1 展示了第一次操作中集合 $S$ 中的点以及凸包的边界。该凸包的面积为 $4$，因此其两倍面积为 $8$。

图 L.1：样例输入 #1 示意图。

样例输入/输出 #2 的说明

图 L.2 展示了前四次操作中的凸包边界。在第四次操作后，集合 $S$ 变为空集。第五次操作的面积为 $0$。

图 L.2：样例输入 #2 示意图。