Grădinarul Hu

Hu’s Garden can be visualized as a Cartesian coordinate system. He wants to choose a triangle from his garden in which to plant more flowers. He has already decided on two of the lines that form the triangle, and you must help him find the third one, knowing that he wants to plant exactly $k$ flowers and that flowers are planted at every point with integer coordinates inside and on the boundary of the triangle, and only at those locations. He also wants flowers to be planted at the vertices of the triangle.

Task

Formally, you are given a natural number $n$, which represents the size of a $2D$ plane, and $2$ lines defined by equations of the form $y = \frac{ax + b}{c}$, where $a$, $b$, $c$ are natural numbers and $c \not= 0$. You must find $3$ points (with integer coordinates) in the plane that form a triangle such that it contains $k$ lattice points (with integer coordinates) on its boundary or in its interior, and among the lines determined by the $3$ vertices, $2$ of them are the given ones.

Input Data

On the first line you will read, in order, $8$ numbers: $n$, $k$, $a_1$, $b_1$, $c_1$, $a_2$, $b_2$, $c_2$; where $n$ is the size of the $2D$ plane, $k$ is the number of flowers inside the triangle, $a_1$, $b_1$ and $c_1$ are the parameters of the first line, and $a_2$, $b_2$ and $c_2$ are the parameters of the second line.

Output Data

If a solution exists, you must output $6$ numbers separated by a space: $x_1$, $y_1$, $x_2$, $y_2$, $x_3$ and $y_3$, representing the coordinates of the $3$ points. Otherwise, you must output $-1$.

Constraints

• $1 \leq n \leq 1 \ 000 \ 000$
• $0 \le k \le 2 \ 000 \ 000 \ 000$
• $-2 \ 000 \ 000 \ 000 \le a_1, b_1, c_1, a_2, b_2, c_2 \le 2 \ 000 \ 000 \ 000$
• The plane is considered to have vertices at the points $(0, 0)$, $(0, n)$, $(n, 0)$ and $(n, n)$.
• It is guaranteed that the given lines intersect at a single point and that this point is a lattice point with coordinates between $0$ and $n$.
• The triangle must have all vertices distinct in order to be considered valid.
• If multiple solutions exist, any of them may be output.

Example 1

stdin

10 6 1 5 1 0 6 1

stdout

1 6 0 5 5 6

Explanation

In the first example, a valid solution is $(1, 6)$, $(0, 5)$, $(5, 6)$. The first line is the one colored orange, the second one is colored blue, and in green we have the third line determined by two of the points. In red we have the lattice points inside and on the sides of the resulting triangle.

Another valid solution, defined by the points $(1, 6)$, $(3, 6)$ and $(3, 8)$, can be seen in the image below. The triangle defined by the $3$ lines also contains $k = 6$ lattice points.

Example 2

stdin

80 52 -1 80 8 1 0 2

stdout

16 8 8 9 34 17