ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Open Ural SU Championship 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Gray Code

Time limit: 0.5 second
Memory limit: 64 MB
Denis, Vanya and Fedya gathered at their first team training. Fedya told them that he knew the algorithm for constructing a Gray code.
  1. Create a 2-bit list: {0, 1}.
  2. Reflect this list and concatenate it with the original list: {0, 1, 1, 0}.
  3. Prefix old entries with 0, and prefix new entries with 1: {00, 01, 11, 10}.
  4. Repeat steps 2 and 3 until the length of all elements is equal to n.
The number n is a length of a Gray code. For example, the code of length 3 is: {000, 001, 011, 010, 110, 111, 101, 100}.
Denis ran the Fedya's algorithm and obtained a binary number x at position k (positions are numbered starting from zero). Vanya wrote down the numbers k and x in binary system. This story happened many years ago and now you hold the paper sheet with these numbers in your hands. Unfortunately, some digits are unreadable now. Could you determine the values of these digits using the readable digits?

Input

The first line contains a number k written in the binary system. Unreadable digits are denoted with symbol “?”. The second line contains a number x in the same format. The lengths of these numbers are equal and don't exceed 105. The numbers may contain leading zeroes.

Output

If there is a unique way to restore the numbers k and x, output them, replacing the symbols “?” with “0” or “1”. If there are multiple ways to restore them, output “Ambiguity”. If Denis or Vanya certainly made a mistake in these numbers, output “Impossible”.

Samples

inputoutput
0?1
0?0
011
010
?00
??0
Ambiguity
100
100
Impossible
Problem Author: Dmitry Poletaev
Problem Source: XV Open USU Championship
To submit the solution for this problem go to the Problem set: 1780. Gray Code