Задано множину s потужності n, що містить усі елементи з інтервалу [1..n]. Необхідно згенерувати всі його підмножини.

Вхідні дані

Єдине число n (1 ≤ n ≤ 8).

Вихідні дані

У кожному рядку необхідно вивести одну з підмножин заданої множини. Підмножина записується перечисленням своїх елементів за збільшенням. Елементи підмножини повинні бути записані разом, без пропусків (пробілів). Кожна підмножина повинна зустрічатися не більше одного разу. Підмножини також потрібно перераховувати за збільшенням (див. приклад). Пусту підмножину виводити не потрібно.