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

Dmitry Gozman Contest 1. Petrozavodsk training camp. Winter 2007

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

I. Ones and Zeroes

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Consider two binary sequences A and B of length n each. Let us call these sequences compatible if A XOR B = A + B where XOR is the element-wise exclusive OR operation.
Given an integer n and a pair of binary sequences p and q, find the pair of compatible binary sequences a and b which comes first after the pair (p, q). Pair (a, b) is said to be lexicographically less that (c, d) if a is lexicographically less than c, or a and c are equal and b is lexicographically less than d. If there is no pair of compatible binary sequences lexicographically greater than (p, q), output the lexicographically first compatible pair.

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

There is a single integer n (1 ≤ n ≤ 100000) on the first line of the input. The sequence p is given on the second line, and the sequence q is on the third one. There are no spaces or other delimiters inside the sequences; however, there could be trailing whitespace on these two lines.

Результат

Output the sequences a and b on the first two lines of the output, correspondingly. Use the same format as the input.

Примеры

исходные данныерезультат
1  
0 
0 
0
1
2   
01 
10 
10
00
Автор задачи: Dmitry Gozman
Источник задачи: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1530. Ones and Zeroes