A square billiard table is located in the coordinate plane, with its vertices at coordinates $(L, L)$, $(L, -L)$, $(-L, L)$, and $(-L, -L)$. Currently, a billiard ball is at rest at point $(x_1, y_1)$, while a hole is located at point $(x_2, y_2)$. The ball and the hole are not on the edge of the table and are at different positions.

If we hit the ball, it will start moving in a straight line. If it hits the edge of the table, it bounces off such that the angle of incidence equals the angle of reflection, and it continues to move in a straight line. It stops only when it reaches one of the four corners of the table or the hole.

Using his great strength, Mr. Malnar once hit the ball so hard that no one but him could see its path. The only thing known is that the ball ended up in the hole, and surviving witnesses further claim that, by using the frequency of the sound created by the fast-moving ball, they could conclude that the ball bounced off the edge of the table at most $n$ times during its path.

The image shows all possible paths for the first sample case when $k = 1$.

Analysts are interested in all the ways the ball could have moved. Determine, for every integer $0 \le k \le n$, how many different paths the ball could have taken such that it bounced off the edge of the table exactly $k$ times before ending up in the hole. It is possible to prove that all answers are finite numbers that fit into a 32-bit integer type.

Input

The first line contains the integers $L$ ($2 \le L \le 1\,000\,000$) and $n$ ($1 \le n \le 500$).

The second line contains the integers $x_1, y_1, x_2, y_2$ ($-L < x_1, y_1, x_2, y_2 < L$). It is guaranteed that $(x_1, y_1) \neq (x_2, y_2)$.

Output

Print $n + 1$ space-separated integers which, in order from $k = 0$ to $k = n$, represent the number of different paths of the ball with exactly $k$ bounces.

Examples

Input 1

2 1
-1 1 -1 -1

Output 1

1 3

Input 2

4 3
0 0 1 1

Output 2

1 4 6 12