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

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\). Зверніть увагу, відповідь не потрібно мінімізовувати.