問題文

大きさ N の非負整数の集合 S = \{S_1, S_2, \dots, S_N\} が与えられます。

変数 x があり、はじめ x = S_1 です。あなたは以下の操作を何度でも行うことができます。

• y \in S を 1 つ選ぶ。y が以下の条件を満たすとき、x に y を代入する。
  • 条件 : x と y をそれぞれ三進数表記したときの 3^j の位の数字を X_j と Y_j とする。このとき、X_j \gt Y_j なる j の個数は 1 個以下である。

この操作を何回か行って x = S_N にできるかどうか判定してください。

制約

• 2 \le N \le 2 \times 10^5
• 0 \le S_i \lt 3^{12}
• i \ne j ならば S_i \ne S_j
• 入力はすべて整数

入力例 1

2
21 14

出力例 1

Yes

以下のようにして x = 21 の状態から x = 14 にすることができます。

• はじめ、x = 21 である。y = 14 を選んで操作を行う。
  • x と y をそれぞれ三進数表記すると、(X_2, X_1, X_0) = (2, 1, 0),\ (Y_2, Y_1, Y_0) = (1, 1, 2) である。
  • X_j \gt Y_j なる j は j = 2 の 1 個であるから、x に 14 を代入する。

入力例 2

2
12 1

出力例 2

No

x = 12 と y = 1 をそれぞれ三進数表記すると、(X_2, X_1, X_0) = (1, 1, 0),\ (Y_2, Y_1, Y_0) = (0, 0, 1) です。

X_j \gt Y_j なる j は j = 1, 2 の 2 個であるので、x = 12 の状態から 1 を代入することはできません。

入力例 3

5
5 15 45 135 405

出力例 3

Yes