22. Алиса, Боб и шифрование

Алиса и Боб всё ещё работают в отделе безопасности передачи данных и занимаются любимым делом — исследуют только что придуманный алгоритм шифрования на криптостойкость.

Алгоритм, придуманный Алисой и Бобом, весьма прост. Во время шифрования алгоритм принимает символы шифруемого текста по одному и заменяет этот символ на ровно один другой символ. Кодировка, которой пользуются Алиса и Боб, состоит из $m$ символов, поэтому можно считать, что текст преставляет собой последовательность натуральных чисел, не превосходящих $m$. Во время работы алгоритм шифрования поддерживает перестановку натуральных чисел от $1$ до $m$. В начале работы перестановка тождественна, то есть $p_i = i$ для всех $i$. Когда алгоритму на вход поступает символ $x$, алгоритм заменяет его на номер позиции в перестановке (в 1-индексации), на которой находится символ $x$, а также переносит $x$ в начало перестановки. Например, если в некоторый момент работы алгоритма перестановка символов в нём равна $[4, 2, 1, 3]$, а на вход подаётся символ $1$, то символ $1$ будет заменён на символ $3$, поскольку $1$ стоит в перестановке на третьей позиции, а перестановка примет вид $[1, 4, 2, 3]$. Несложно заметить, что результатом шифрования текста, состоящего из $n$ натуральных чисел, не превосходящих $m$, также является текст, состоящий из $n$ натуральных чисел, не превосходящих $m$.

Для упрощения исследования Алиса и Боб решили реализовать эффективное кодирование и декодирование текстов при помощи своего алгоритма, однако Чак, Крейг и Ева нарушили их планы, поэтому Алиса и Боб просят вас реализовать их алгоритм кодирования.

В первой строке заданы три целых числа $n$, $m$ и $type$ ($1 \leq n, m \leq 300\,000, type \in \{1, 2\}$) — длина текста, количество символов в кодировке и режим работы программы соответственно.

Если $type = 1$, то требуется зашифровать заданный текст.

Если $type = 2$, то требуется расшифровать заданный зашифрованный текст.

В следующей строке задано $n$ целых чисел ($1 \leq a_i \leq m$) — текст для обработки.

Выведите $n$ целых чисел — результат обработки текста. Можно показать, что результат расшифровки текста всегда существует и единственен.

В первом примере требуется зашифровать заданный текст. Проиллюстрировать работу алгоритма удобно при помощи таблицы. Обозначим за $x$ — символ текста, $p$ — перестановку символов кодировки до шифрования $x$, $y$ — зашифрованный символ.

Во втором примере требуется расшифровать текст, зашифрованный в первом пункте, поэтому результат расшифровки совпадёт с исходным текстом.