Поганий Treap

Treap, також відоме як декартове дерево, є структурою даних, що зберігає набір ключів у вигляді бінарного дерева пошуку.

Кожна вершина цього дерева описується парою $(x,y)$.

Значення $x$ у вершинах — це значення збережених ключів. Вони підкоряються правилу "бінарного дерева пошуку": всі значення $x$ у лівому піддереві менші за значення $x$ у корені, а всі значення $x$ у правому піддереві більші за значення $x$ у корені.

Значення $y$ у вершинах підкоряються правилу "купки": значення $y$ у вершини менше або дорівнює значенню $y$ у її батька.

Значення $y$ для кожного нового вузла зазвичай вибирається випадковим чином відповідно до певного розподілу, що забезпечує хорошу середню часову складність багатьох операцій.

Оскільки ця структура даних поєднує властивості бінарного дерева пошуку та купи, її назва є "портманто" з двох слів: TRee + hEAP = TREAP.

Бенджамін вирішив, що недетермінізм у виборі значення $y$ є недоліком, оскільки це призводить до різного часу виконання запитів. Він вирішив обчислювати $y$ для кожного вузла детерміновано на основі його значення $x$, обравши правило $y=sin(x)$. Бенджамін особливо задоволений тим, що різні цілі числа $x$ завжди даватимуть різні значення $y$.

Барбара розуміє, що хоча недетерміноване декартове дерево може мати гіршу продуктивність при "поганій" випадковій послідовності, детерміноване декартове дерево може мати гіршу продуктивність при "поганому" наборі ключів. Вона хоче пояснити це Бенджаміну, показавши йому $n$ цілих чисел, які, будучи збереженими в його структурі даних, утворять дерево висоти $n$ — "найбільш незбалансовану" можливу ситуацію.

Допоможіть Барбарі знайти $n$ таких ключів. Усі ці ключі повинні вміщуватися в $32$-бітовий знаковий тип.

Вхідні дані

Одне ціле число $n(1\le n\le 50000)$.

Вихідні дані

Виведіть $n$ рядків, кожен з яких містить різні цілочисельні ключі. Усі ключі повинні бути в межах від $-2^{31}$ до $2^{31}-1$ включно. Декартове дерево, побудоване на цих ключах за правилом $y=sin(x)$, повинно мати висоту $n$.

Приклади