Женя давно уже не бедный студент, живёт в большом городе и работает в престижной компании. Теперь в его кошельке не папина кредитка с нулевым балансом, а целая стопка собственных карточек: зарплатная банковская карта, карточка для оплаты обедов, проездной в метро, скидочные карточки кафе и магазинов.

Каждая неделя у Жени проходит по устоявшемуся распорядку: он передвигается одним и тем маршрутом, посещает одни и те же места. Спустя месяцы жизни в большом чужом городе он, наконец, может ни о чем не думать, а без проблем следовать понятному набору действий!

Впрочем, одна проблема у Жени всё-таки есть. Иногда в магазине, в кафе или даже на входе в метро он вынужден долго искать в кошельке нужную карточку. Это отнимает его драгоценное время и сбивает жизнь с привычного ритма.

Карточки в Женином кошельке хранятся одной стопкой. Женя хочет, чтобы каждый раз, когда у него возникает необходимость воспользоваться картой, наверху стопки оказывалась именно та, которая ему нужна. При этом для Жени не проблема после использования карты убрать её в определённое место стопки.

Зная, в каком порядке будут использоваться карты, несложно складывать их так, чтобы сверху всегда оказывалась нужная. Женя мог бы решить эту задачу, но ему не хочется. Так что займитесь-ка этим сами.

В первой строке записано два числа — n и k (1 ≤ n, k ≤ 10⁵) — общее количество карточек у Жени в кошельке и количество раз, которое Женя использует свои карточки в течение недели. Карточки пронумерованы целыми числами от 1 до n.

Во второй строке через пробел записано k чисел a₁, a₂, …, a_k (1 ≤ a_i ≤ n) — номера карточек, перечисленные в порядке их использования.

Выведите k+1 строку.

В первой строке должны находиться записанные через пробел n чисел от 1 до n — порядок, в котором карты требуется расположить изначально, от самой верхней до самой нижней.

В (i + 1)-й строке должно содержаться одно число — сколько карточек будет располагаться над a_i-й сразу после её возвращения в кошелёк.

Если существует несколько возможных решений, выведите любое.