Teleports

Time Limit:	1000ms	Memory Limit:	64000KiB
Accepted:	0	Submitted:	2

Teleports

BOI 2001 Day 2 Problem 3

Teleports

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

receiving--one can be teleported to it,
sending--anyone who enters the teleport is transfered to the specific destination teleport on the other island, provided that the other teleport is in the 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 sending to it, set in the sending mode; and vice versa, for each teleport set in the sending mode, the destination teleport must be set in the receiving mode.

Task

Write a program that:

reads the description of the teleports on both islands, form the input file tel.in,
determines the appropriate modes for teleports,
writes the result to the output file tel.out.

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

Input

In the first line of the text file tel.in, there are two integers m and n, 1<=m,n<=50 000, separated by a single space; 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 file contains m positive integers, not greater than n, separated by single spaces--k-th of these integers is the number of the teleport on Gotland that is the destination of the teleport k 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--k-th of these integers is the number of the teleport on Bornholm that is the destination of the teleport k on Gotland.

Output

Your program should write two lines describing the modes of the teleports, respectively, on Bornholm and Gotland, to the output file tel.out. Both lines should contain a string of, respectively, m or n ones and/or zeros. If the k-th character in the string is 1, then the k-th teleport is in the sending mode, and if it is 0, than the corresponding teleport is in the receiving mode.

Sample Input

4 5
3 5 2 5
4 4 4 1 3

Sample Output

0110
10110

Figures

Submit Statistics