D

 D - 燕尾服

OHgg 是一个情趣高雅的人，他经常和他的朋友们打扑克. 今天他们去了一个赌场，那里有 n 个玩家 (包括 OHgg 自己) 并且他们现在桌子上都有一些筹码. 他们第 i个人有 ai 的筹码.

每个人有任意次操作，每次操作都可以让自己的筹码数量 \times2×2 或 \times3×3. 如果所有人的筹码都可以变得相同，那么 OHgg 就赢了. OHgg 有可能赢吗?

Input

第一行一个正整数 n (2 ≤ n ≤ 105), 玩家的数量.

第二行有 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109) — 玩家手里的筹码数量.

Output

如果所有玩家可以让手里的筹码数量相同，输出 "Yes" (不带引号) ，否则输出"No"

Examples

Input

4
75 150 75 50

Output

Yes

Input

3
100 150 250

Output

No

Note

第一个样例中第一个和第三个玩家可以让自己手里的筹码乘两次 22, 第二个玩家可以乘一次 22 并且第四个玩家乘一次 22 和一次 33.

可以看出第二个样例几个玩家无法让筹码相同.

Sponsor

/*这题乘二或乘三相等的前提是有在此倍数下
的共同的最简基数。比如10和12，不论怎样乘
2成3都不会相等，但如果换了倍数便有可能相
等（比如在倍数5,6下）所以这题就转化成了在
倍数2,3下看基数是否相等*/#include <iostream>
using namespace std;
int min_(int k) {//找基数while (k % 2 == 0) {k /= 2;}while (k % 3 == 0) {k /= 3;}return k;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;int count = 0, t, low;cin >> t;low = t;low = min_(low);int i;for (i = 1; i < n; i++) {cin >> t;int k = min_(t);if (k == low) continue;else {//有一个不相等直接输出cout << "No";return 0;}}if (i == n) cout << "Yes";return 0;
}

D

 D - 燕尾服

OHgg 是一个情趣高雅的人，他经常和他的朋友们打扑克. 今天他们去了一个赌场，那里有 n 个玩家 (包括 OHgg 自己) 并且他们现在桌子上都有一些筹码. 他们第 i个人有 ai 的筹码.

每个人有任意次操作，每次操作都可以让自己的筹码数量 \times2×2 或 \times3×3. 如果所有人的筹码都可以变得相同，那么 OHgg 就赢了. OHgg 有可能赢吗?

Input

第一行一个正整数 n (2 ≤ n ≤ 105), 玩家的数量.

第二行有 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109) — 玩家手里的筹码数量.

Output

如果所有玩家可以让手里的筹码数量相同，输出 "Yes" (不带引号) ，否则输出"No"

Examples

Input

4
75 150 75 50

Output

Yes

Input

3
100 150 250

Output

No

Note

第一个样例中第一个和第三个玩家可以让自己手里的筹码乘两次 22, 第二个玩家可以乘一次 22 并且第四个玩家乘一次 22 和一次 33.

可以看出第二个样例几个玩家无法让筹码相同.

Sponsor

/*这题乘二或乘三相等的前提是有在此倍数下
的共同的最简基数。比如10和12，不论怎样乘
2成3都不会相等，但如果换了倍数便有可能相
等（比如在倍数5,6下）所以这题就转化成了在
倍数2,3下看基数是否相等*/#include <iostream>
using namespace std;
int min_(int k) {//找基数while (k % 2 == 0) {k /= 2;}while (k % 3 == 0) {k /= 3;}return k;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;int count = 0, t, low;cin >> t;low = t;low = min_(low);int i;for (i = 1; i < n; i++) {cin >> t;int k = min_(t);if (k == low) continue;else {//有一个不相等直接输出cout << "No";return 0;}}if (i == n) cout << "Yes";return 0;
}