Little boy Oleg loves the cartoon My Little Pony. How it cannot be loved,
because there is friendship, magic and colored horses!
For the past several months Oleg has been begging from his parents a real
pony, but they are just ready to buy him only collectible figures of
cartoon characters. With these figures Oleg recreates the best episodes of
My Little Pony on his desk. Sometimes he realizes that he has already all
the key characters for the next episode, and begins to feel the
desire to immediately buy the missing figures for this episode. For
example, if Oleg has on hand Twilight Sparkle and Spike, his life will not
be sweet without Princess Celestia. It may happen that the new figures
will cause new desires: having three above-mentioned figures, Oleg
will want Nightmare Moon.
For convenience, let’s number all the figures with integers from 1 to n.
Then the Oleg’s desire will be described by two sets of numbers
{a1, ..., ak} and {b1, ..., bt}, which means that if he
already has figures with numbers a1, ..., ak, he also wants figures
with numbers b1, ..., bt.
Oleg’s parents in order to distract him from his desires of real pony are
ready to buy him as many figures as he wants. But they want to buy a set
of figures that will satisfy all the desires of Oleg, in a single
purchase. Of course, parents will not buy the extra figures.
What figures will Oleg have after purchase?
Input
The first line contains integers n and m that are the number of
figures and the number of Oleg’s desires (1 ≤ n ≤ 1000; 0 ≤ m ≤
4000). The following m lines describe the desires. Each desire is given
by two sets, separated by a space. A set is a string of n characters,
each of that is “0” or “1”. The figure with number i is in the set,
only when i-th character of the string is “1”. The last line contains
the set of figures, which Oleg already has, in the same format.
Output
In a single line output a set of figures, which Oleg will have after
purchase. In other words, it is the union of the set of the existing
figures and the set of figures bought by parents. Output format is the
same as in the input.
Sample
input | output |
---|
6 4
111000 101000
110000 111000
010000 100000
000010 000001
010100
| 111100
|
Notes
In the example Oleg has already the figures 2 and 4. First, he wants the
figure 1 (the third desire). If he gets it, he will want the figure 3 (the
second desire). If you just buy him the figures 1 and 3, Oleg will not
want anything more (the right part of the first desire consists of already
existing figures, and the left side of the last desire is not fulfilled).
Thus, after purchase Oleg will have figures with the numbers 1, 2, 3 and
4.
Problem Author: Kirill Borozdin
Problem Source: Ural FU Junior Championship 2016