ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2108. Олег и маленькие пони

Ограничение времени: 0.9 секунды
Ограничение памяти: 64 МБ
Мальчик Олег очень любит мультсериал My Little Pony. А как можно его не любить, ведь там дружба, магия и цветные кони!
Вот уже который месяц Олег выпрашивает у своих родителей настоящего пони, но пока они готовы покупать ему лишь коллекционные фигурки героев мультсериала. С помощью этих фигурок Олег воссоздаёт лучшие эпизоды My Little Pony у себя на столе. Иногда он понимает, что у него уже есть все ключевые персонажи для очередного эпизода, и начинает испытывать желание срочно приобрести недостающие для этого эпизода фигурки. Например, если у Олега на руках есть Twilight Sparkle (Сумеречная Искорка) и Spike (Спайк), жизнь его будет не мила без Princess Celestia (Принцессы Селестии). Может случиться так, что новые фигурки вызовут новые желания: имея три вышеназванные фигурки, Олег непременно захочет и Nightmare Moon (Лунную пони).
Для удобства пронумеруем все фигурки целыми числами от 1 до n. Тогда желание Олега описывается двумя наборами чисел {a1, ..., ak} и {b1, ..., bt} и означает, что если у него уже есть фигурки с номерами a1, ..., ak, то он хочет также фигурки с номерами b1, ..., bt.
Родители Олега, чтобы отвлечь его от мечтаний о настоящем пони, готовы купить ему столько фигурок, сколько тот захочет. Вот только им хочется приобрести набор фигурок, который удовлетворит все желания Олега, за одну покупку. Естественно, родители не будут покупать лишние фигурки.
Какие фигурки будут у Олега после покупки?

Исходные данные

В первой строке даны целые числа n и m — количество фигурок и количество желаний Олега (1 ≤ n ≤ 1000; 0 ≤ m ≤ 4000). В следующих m строках описаны желания. Каждое желание задаётся двумя наборами, разделёнными пробелом. Набор задаётся строкой из n символов, каждый из которых является «0» или «1». Фигурка с номером i присутствует в наборе тогда и только тогда, когда i-й символ строки — это «1». В последней строке в том же формате задан набор фигурок, которыми уже обладает Олег.

Результат

В единственной строке выведите набор фигурок, который будет у Олега после покупки. Другими словами, это объединение наборов уже имеющихся фигурок и купленных родителями фигурок. Формат вывода набора такой же, как во входных данных.

Пример

исходные данныерезультат
6 4
111000 101000
110000 111000
010000 100000
000010 000001
010100
111100

Замечания

В примере Олег уже имеет фигурки с номерами 2 и 4. Сначала он захочет фигурку номер 1 (желание № 3). Если он получит её, то захочет фигурку номер 3 (желание № 2). Если сразу купить ему фигурки 1 и 3, больше Олег ничего не захочет (в правой части первого желания стоят уже имеющиеся фигурки, а левая часть последнего желания не выполняется). Таким образом, после покупки у Олега будут фигурки с номерами 1, 2, 3 и 4.
Автор задачи: Кирилл Бороздин
Источник задачи: Чемпионат УрФУ среди юниоров 2016