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 *a*_{i} 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?

First line of input contains an integer *n* (2 ≤ *n* ≤ 10^{5}), the number of players.

The second line contains *n* integer numbers *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 10^{9}) — the bids of players.

提交代码