给定一个大小为 $N$ 的非负整数集合 $S = \{S_1, S_2, \dots, S_N\}$。 有一个变量 $x$，初始值为 $S_1$。你可以执行任意次数以下操作：

• 从 $S$ 中选择一个元素记为 $y$。如果满足以下条件，则将 $x$ 替换为 $y$：
  • 条件：设 $X_j$ 和 $Y_j$ 分别为 $x$ 和 $y$ 在三进制表示下第 $3^j$ 位上的数字。满足 $X_j > Y_j$ 的索引 $j$ 的数量至多为 1。

判断在执行若干次操作后，是否可以将 $x$ 变为 $S_N$。

输入格式

输入通过标准输入给出，格式如下：

$N$ $S_1 \ S_2 \ \dots \ S_N$

• 所有输入值均为整数。
• $2 \le N \le 2 \times 10^5$
• $0 \le S_i < 3^{12} \ (1 \le i \le N)$
• $S_i \neq S_j \ (1 \le i < j \le N)$

输出格式

如果可以将 $x$ 变为 $S_N$，输出 Yes，否则输出 No。

样例

样例输入 1

2
21 14

样例输出 1

Yes

样例输入 2

2
12 1

样例输出 2

No

样例输入 3

5
5 15 45 135 405

样例输出 3

Yes

说明

在第一个样例中，你可以按如下方式将 $x = 21$ 转换为 $x = 14$：

• 初始时，$x = 21$。选择 $y = 14$ 并执行操作。
  • 在三进制表示下，$x$ 为 $(X_2, X_1, X_0) = (2, 1, 0)$，$y$ 为 $(Y_2, Y_1, Y_0) = (1, 1, 2)$。
  • 仅在索引 $j = 2$ 处满足 $X_j > Y_j$，因此将 $x$ 替换为 $14$。