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.

Input

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$$$).

Output

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

Note

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$$$.

$\text{[math]}$

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$$$.

$\text{[math]}$

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

Onion

Examples