洋葱广泛用于世界各地的美食中。这道题是关于几何学中的“洋葱皮”过程。
二维平面中的一组点是 凸 如果对于集合中的任意一对点 $$$p$$$ 和 $$$q$$$,连接 $$$p$$$ 和 $$$q$$$ 的线段完全包含在集合中。对于一组点 $$$S$$$,其 凸包 是包含 $$$S$$$ 中所有点的最小凸集。
给定四个整数 $$$n$$$、$$$a$$$、$$$b$$$ 和 $$$k$$$。您有一组 $$$S$$$ 的 $$$n$$$ 点,初始化如下: $$S = \{ (x, (ax + b) \bmod n) \mid x = 0, 1, \ldots, n-1 \}.$$
您应用以下操作 $$$k$$$ 次:令 $$$H$$$ 为集合 $$$S$$$ 的凸包,然后从 $$$S$$$ 中删除位于凸包 $$$H$$$ 边界上的所有点。
请注意,$$$S$$$ 可以变为空。在这种情况下,它的凸包也是空的,并且它的面积为零。
对于每个操作,确定 翻倍 凸包的面积$$$H$$$。可以证明这个值始终是一个整数。
输入
输入由一行组成,其中包含四个整数 $$$n$$$、$$$a$$$、$$$b$$$ 和 $$$k$$$ ($$$1 \le n \le 10^9$$$; $$$0 \le a, b \lt n$$$; $$$1 \le k \le 300$$$)。
输出
输出 $$$k$$$ 行。第 $$$i$$$ 行应包含一个整数,表示第 $$$i$$$ 操作中凸包的双倍面积。
示例
输入复制
4 1 2 1
输出复制
8
输入复制
37 14 7 5
输出复制
2257 1406 592 74 0
输入复制
280 40 12 4
输出复制
131040 82880 39200 0
注意
示例输入/输出#1 的说明
图L.1说明了第一个操作中$$$S$$$中的点和凸包的边界。凸包的面积为 $$$4$$$,因此加倍面积为 $$$8$$$。
![]() |
| 图 L.1:示例输入 #1 的图示。 |
示例输入/输出#2 的说明
图 L.2 说明了前四个操作的边界。第四次操作后,集合 $$$S$$$ 变空。第五次操作的区域是$$$0$$$。
![]() |
| 图 L.2:示例输入 #2 的图示。 |

