Baltic Olympiad in Informatics: 2001 Day 2, Problem 3

Great sorcerer Byter created two islands on the Baltic Sea: Bornholm and Gotland. On each island he has installed some magical teleports. Each teleport supports two modes, but can only work in one of two modes:

• receiving — one can be teleported to it,
• sending — anyone who enters the teleport is transferred to the specific destination teleport on the other island, only if the other teleport is in receiving mode.

Once, Byter gave his apprentices the following task: they must set the teleports' modes in such a way, that no teleport is useless, i.e. for each teleport set in the receiving mode there must be at least one teleport set in the sending mode and sending to it; and vice versa, for each teleport set in the sending mode, the destination teleport must be set in the receiving mode.

Write a program that determines the appropriate modes for teleports such that every teleport is used (either receiving or sending).

Constraints

~1 \le m, n \le 5 \times 10^4~

Input Specification

In the first line of input, there are two space-separated integers ~m~ and ~n~, where ~m~ is the number of teleports on Bornholm, and ~n~ is the number of teleports on Gotland. Teleports on both islands are numbered from ~1~ to ~m~ and ~n~ respectively.

The second line of the input contains ~m~ positive integers, not greater than ~n~, separated by single spaces — the ~i^\text{th}~ of these integers is the number of the teleport on Gotland that is the destination of the teleport ~i~ on Bornholm.

The third line contains analogous data for teleports on Gotland, i.e. ~n~ positive integers, not greater than ~m~, separated by single spaces — the ~i^\text{th}~ of these integers is the number of the teleport on Bornholm that is the destination of the teleport ~i~ on Gotland.

Output Specification

Your program should write two lines describing the modes of the teleports, respectively, on Bornholm and Gotland.

Both lines should contain a string of, respectively, ~m~ or ~n~ ones and/or zeros. If the ~i^\text{th}~ character in the string is ~1~, then the ~i^\text{th}~ teleport is in the sending mode, and if it is ~0~, then the corresponding teleport is in the receiving mode.

If there are several possible solutions, your program should output any one of them.

Sample Input

4 5
3 5 2 5
4 4 4 1 3

Sample Output

0110
10110

Sample Explanation

The diagram above shows the network of teleports with both receiving and sending modes on.

The diagram above shows the network of teleports based on the states in the sample output. As seen above, each teleport is used in some way, and each teleport is in only one mode.