You are given five integers $n$, $dx_1$, $dy_1$, $dx_2$ and $dy_2$. You have to select $n$ distinct pairs of integers $(x_i, y_i)$ in such a way that, for every possible pair of integers $(x, y)$, there exists exactly one triple of integers $(a, b, i)$ meeting the following constraints:

$ \begin{cases} x \, = \, x_i + a \cdot dx_1 + b \cdot dx_2, \\ y \, = \, y_i + a \cdot dy_1 + b \cdot dy_2. \end{cases} $


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^5$).

The second line contains two integers $dx_1$ and $dy_1$ ($-10^6 \le dx_1, dy_1 \le 10^6$).

The third line contains two integers $dx_2$ and $dy_2$ ($-10^6 \le dx_2, dy_2 \le 10^6$).


-----Output-----

If it is impossible to correctly select $n$ pairs of integers, print NO.

Otherwise, print YES in the first line, and then $n$ lines, the $i$-th of which contains two integers $x_i$ and $y_i$ ($-10^9 \le x_i, y_i \le 10^9$).

If there are multiple solutions, print any of them.


-----Examples-----

Input
4
2 0
0 2
Output
YES
0 0
0 1
1 0
1 1
Input
5
2 6
1 5
Output
NO
Input
2
3 4
1 2
Output
YES
0 0
0 1


-----Note-----

None

Source: codeforces | Difficulty: VERY_HARD
Tags: Mathematics

Geometry

Implementation


Solutions:
n = int(input())
v1 = list(map(int, input().split()))
v2 = list(map(int, input().split()))
if v1[0] < 0:
	v1[0] *= -1
	v1[1] *= -1
if v2[0] < 0:
	v2[0] *= -1
	v2[1] *= -1
while v2[0]:
	sub = v1[0] // v2[0]
	v1[0] -= v2[0] * sub
	v1[1] -= v2[1] * sub
	(v1, v2) = (v2, v1)
y = abs(v2[1])
x = abs(v1[0])
if x * y == n:
	print('YES')
	out = []
	for i in range(x):
		for j in range(y):
			out.append(str(i) + ' ' + str(j))
	print('\n'.join(out))
else:
	print('NO')