Старый Бильбо собирает песни и сказания всех народов Средиземья. С этой целью он хочет на год уехать из Ривенделля, обойти за это время N городов Средиземья, пронумерованных числами от 1 до N (Ривенделль имеет номер 1), и в конце путешествия вернуться назад. На входе в каждый город стоит стражник. Стражник спрашивает у путников, из какого города они пришли, и, в зависимости от этого, требует некоторую плату за вход в город. От мудрого короля эльфов Эльронда Бильбо узнал, что за вход в город с номером P у тех, кто пришёл из города с номером Q, стражник требует ровно PQ золотых. До начала путешествия хотелось бы найти такой порядок посещения городов, при котором потраченная сумма будет минимальна, а также такой, при котором она будет максимальна.

Целое число N (2 ≤ N ≤ 50000).

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