Foot Typing

Changyoung and Gangsan play a very fun game called 'typing with your feet'.

To play, the two of them first each think of a word. Then they sit side by side at the same computer: Changyoung on the left and Gangsan on the right.

They put the keyboard on the floor, and Changyoung types his word with his right foot while Gangsan types his word with his left foot. They take turns entering their words, but a turn does not have to be exactly one character (a player may type several characters in a row).

Looking at the word that appears on the screen from their alternating input, Seonyoung wants to figure out who typed each letter.

For example, suppose Changyoung thought of 'weissblume' and Gangsan thought of 'exupery', and by taking turns they produced 'weeisxsbulupmerey' on the screen. Then Seonyoung writes, for each position, a 1 (a letter typed by Changyoung) or a 2 (a letter typed by Gangsan) to indicate who typed that letter.

Each player always types their own word in order and never skips a letter, and thanks to long practice they make no typos. In other words, the word on the screen is exactly the two words interleaved while keeping each word's order.

Given the two words the players thought of and the word entered on the screen, write a program that determines who typed each letter.

The first line contains the word Changyoung thought of, and the second line contains the word Gangsan thought of. Both words consist only of lowercase letters and each has length at most 150.

The third line contains the word entered on the screen. Its length equals the sum of the lengths of the two words.

The input is always such that an answer exists.

On the first line, print a string of 1s and 2s indicating who typed each letter. If the i-th character (from the left) is 1, the i-th letter of the screen word was typed by Changyoung; if it is 2, it was typed by Gangsan. That is, reading only the positions marked 1 in order must give Changyoung's word, and reading only the positions marked 2 must give Gangsan's word.

If several strings satisfy this, print the lexicographically smallest one (that is, the one that prefers placing 1 before 2).