Elementary Math

Time limit10sMemory limit256 MB

Summary

Assign +, -, or * to each of n given pairs so all results differ, choosing the lexicographically smallest valid assignment.

Level: Medium7 of 10
Topics: Graph, Greedy
Solved: No attempts yet

Problem

Ellen teaches elementary math and the final exam is coming up. The exam has $n$ questions. In each question a student adds (+), subtracts (-), or multiplies (*) a pair of integers.

Ellen has already picked the $n$ pairs. What is left is deciding which operation goes with each pair. So the students do not get bored, all $n$ results must be different.

Help Ellen prepare the exam.

Input

The first line contains the number of pairs $n$ ( $1 \le n \le 2500$ ).

Each of the next $n$ lines contains the two integers $a$ and $b$ of one pair, separated by a space ( $-10^6 \le a, b \le 10^6$ ).

Output

If an assignment exists, print $n$ lines in the same order as the input. Line $i$ has the form a op b = c, where op is one of +, -, * and c is the result of that operation. Separate the parts with single spaces. The $n$ results must all be different.

Several assignments can satisfy this, so print exactly one of them. Read the chosen operators in input order as a string and print the assignment whose string is smallest in the order +, -, *. Equivalently, go pair by pair from the first one and use + whenever the remaining pairs can still be given distinct results, otherwise -, otherwise *.

If no assignment makes the $n$ results different, print impossible.

Examples3

Example 1

Input

Expected output

1 + 5 = 6
3 - 3 = 0
4 + 5 = 9
-1 + -6 = -7

Example 2
Input
```
4
-4 2
-4 2
-4 2
-4 2
```
Expected output
```
impossible
```

Example 3

Input

Expected output

2 + 2 = 4
2 - 2 = 0
3 + 3 = 6