Limak is an old brown bear. He often plays poker with his friends. Today they went to a casino. There are n players (including Limak himself) and right now all of them have bids on the table. i-th of them has bid with size ai dollars.

Each player can double his bid any number of times and triple his bid any number of times. The casino has a great jackpot for making all bids equal. Is it possible that Limak and his friends will win a jackpot?

Input

First line of input contains an integer n (2 ≤ n ≤ 105), the number of players.

The second line contains n integer numbers a1, a2, ..., an (1 ≤ ai ≤ 109) — the bids of players.

Output

Print "Yes" (without the quotes) if players can make their bids become equal, or "No" otherwise.

Examples

Input

4
75 150 75 50


Output

Yes


Input

3
100 150 250


Output

No

Note

In the first sample test first and third players should double their bids twice, second player should double his bid once and fourth player should both double and triple his bid.

It can be shown that in the second sample test there is no way to make all bids equal.

Difficulty: EASY
Tags: Mathematics

Number theory

Implementation

Starter code:

Solutions:
n = int(input())
arr = [int(x) for x in input().split()]
for i in range(n):
	while arr[i] % 2 == 0:
		arr[i] /= 2
	while arr[i] % 3 == 0:
		arr[i] /= 3
print('Yes' if all((arr[0] == arr[i] for i in range(n))) else 'No')


def dividers(n):
	if n == 1:
		return set()
	elif n == 2:
		a = set()
		a.add(2)
		return a
	elif n == 3:
		a = set()
		a.add(3)
		return a
	i = 2
	dividers = []
	while n > 1 and i * i <= n:
		if n % i == 0:
			if i in dividers:
				if i != 2 and i != 3:
					dividers.append(i)
			else:
				dividers.append(i)
			n //= i
			continue
		i += 1
	if i * i > n and n != 2 and (n != 3):
		dividers.append(n)
	ans = set()
	i1 = 0
	i2 = 0
	while i2 < len(dividers):
		if dividers[i2] != dividers[i1]:
			ans.add(dividers[i1] ** (i2 - i1))
			i1 = i2
		else:
			i2 += 1
	ans.add(dividers[i1] ** (i2 - i1))
	return ans
n = int(input())
mas = list(set((int(e) for e in input().split())))
mas[0] = dividers(mas[0])
ans = True
for_help = set()
for_help.add(2)
for_help.add(3)
for i in range(len(mas) - 1):
	mas[i + 1] = dividers(mas[i + 1])
	if len((mas[i] ^ mas[i + 1]) - for_help) != 0:
		ans = False
		break
if ans:
	print('Yes')
else:
	print('No')


n = int(input())
n = None
f = True
for i in map(int, input().split()):
	while i % 2 == 0:
		i //= 2
	while i % 3 == 0:
		i //= 3
	if n == None:
		n = i
	elif i != n:
		f = False
		break
if f:
	print('Yes')
else:
	print('No')


from sys import stdin, stdout
from collections import Counter
from math import ceil
from bisect import bisect_left
from bisect import bisect_right
import math
ai = lambda : list(map(int, stdin.readline().split()))
ei = lambda : map(int, stdin.readline().split())
ip = lambda : int(stdin.readline().strip())
n = ip()
li = ai()
for i in range(n):
	while li[i] % 2 == 0:
		li[i] //= 2
	while li[i] % 3 == 0:
		li[i] //= 3
for i in range(1, n):
	if li[i] != li[0]:
		exit(print('No'))
print('Yes')


n = int(input())
a = list(map(int, input().split()))
for i in range(len(a)):
	while a[i] % 2 == 0:
		a[i] = a[i] // 2
	while a[i] % 3 == 0:
		a[i] = a[i] // 3
flag = 1
for i in range(1, len(a)):
	if a[i] != a[0]:
		print('No')
		flag = 0
		break
if flag:
	print('Yes')


def solve(arr, n):
	for i in range(n):
		while arr[i] % 2 == 0:
			arr[i] //= 2
		while arr[i] % 3 == 0:
			arr[i] //= 3
	arr.sort()
	if arr[0] == arr[-1]:
		print('Yes')
	else:
		print('No')
n = int(input())
arr = list(map(int, input().split()))
solve(arr, n)


n = int(input())
a = list(map(int, input().split()))
p2 = 2 ** 7
p3 = 3 ** 7
for i in range(n):
	while a[i] % p3 == 0:
		a[i] /= p3
		goon = True
	while a[i] % p2 == 0:
		a[i] /= p2
		goon = True
	while a[i] % 3 == 0:
		a[i] /= 3
		goon = True
	while a[i] % 2 == 0:
		a[i] /= 2
		goon = True
ans = 'Yes'
for i in range(1, n):
	if a[0] != a[i]:
		ans = 'No'
print(ans)


def divide(n):
	while True:
		if n % 2 == 0:
			n //= 2
		elif n % 3 == 0:
			n //= 3
		else:
			break
	return n
n = int(input())
l = [int(i) for i in input().split()]
itJustWorks = True
rem = divide(l[0])
for i in range(1, n):
	if rem != divide(l[i]):
		itJustWorks = False
		break
print('Yes') if itJustWorks else print('No')


n = int(input())
a = input().split()
for i in range(n):
	a[i] = int(a[i])

def thanhloc(x):
	while x % 2 == 0:
		x = x // 2
	while x % 3 == 0:
		x = x // 3
	return x
res = 'Yes'
a[0] = thanhloc(a[0])
for i in range(1, n):
	a[i] = thanhloc(a[i])
	if a[i] != a[i - 1]:
		res = 'No'
		break
print(res)


n = int(input())
a = [int(x) for x in input().split()]
for i in range(n):
	while a[i] % 2 == 0:
		a[i] /= 2
	while a[i] % 3 == 0:
		a[i] /= 3
ok = True
for i in range(n):
	if a[i] != a[0]:
		ok = False
print('YES' if ok else 'NO')


n = int(input())
x = [int(i) for i in input().split(' ')]
for j in range(len(x)):
	while x[j] % 2 == 0:
		x[j] /= 2
	while x[j] % 3 == 0:
		x[j] /= 3
if len(set(x)) == 1:
	print('Yes')
else:
	print('No')


import itertools as it
import math as mt
import collections as cc
import heapq as hp
import sys
import collections as cc
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))

def lcm(a, b):
	return a * b // mt.gcd(a, b)
(n,) = I()
l = I()
ans = l[0]
for i in range(1, n):
	ans = mt.gcd(ans, l[i])
tf = 1
for i in l:
	now = i // ans
	while now % 2 == 0:
		now //= 2
	while now % 3 == 0:
		now //= 3
	if now != 1:
		tf = 0
print('YES' if tf else 'NO')


n = int(input())
a = list(map(int, input().split()))
for i in range(n):
	while a[i] % 2 == 0:
		a[i] //= 2
	while a[i] % 3 == 0:
		a[i] //= 3
print('YES' if max(a) == min(a) else 'NO')


import sys
import io

def div(n):
	while n % 2 == 0:
		n //= 2
	while n % 3 == 0:
		n //= 3
	return n

def solve(n, bs):
	assert 2 <= n <= 10 ** 5
	bs = list(set(bs))
	for b in bs:
		assert 1 <= b <= 10 ** 9
	(b, rest) = (bs[0], bs[1:])
	v = div(b)
	for r in rest:
		if div(r) != v:
			return 'No'
	return 'Yes'

def getinput():

	def getint():
		return int(input())

	def getints_line():
		return list(map(int, input().split(' ')))

	def getints(n):
		return [getint() for _ in range(n)]

	def getints_lines(n):
		return [getints_line() for _ in range(n)]
	return [getint(), getints_line()]

def iosolve():
	return str(solve(*getinput()))

def main():
	if sys.stdin.isatty():
		test()
	stdin_lines = getstdin_lines()
	sys.stdin = io.StringIO('\n'.join(stdin_lines))
	if stdin_lines:
		print(iosolve())
	else:
		test()

def test():
	IO_TEST_CASES = [('4\n75 150 75 50\n            ', 'Yes\n            '), ('3\n100 150 250\n            ', 'No\n            ')]
	TEST_CASES = []
	import unittest
	import sys
	import io

	class Assert(unittest.TestCase):

		def equal(self, a, b):
			self.assertEqual(a, b)

		def float_equal(self, actual, expect, tolerance):
			self.assertTrue(expect - tolerance < actual < expect + tolerance)
	art = Assert()
	for (inputs, expect) in TEST_CASES:
		art.equal(solve(*inputs), expect)
	for (stdin, expect) in IO_TEST_CASES:
		sys.stdin = io.StringIO(stdin.strip())
		art.equal(iosolve(), expect.strip())

def getstdin_lines():
	stdin = []
	while 1:
		try:
			stdin.append(input())
		except EOFError:
			break
	return stdin
main()


def main():
	import sys
	from fractions import gcd
	n = int(input())
	a = [int(i) for i in input().split()]
	t = a[0]
	for i in range(1, n):
		t = gcd(a[i], t)
	a = [a[i] // t for i in range(n)]
	for i in range(n):
		while a[i] % 2 == 0:
			a[i] //= 2
		while a[i] % 3 == 0:
			a[i] //= 3
		if a[i] > 1:
			print('No')
			sys.exit()
	print('Yes')
main()


s = input()
(*v,) = (int(x) for x in input().split())
for i in range(len(v)):
	while v[i] % 2 == 0 or v[i] % 3 == 0:
		v[i] = v[i] / 2 if v[i] % 2 == 0 else v[i] / 3
	if i > 0 and v[i] != v[i - 1]:
		print('No')
		break
else:
	print('Yes')


import fractions
n = int(input())
l = [int(i) for i in input().split()]
gcd = l[0]
for i in range(1, n):
	gcd = fractions.gcd(gcd, l[i])
while gcd % 2 == 0:
	gcd /= 2
while gcd % 3 == 0:
	gcd /= 3
ans = 'YES'
for i in range(n):
	k = l[i]
	t = 1
	t1 = 1
	while k % (2 * t) == 0:
		t = t * 2
	while k % (t1 * 3) == 0:
		t1 = t1 * 3
	if gcd * t * t1 != l[i]:
		ans = 'NO'
		break
print(ans)


__author__ = 'JohnHook'
n = list(map(int, input().split()))[0]
a = list(map(int, input().split()))
for i in range(len(a)):
	while a[i] % 2 == 0:
		a[i] //= 2
	while a[i] % 3 == 0:
		a[i] //= 3
if a.count(a[0]) == len(a):
	print('Yes')
else:
	print('No')


def fun(num):
	while num % 2 == 0:
		num //= 2
	while num % 3 == 0:
		num //= 3
	return num
n = int(input())
flag = True
p = 0
c = 0
for i in input().split():
	if p == 0:
		p = fun(int(i))
	else:
		c = fun(int(i))
		if c != p:
			flag = False
print('Yes') if flag else print('No')


def f(n):
	while n % 3 == 0:
		n //= 3
	while n % 2 == 0:
		n //= 2
	return n
n = int(input())
ar = list(map(int, input().split()))
for x in range(n):
	ar[x] = f(ar[x])
for x in range(1, n):
	if ar[x] != ar[x - 1]:
		print('No')
		break
else:
	print('Yes')


n = int(input())
arr = list(map(int, input().split()))
for i in range(n):
	while arr[i] % 2 == 0:
		arr[i] //= 2
	while arr[i] % 3 == 0:
		arr[i] //= 3
eq = True
for i in range(1, n):
	if arr[i] != arr[i - 1]:
		eq = False
if eq:
	print('Yes')
else:
	print('No')


import sys
lines = sys.stdin.read().split('\n')

def gcd(a, b):
	if a % b == 0:
		return b
	else:
		return gcd(b, a % b)

def gcds(nums):
	if len(nums) == 1:
		return nums[0]
	else:
		tmp = []
		for i in range(len(nums) // 2):
			tmp.append(gcd(nums[2 * i], nums[2 * i + 1]))
		if len(nums) % 2 != 0:
			tmp.append(nums[-1])
		return gcds(tmp)

def check(num):
	while num % 2 == 0:
		num = num // 2
	while num % 3 == 0:
		num = num // 3
	if num > 1:
		return False
	else:
		return True
n = int(lines[0])
nums = list(map(int, lines[1].split(' ')))
g = gcds(nums)
for num in nums:
	case = num // g
	if not check(case):
		print('No')
		sys.exit(0)
print('Yes')


from sys import stdin, stdout
input = stdin.readline
n = int(input())
a = list(map(int, input().split()))

def fac(n, d):
	ans = 0
	while n % d == 0:
		ans += 1
		n //= d
	return ans
f2 = [fac(i, 2) for i in a]
f3 = [fac(i, 3) for i in a]
m2 = max(f2)
m3 = max(f3)
for i in range(n):
	if f2[i] < m2:
		a[i] *= 2 ** (m2 - f2[i])
	if f3[i] < m3:
		a[i] *= 3 ** (m3 - f3[i])
if a.count(a[0]) != n:
	stdout.write('No')
else:
	stdout.write('Yes')


def main():
	gcd = lambda a, b: a if b == 0 else gcd(b, a % b)
	n = int(input())
	a = list(map(int, input().split()))
	G = a[0]
	for i in range(n):
		while a[i] % 3 == 0:
			a[i] //= 3
		while a[i] % 2 == 0:
			a[i] //= 2
		G = gcd(a[i], G)
	f = not bool(sum((G != a[i] for i in range(n))))
	print('Yes' if f else 'No')
main()


from math import ceil
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
	l = 0
	r = 40
	while l + 1 < r:
		m = (l + r) // 2
		if a[i] % 2 ** m == 0:
			l = m
		else:
			r = m
	a[i] //= 2 ** l
	l = 0
	r = 30
	while l + 1 < r:
		m = (l + r) // 2
		if a[i] % 3 ** m == 0:
			l = m
		else:
			r = m
	a[i] //= 3 ** l
k = a[0]
flag = True
for i in range(len(a)):
	if a[i] != k:
		print('No')
		flag = False
		break
if flag == True:
	print('Yes')


n = int(input())
lst = list(map(int, input().split()))
for i in range(n):
	while lst[i] % 2 == 0:
		lst[i] //= 2
	while lst[i] % 3 == 0:
		lst[i] //= 3
check = lst[0]
for i in range(n):
	if lst[i] != check:
		print('No')
		break
else:
	print('Yes')


import sys
import math

def read_input(input_path=None):
	if input_path is None:
		f = sys.stdin
	else:
		f = open(input_path, 'r')
	n = int(f.readline())
	a = list(map(int, f.readline().split()))
	return (n, a)

def sol(n, a):
	for i in range(n):
		while a[i] % 2 == 0:
			a[i] //= 2
		while a[i] % 3 == 0:
			a[i] //= 3
	for i in range(1, n):
		if a[i] != a[0]:
			return ['NO']
	return ['YES']

def solve(input_path=None):
	return sol(*read_input(input_path))

def main():
	for line in sol(*read_input()):
		print(f'{line}')
main()


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def jud(x):
	while x % 2 == 0:
		x = x // 2
	while x % 3 == 0:
		x = x // 3
	if x == 1:
		return True
	return False
n = int(input())
a = list(map(int, input().split()))
x = a[0]
for i in range(n - 1):
	x = gcd(x, a[i + 1])
flag = True
for i in range(n):
	if not jud(a[i] // x):
		flag = False
		break
if flag:
	print('Yes')
else:
	print('No')


n = int(input())
a = list(map(int, input().split()))
rest = a[0]
while rest % 2 == 0 or rest % 3 == 0:
	if rest % 2 == 0:
		rest //= 2
	else:
		rest //= 3
for i in a[1:]:
	if i % rest != 0:
		print('No')
		exit()
	else:
		current = i // rest
		while current % 2 == 0 or current % 3 == 0:
			if current % 2 == 0:
				current //= 2
			else:
				current //= 3
		if current != 1:
			print('No')
			exit()
print('Yes')


n = int(input())
mas = list(map(int, input().split(' ')))
for i in range(n):
	while mas[i] % 2 == 0:
		mas[i] //= 2
	while mas[i] % 3 == 0:
		mas[i] //= 3
print('YES') if len(set(mas)) <= 1 else print('NO')


import sys
from math import gcd
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(n,) = I()
l = I()
gd = l[0]
for i in range(1, n):
	gd = gcd(gd, l[i])
pos = 0
for i in range(n):
	cr = l[i] // gd
	while cr % 2 == 0:
		cr //= 2
	while cr % 3 == 0:
		cr //= 3
	if cr != 1:
		pos = 1
		break
print('YNEOS'[pos::2])


def divby(m):
	for k in range(len(arr)):
		while arr[k] % m == 0:
			arr[k] /= m

def issame():
	return len(set(arr)) <= 1
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
divby(2)
divby(3)
if issame():
	print('Yes')
else:
	print('No')


def prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def p(n):
	if prime(n) and n not in [2, 3]:
		return n
	else:
		if n in [2, 3]:
			return 1
		i = 2
		result = 2
		while i < 4:
			if n % i == 0:
				n //= i
			else:
				i += 1
	return n
n = int(input())
array = list(map(int, input().split()))
f = True
used = []
if array[0] == array[1]:
	for i in array:
		if i not in used:
			used.append(i)
	array = used
a = p(array[0])
for i in array:
	if p(i) != a:
		f = False
		break
if f:
	print('Yes')
else:
	print('No')


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	n = I()
	a = LI()
	s = set()
	for c in a:
		while c % 2 == 0:
			c //= 2
		while c % 3 == 0:
			c //= 3
		s.add(c)
	if len(s) > 1:
		return 'No'
	return 'Yes'
print(main())


N = int(input())
x = [int(i) for i in input().split()]
for i in range(N):
	while x[i] % 2 == 0:
		x[i] //= 2
	while x[i] % 3 == 0:
		x[i] //= 3
T = True
for i in range(N - 1):
	if x[i] != x[i + 1]:
		T = False
print('Yes' if T else 'No')


N = input().split()
A = list(map(int, input().split()))

def reduce(N):
	if N % 2 == 0:
		return reduce(N / 2)
	if N % 3 == 0:
		return reduce(N / 3)
	return N
if len(set((reduce(a) for a in A))) == 1:
	print('Yes')
else:
	print('No')


n = int(input())
v = list(map(int, input().split()))
for i in range(n):
	while v[i] % 3 == 0:
		v[i] //= 3
	while v[i] % 2 == 0:
		v[i] >>= 1
n = v.pop(0)
for i in v:
	if i != n:
		print('No')
		exit()
print('Yes')


def check(p):
	while True:
		if p % 2 == 0:
			p = p // 2
		elif p % 3 == 0:
			p = p // 3
		else:
			return p
n = int(input())
a = list(map(int, input().split()))
x = check(a[0])
for i in range(1, n):
	temp = check(a[i])
	if temp != x:
		print('No')
		break
else:
	print('Yes')


n = int(input())
a = []
for x in input().split():
	bid = int(x)
	while bid % 2 == 0:
		bid /= 2
	while bid % 3 == 0:
		bid /= 3
	a.append(bid)
val = a[0]
jackpot = True
for i in range(1, n):
	if a[i] != val:
		jackpot = False
		break
if jackpot:
	print('YES')
else:
	print('NO')


leng = int(input())
vals = list(map(lambda x: int(x), input().split(' ')))
sbt = -1
for s in vals:
	while not s % 2:
		s = s // 2
	while not s % 3:
		s = s // 3
	if sbt == -1:
		sbt = s
	elif sbt != s:
		print('No')
		sbt = 0
		break
if sbt:
	print('Yes')


from sys import stdin, stdout
input = stdin.readline

def nod(a, b):
	if b == 0:
		return a
	else:
		return nod(b, a % b)

def good(a):
	while a > 1:
		if a % 2 == 0:
			a //= 2
		elif a % 3 == 0:
			a //= 3
		else:
			return False
	return True
n = int(input())
a = list(map(int, input().split()))
n = a[0]
for el in a[1:]:
	n = nod(n, el)
ans = None
if all(list(map(lambda x: good(x // n), a))):
	ans = 'Yes'
else:
	ans = 'No'
stdout.write(ans)


from sys import stdin, stdout
n = int(stdin.readline().rstrip())
(st, sh) = (list(map(int, stdin.readline().rstrip().split())), True)
for i in range(len(st)):
	while st[i] % 2 == 0:
		st[i] //= 2
	while st[i] % 3 == 0:
		st[i] //= 3
for i in range(1, n):
	sh = st[0] == st[i] and sh
stdout.write('Yes' if sh else 'No')


n = int(input())
A = []
A = [int(x) for x in input().split()]
for i in range(n):
	while A[i] % 2 == 0:
		A[i] = A[i] // 2
	while A[i] % 3 == 0:
		A[i] = A[i] // 3
for i in A:
	if i != A[0]:
		print('No')
		exit()
print('Yes')


__author__ = 'pxy'
n = int(input())
c = [int(i) for i in input().split()]
f = True
for j in range(n):
	while c[j] % 2 == 0:
		c[j] = c[j] // 2
	while c[j] % 3 == 0:
		c[j] = c[j] // 3
if max(c) == min(c):
	print('Yes')
else:
	print('No')


n = int(input())
bids = list(map(int, input().split()))
for i in range(n):
	while bids[i] % 2 == 0:
		bids[i] /= 2
	while bids[i] % 3 == 0:
		bids[i] /= 3
is_all_equal = True
for i in range(n - 1):
	if bids[i] != bids[i + 1]:
		is_all_equal = False
		break
if is_all_equal:
	print('Yes')
else:
	print('No')


from math import gcd
nb = int(input())
liste2 = []
liste = [int(x) for x in input().split()]

def pp():
	for loop in range(len(liste)):
		while liste[loop] % 2 == 0:
			liste[loop] //= 2
		while liste[loop] % 3 == 0:
			liste[loop] //= 3
		liste2.append(liste[loop])
	if liste2.count(liste2[0]) == len(liste2):
		return 'Yes'
	return 'No'
print(pp())