洋葱在世界各地的烹饪中被广泛使用。本题是关于几何中的“剥洋葱”过程。

如果对于二维平面上点集中的任意一对点 $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