Make the target from four numbers

Interview

Time limit1sMemory limit128 MB

Summary

Decide whether the first four integers can form the fifth using each exactly once with +, -, *, / and parentheses.

Level: Medium5 of 10
Topics: Brute force, Backtracking, Recursion
Solved: No attempts yet

Problem

You are given five integers $n_1, n_2, n_3, n_4, n_5$ , and every one of them satisfies $0 \le n_i \le 100$ .

Join the first four numbers $n_1, n_2, n_3, n_4$ into one expression with addition, subtraction, multiplication, division (+, -, *, /) and parentheses. Each of the four numbers must appear exactly once, and you may put them in any order. Division is exact, so an intermediate value is allowed to be a fraction, but no expression may divide by zero.

Write a program that decides whether some such expression equals $n_5$ .

Input

The input holds several data sets. One data set is one line with five numbers separated by blanks. A line containing a single -1 ends the input.

Output

Print one line per data set. Write the five input numbers first, separated by single blanks, then one more blank, then the verdict. Print OK! when an expression equal to $n_5$ exists, and NO! when none does.

Examples1

Example 1

Input

1 2 3 4 50
2 3 10 1 61
-1

Expected output

1 2 3 4 50 NO!
2 3 10 1 61 OK!