洋葱在世界各地的烹饪中被广泛使用。本题是关于几何中的“剥洋葱”过程。
如果对于二维平面上点集中的任意一对点 $p$ 和 $q$，连接 $p$ 和 $q$ 的线段都完全包含在该集合中，则称该点集是凸的。对于点集 $S$，其凸包是包含 $S$ 中所有点的最小凸集。
给你四个整数 $n$、$a$、$b$ 和 $k$。你有一个包含 $n$ 个点的集合 $S$，初始化如下：
$$S = \{(x, (ax + b) \bmod n) \mid x = 0, 1, \dots, n - 1\}$$
你需要执行以下操作 $k$ 次：设 $H$ 为点集 $S$ 的凸包，然后从 $S$ 中移除所有位于凸包 $H$ 边界上的点。
注意，$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$ 次操作中凸包面积的两倍。
样例
输入样例 1
4 1 2 1
输出样例 1
8
说明 1
图 L.1 展示了第一次操作中 $S$ 中的点以及凸包的边界。凸包的面积为 4，因此其两倍面积为 8。
图 L.1：样例输入 1 的示意图。
输入样例 2
37 14 7 5
输出样例 2
2257 1406 592 74 0
说明 2
图 L.2 展示了前四次操作中的边界。在第四次操作后，集合 $S$ 变为空集。第五次操作的面积为 0。
图 L.2：样例输入 2 的示意图。
输入样例 3
280 40 12 4
输出样例 3
131040 82880 39200 0