Задано рядок, який містить від 2 до 50 слів, в кожному від 1 до 30 літер з проміжку 'a'..'z'. Вивести всі слова, в яких символи впорядковані за алфавітом.

Input

Один рядок, який містить від 2 до 50 слів, розділених одним пропуском. Рядок містить тільки літери з проміжку 'a'..'z' і пропуски.

Output

Вивести в кожному новому рядку слово, літери в якому розміщені за алфавітом. Слова виводити в тому порядку, в якому вони розміщені в рядку.

Sample Input 1

there is the house where my family lives

Sample Output 1

is
my

Розглянемо алгоритм, який на вході отримує натуральне число ~n~ і, якщо ~n~ парне, алгоритм ділить його на два, а якщо ~n~ непарне, алгоритм множить його на три та додає одиницю.

Алгоритм повторює це, поки ~n~ не стане одиницею.

Наприклад, послідовність для ~n=3~ така:

3→10→5→16→8→4→2→1

Ваше завдання — змоделювати виконання алгоритму для заданого значення ~n~.

Обмеження

• ~1 \le n \le 10^6~

Input

Єдиний рядок вводу містить ціле число nn.

Output

Вивести рядок, який містить усі значення ~n~ під час роботи алгоритму.

Sample Input 1

3

Sample Output 1

3 10 5 16 8 4 2 1

Учень 5 класу Василь захотів займатися в математичному гуртку. Але для того, щоб тебе зарахували на гурток необхідно успішно скласти вступний екзамен з логіки. Одним із завдань екзамену є математична задача із сірниками.

Приклад умови задачі "На столі лежить певна кількість сірників, розкладених так, що вони утворюють математичне рівняння. Переставивши лише один сірник, зроби це рівняння правильним." Сірник можна брати з будь-якого числа та арифметичного знака, крім дорівнює.

Input

Один рядок, який містить математичне рівняння (рівняння містить тільки одноцифрові числа, арифметичний знак + або -, і знак рівності =).

Output

Вивести одним рядком правильний розв'язок математичного рівняння (в розв'язку мають бути присутні тільки одноцифрові числа, арифметичний знак + або -, і знак рівності =). Якщо розв'язків є декілька, то вивести будь-який.

Sample Input 1

6-4=3

Sample Output 1

6-4=2

Notes

Для того, щоб розв'язати дану головоломку, потрібно перемістити один сірник у числі 3, щоб отримати число 2.

У розпоряджені Цезаря є ~n~ колісниць. У кожну колісницю імператор хоче запрягти по дві групи коней, у кожній з яких буде по ~k~ гривастих. Цезар бажає, щоб різниця швидкостей між групами в кожній колісниці була як можна меншою. Швидкість групи визначається найнижчою швидкістю серед коней в цій групі.

Кінниця Цезаря складається із ~2nk~ коней. Перед походом, потрібно вирахувати, якою буде найбільша різниця між швидкостями для всіх колісниць, враховуючи, що це значення потрібно мінімізувати.

Input

В першому рядку знаходяться два числа ~n~ і ~k~ (~2nk \le 10^6~).

В другому рядку мітисться ~2nk~ цілих чисел - швидкостя коней (~1 \le S_i \le 10^9~).

Output

Виведіть одне ціле число - відповідь для Цезаря.

Sample Input 1

2 3
1 2 3 4 5 6 7 8 9 10 11 12

Sample Output 1

1

Sample Input 2

2 2
3 1 3 3 3 3 3 3

Sample Output 2

2

Notes

Пояснення до прикладу 1

Є 2 колісниці, а в кожну групу входить 3 коня. Можна розбити коней наступним чином.

У першу групу першої колісниці ввійдуть коні із швидкостями 1 11 12. (швидкість групи - 1)

У другу групу першої колісниці ввійдуть коні із швидкостями 2 10 9. (швидкість групи - 2) Різниця між групами - (2-1) = 1.

У першу групу другої колісниці ввійдуть коні із швидкостями 3 7 8. (швидкість групи - 3)

У другу групу другої колісниці ввійдуть коні із швидкостями 4 5 6. (швидкість групи - 4) Різниця між групами - (4-3) = 1.

Найбільша різниця серед усіх колісниць - max(1, 1) = 1.

Вчений ~Х~ провів експеримент над явищем ~Y~ і отримав таблицю значень/результатів, яка складається із ~N~ пар дійсних чисел. Він помітив, що це явище можна описати як многочлен (~N-1~) степеня.

Враховуючи наявні дані, ~Х~ хоче дізнатися, який би результат він отримав, якщо провів би експеримент над значенням ~Z~.

Обмеження

• ~ 2 \le N \le 10~
• Значення подаються в порядку зростання у діапазоні [-100, 100].

Input

Перший рядок - ціле число ~N~.

Далі ~N~ рядків із парами дійсних чисел (значення результат) розділених пробілом.

Останній рядок - дійсне число ~Z~.

Output

Одне число, закруглене до 2 знаків після коми.

Sample Input 1

2
-5 8.1
1 4
7.55

Sample Output 1

-0.48

Notes

В даному прикладі експеримент описується за допомогою прямої (многочлен 1-го степеня)