Задача . C. Идеальная защита

У Алисы есть важное сообщение M, состоящее из нескольких неотрицательных целых чисел, которое она хочет сохранить в тайне от Евы. Алиса знает, что единственный теоретически защищенный способ шифрования — использование одноразового ключа. Алиса сгенерировала случайный ключ K с длиной, равной длине сообщения. Алиса затем вычислила побитовое исключающее ИЛИ каждого соответствующего элемента массива и ключа (, где обозначает операцию побитового исключающего ИЛИ) и сохранила зашифрованное сообщение A. Алиса умная. Будь как Алиса.

Например, пусть Алиса хочет сохранить сообщение M = (0, 15, 9, 18), и она сгенерировала ключ K = (16, 7, 6, 3). Тогда зашифрованное сообщение равно A = (16, 8, 15, 17).

Алиса понимает, что она не может хранить ключ вместе с зашифрованным сообщением. Поэтому Алиса послала ключ K Бобу и удалила свою копию. Алиса умная. Действительно, будь как Алиса.

Боб понимает, что зашифрованное сообщение защищено только до тех пор, пока ключ является секретным. Поэтому Боб случайным образом поменял местами элементы ключа перед тем, как сохранить его. Боб думает, что в таком случае, даже если Ева получит и зашифрованное сообщение, и ключ, она не сможет прочитать исходное сообщение. Боб не умный. Не будь как Боб.

В примере выше Боб мог, например, выбрать перестановку (3, 4, 1, 2), перемешать элементы в соответствии с ней и сохранить ключ P = (6, 3, 16, 7).

Прошел год, и Алиса теперь хочет расшифровать свое сообщение. Только сейчас Боб понял, что это невозможно. Так как он поменял местами элементы ключа случайным образом, сообщение утеряно навсегда. Мы уже сказали, что Боб не очень умный?

Боб хочет получить хотя бы какую-то информацию из сообщения. Так как он не очень умный, он попросил у вас помощи. Вам известны зашифрованное сообщение A и произвольно перемешанный ключ P. Каково лексикографически минимальное сообщение, которое могло быть зашифровано подобным образом?

Формально, по данным A и P найдите лексикографически минимальное сообщение O такое, что существует перестановка π такая, что для всех i.

Напомним, что последовательность S лексикографически меньше последовательности T, если существует такая позиция i, что S_i < T_i, а для всех j < i выполняется S_j = T_j.