Щасливе спільне кратне

Limits: 2 sec., 256 MiB

Задано $m$ натуральних чисел $n_i$.

Як відомо, є всього дві щасливі цифри — $4$ та $7$. Відповідно до цього число є щасливим, якщо воно містить у своєму десятковому записі тільки щасливі цифри. Наприклад, $47$ та $77474$ є щасливими числами.

Знайдіть щасливе число, яке є спільним кратним чисел $n_i$, або повідомте, що такого не існує.

Оскільки ваша відповідь може бути дуже великою, виведіть її в стисненому вигляді.

Стиснена відповідь повинна складатись із цифр та круглих дужок.

Рядок $s$, огорнутий у дужки, після якого слідує число $k$, означає що рядок $s$ повторюється $k$ разів. Наприклад, $(47)6$, $(4747)3$, $(474747)2$, $(474747474747)1$ — це різні варіанти стиснення щасливого числа $474747474747$.

Рядки можна конкатенувати. Наприклад, $(4)2(74)3(47)1$ — це один із способів стиснення числа $4474747447$.

Рядки можуть бути огорнуті в дужки та сконкатеновані кілька разів. Наприклад, $((4)2(7)3)2$ — один із способів стиснення числа $4477744777$, а $(((47)3(4)2(7)1)2(744)5)1$ — один із способів стиснення числа $474747447474747447744744744744744$.

Формально, стиснений рядок повинен задовольняти таку форму Бекуса-Наура:

Зверніть увагу, що вам не потрібно мінімізовувати ні щасливе число, яке є відповіддю на задачу, ні довжину стисненого числа.

Input

У першому рядку задано ціле число $m$ — кількість чисел, для яких треба знайти щасливе спільне кратне.

У другому рядку записано $m$ натуральних чисел $n_i$, для яких треба знайти щасливе спільне кратне.

Output

Якщо існує щасливе число, яке є спільним кратним чисел $n_i$, виведіть його в стисненому вигляді довжиною не більшою за $10^5$. Для обмежень задачі можна довести, що якщо існує таке щасливе число то існує стиснена відповідь, яка не перевищує $10^5$ символів.

Якщо такого числа не існує, виведіть -1.

Constraints

$1 \le m \le 100$,

$1 \le n_i \le 10^5$.

Samples

Input (stdin) сopy	Output (stdout) сopy
1 24	(7)1(4)2

Input (stdin) сopy	Output (stdout) сopy
7 3 7 13 37 47 101 9901	(47)6

Input (stdin) сopy	Output (stdout) сopy
2 8 9	(((47)3(4)2(7)1)2(744)5)1

Input (stdin) сopy	Output (stdout) сopy
3 4 44 2000	-1

Notes

Відповідь на перший приклад дорівнює $744 = 24 \cdot 31$.

Відповідь на другий приклад дорівнює $474747474747 = 3 \cdot 7 \cdot 13 \cdot 37 \cdot 47 \cdot 101 \cdot 9901$.

У третьому прикладі іншою правильною відповіддю є $(4)3(7)1(4)2$. Зверніть увагу, відповідь не потрібно мінімізовувати.