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
Input Specification
In the first line of input, there are two space-separated integers and , where is the number of teleports on Bornholm, and is the number of teleports on Gotland. Teleports on both islands are numbered from to and respectively.
The second line of the input contains positive integers, not greater than , separated by single spaces — the of these integers is the number of the teleport on Gotland that is the destination of the teleport on Bornholm.
The third line contains analogous data for teleports on Gotland, i.e. positive integers, not greater than , separated by single spaces — the of these integers is the number of the teleport on Bornholm that is the destination of the teleport 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, or ones and/or zeros. If the character in the string is , then the teleport is in the sending mode, and if it is , 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.
Comments