Welcome to ZOJ
 Contests Information Problems Runs Statistics Ranklist Clarification
135 - ZOJ Monthly, August 2014 - F
Function

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Let x is a binary number with n digits (AnAn-1An-2...A2A1). And we can encode it as G(x) = x ⊕ ⌊x / 2⌋ or as C(x) = (2n - x) mod 2n, where "⊕" is bitwise XOR operation and "⌊x⌋" indicates the largest integer which is not greater than x.

For some reasons, Alice encodes her password P into G(P), and additionally, she encodes P into C(P). And she writes G(P) and C(P) in a paper. However, something terrible happened. A bug ate some parts of the paper, so some digits are unreadable now. Alice is so worried that she want you to determine the values of these digits using the readable digits.

#### Input

There are multiple test cases. For every test case, it has 2 lines of same number of digits describe G(P) and C(P). In every line, it only contains '1', '0' and '?'. Unreadable digits are denoted with symbol '?'. The length of every line in the input is up to 105.

#### Output

If it is impossible to restore G(P) and C(P), you should output "IMPOSSIBLE" (without quotes).

If G(P) is unique, you should output "UNIQUE" (without quotes) in the first line. Then output restored G(P) and C(P) in the same format.

If there are two or more possible G(P) that can be restored using the readable digits. You should output "AMBIGUOUS" (without quotes) and the number of possible G(P). The number may be very large, so the answer should modulo 109 + 7.

```1110
0101
11??
01??
111?
100?
```

#### Sample Output

```UNIQUE
1110
0101
AMBIGUOUS 3
IMPOSSIBLE
```

#### Hint

In the second sample case, the three possible situations are:
1.G(1001) = 1101, C(1001) = 0111
2.G(1010) = 1111, C(1010) = 0110
3.G(1011) = 1110, C(1011) = 0101
Author: LIN, Xi
Submit    Status