Toán trò chơi truyền hình (Game Show Math)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một dãy số và một giá trị đích. Chèn giữa các số các phép +, -, *, / để nhận đúng giá trị đích. Phép chia chỉ hợp lệ khi chia hết. Mọi giá trị trung gian phải nằm trong $[-32000,32000]$.

Input

Dòng đầu chứa $n$. Dòng hai chứa $n$ số nguyên. Dòng ba chứa giá trị đích.

Output

In một biểu thức hợp lệ có dạng a1 op a2 ... =target, hoặc NO EXPRESSION nếu không tồn tại.

Subtask

• Subtask 1 — 20 điểm: dữ liệu nhỏ, phù hợp để kiểm tra cách trực tiếp hoặc DP cơ bản.
• Subtask 2 — 30 điểm: dữ liệu trung bình, yêu cầu lưu trạng thái hợp lý.
• Subtask 3 — 50 điểm: toàn bộ giới hạn của gói Phước Hưng OJ.

Ví dụ

Input

5
1 2 3 4 5
15

Output

1+2+3+4+5=15

Giải thích

Kết quả được tính đúng theo quy tắc của đề. Đây là một trường hợp nhỏ để đối chiếu định dạng vào/ra trước khi nộp bài.