题目描述

洋葱在世界各地的美食中被广泛使用。本题讨论的是几何中的“洋葱剥皮”过程。

在二维平面中，一组点是凸的，如果对于集合中的任意两点 $p$ 和 $q$，连接 $p$ 和 $q$ 的线段都完全包含在该集合中。对于一组点 $S$，它的凸包是包含 $S$ 的最小的凸集。

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

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

你要进行如下操作 $k$ 次：令 $H$ 为集合 $S$ 的凸包，然后将 $S$ 中所有在 $H$ 的边界上的点都从 $S$ 中移除。

注意，$S$ 可能会变为空集。在这种情况下，它的凸包也是空的，面积为零。

对于每一次操作，输出相应的凸包 $H$ 的面积的两倍。可以证明，这个结果总是整数。

输入格式

输入包含一行，四个整数 $n$、$a$、$b$ 和 $k$，满足 $1 \le n \le 10^9$，$0 \le a, b < n$，$1 \le k \le 300$。

输出格式

输出 $k$ 行，第 $i$ 行为第 $i$ 次操作后的凸包的面积的两倍。

4 1 2 1

8

37 14 7 5

2257
1406
592
74
0

提示

样例输入输出 #1 说明

下图展示了 $S$ 中的点和第一次操作中凸包的边界。凸包的面积为 $4$，其两倍为 $8$。

:::align{center} :::

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

样例输入输出 #2 说明

下图展示了前四次操作中凸包的边界。第 $4$ 次操作后，$S$ 变为空集。第 $5$ 次操作的面积为 $0$。

:::align{center} :::

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

由 ChatGPT 5 翻译