On June 4, 2089, after a long journey of 17 years and 3 months, the manned rocket "Gnaglu-1" finally landed safely. This rocket was developed and launched by NASA. It passed by 23 solar system planets, including Mars, Venus, Titan, Europa, Ceres, and "Zhang Heng Star," and finally discovered extraterrestrial life on the asteroid "Jason Star." Astronauts found a batch of precious living life samples 45.70 meters below the surface rock layer of "Jason Star" and brought them back for testing. Among the living samples brought back, the most fascinating are these alien millipedes. These creatures have slender bodies divided into several segments. When touched, they curl their bodies into a ring shape and only resume activity after a period of time.

What is even more interesting is that researchers found that the legs of these insects do not appear in pairs like those of Earth millipedes—they have an indefinite number of legs under each body segment, but the total number of legs is always odd! Although it is difficult to distinguish the two from their appearance, by counting the number of legs, scientists can determine the planet the millipede belongs to based on parity.

As a secret agent sent by country J to NASA, you hope to participate in this research activity to obtain further intelligence, and the researchers selected by NASA are all the best scientists. Therefore, NASA Administrator Charles Bolden set a difficult problem to test your ability:

There are $N$ millipedes in front of you, numbered $1 \dots N$. Your task is to identify the planet each insect belongs to, but you are not allowed to count their legs yourself. Charles will select several millipedes from these $N$ millipedes each time and put them into the "Insect Feet Counter" (IFC). The "counter" will automatically calculate the sum of the legs of all insects inside. Charles will feed back the result of this sum mod 2 to you, and tell you which insects were put into the machine at the beginning. He performs this statistical operation a total of $M$ times, and you should obtain the identification results as soon as possible.

If after the $K$-th statistical operation, the existing data is sufficient to determine the identity of each insect, you should also feed this $K$ back to Charles. If $K < M$ at this time, it indicates that the subsequent $M-K$ statistical operations are not necessary.

If, based on all $M$ statistical data, it is still impossible to determine the identity of each insect, you must also inform Charles: there are multiple solutions based on the current data.

Input

The first line contains two positive integers $N, M$.

The next $M$ lines provide the statistical results of Charles's $M$ uses of the "Insect Feet Counter" in order. Each line contains a "01" string and a number, separated by a space. The "01" string indicates bit by bit whether each insect was put into the machine: if the $i$-th character is "0", it means the insect numbered $i$ was not put in, and "1" means it was. The following number is the result of the insect leg count mod 2.

Since NASA's experimental machine is precise and error-free, it is guaranteed that the data will not be self-contradictory. That is, the given data is guaranteed to have a solution.

Output

If there is a unique solution for the given data, output $N+1$ lines. The first line outputs a positive integer $K \le M$, indicating that the unique solution can be determined after the $K$-th statistical operation; the next $N$ lines answer the identity of each millipede in order. If it has an odd number of legs, output "?y7M#" (Martian language), and if it has an even number of legs, output "Earth". If the input data has multiple solutions, output "Cannot Determine".

All outputs do not contain quotes, and please pay attention to case sensitivity when outputting.

Examples

Input 1

3 5
011 1
110 1
101 0
111 1
010 1

Output 1

4
Earth
?y7M#
Earth

Input 2

5 7
01100 1
11000 1
10100 0
11100 1
00011 1
00000 0
11111 0

Output 2

Cannot Determine

Subtasks

• For 20% of the data, $N=M \le 20$;
• For 40% of the data, $N=M \le 500$;
• For 70% of the data, $N \le 500, M \le 1,000$;
• For 100% of the data, $N \le 1,000, M \le 2,000$.

Note

For each test case, if your output file is exactly the same as the answer file, you will get full marks for that test case; Otherwise, for test cases with a unique solution, if you correctly answer the identity of all millipedes, you will get 50% of the score; In other cases, the test case will receive zero points.