Задача . C. Название компании

Клиент банка Олег и аналитик Игорь — хорошие друзья. Однако, иногда они спорят по мелочам. Недавно они основали новую компанию, но испытывают трудности с выбором названия для компании.

Чтобы разрешить спор, они решили сыграть в игру. Название компании будет состоять из n букв. У Олега и Игоря есть по одному набору из n букв (наборы могут содержать одну и ту же букву несколько раз, наборы могут отличаться). Изначально название компании состоит из n знаков вопроса. Олег и Игорь ходят по очереди, Олег ходит первым. На каждом ходу игрок выбирает одну букву c, имеющуюся у него в наборе, и заменяет один любой знак вопроса на эту букву c. Затем одна такая буква c исчезает из его набора. Игра оканчивается, когда все знаки вопроса заменены на какие-то буквы.

Например, предположим, у Олега есть набор букв {i, o, i}, а у Игоря есть набор букв {i, m, o}. Одна из возможных игр приведена ниже:

Изначально название компании равно ???.

Олег заменяет второй знак вопроса на «i». Название компании теперь ?i?. Набор букв Олега теперь равен {i, o}.

Игорь заменяет третий знак вопроса на «o». Название компании теперь ?io. Набор букв Игоря теперь равен {i, m}.

Наконец, Олег заменяет первый знак вопроса на «o». Название компании теперь oio. Набор букв Олега равен {i}.

В итоге название компании равно oio.

Олег хочет, чтобы название компании было лексикографически как можно меньше, а Игорь хочет, чтобы название компании было лексикографически как можно больше. Каким будет название компании, если Олег и Игорь играют оптимально?

Строка s = s₁s₂...s_m лексикографически меньше строки t = t₁t₂...t_m (если s ≠ t), если s_i < t_i, где i — наименьший индекс такой, что s_i ≠ t_i (т.е. s_j = t_j для всех j < i).