ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural FU Junior Championship 2016

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Oleg and Little Ponies

Time limit: 0.9 second
Memory limit: 64 MB
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

inputoutput
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
To submit the solution for this problem go to the Problem set: 2108. Oleg and Little Ponies