Зверніть увагу, що у цій задачі вам, можливо, буде корисно використовувати Python 3.10 (PyPy) замість Python 3.13.
Нещодавно на лекції з лінійної алгебри Козак Вус дізнався про існування множин. Проте, посеред лекції Козаку Вусу набридло слухати далі, і він програв решту лекції в Stawl Brars. Тепер він не може виконати домашнє завдання на наступний урок, тому він просить вас йому допомогти. Домашнє завдання Козака Вуса виглядає наступним чином:
Є масив з різних цілих додатних чисел, який потрібно розбити на підмножини. Розбиття на підмножини вважається гарним, якщо кожне число з масиву належить рівно одній підмножині, а також якщо для будь-яких двох чисел з однієї підмножини одне з двох чисел є префіксом іншого. З усіх гарних розбиттів масиву на підмножини треба знайти таке, в якому кількість підмножин мінімальна.
Допоможіть Козаку Вусу зробити домашнє завдання. Якщо відповідей на завдання декілька, дозволяється вивести будь-яку з них.
Масив називається підмножиною масиву , якщо можна отримати шляхом видалення декількох (або нуля) будь-яких елементів з масиву , а також перестановки елементів в ньому. Наприклад, масиви [3, 1, 5], та [1, 2, 3, 4, 5] є підмножинами масиву [1, 2, 3, 4, 5], а [1, 3, 10] або [1, 1, 2, 3] не є підмножинами масиву [1, 2, 3, 4, 5].
Число є префіксом іншого числа , якщо існує таке ціле x \geq 0, що якщо націло розділити на 10^x, то вийде число . Більш формально, існує таке ціле x \geq 0, що \lfloor{\frac{C}{10^x} \rfloor} =b. Наприклад, число є префіксом числа , а числа та не є префіксами числа .
Перший рядок містить одне ціле число (1 \leq n \leq 10^5) — довжина масиву .
Другий рядок містить цілих чисел a_1, a_2, \dots, a_n (1 \leq a_i \leq 10^{18}) — елементи масиву .
Гарантується, що всі числа масиву різні.
У першому рядку вихідних даних виведіть одне ціле додатне число — мінімальна можлива кількість підмножин у гарному розбитті.
Далі виведіть k\cdot2 рядків:
У рядку з номером i\cdot2 виведіть одне ціле число x_i — кількість чисел у -тій підмножині (1 \leq i \leq k).
У рядку з номером i\cdot2+1 виведіть x_i цілих чисел — зміст -тої підмножини. Числа в цій множині можна виводити у будь-якому порядку.
Example 1
Example 2
У першому прикладі оптимальне розбиття виглядає наступним чином:
, , , ,
У зеленій підмножині:
є префіксом , оскільки \lfloor \frac{21}{10^1} \rfloor\ = 2.
У червоній підмножині:
є префіксом , оскільки \lfloor \frac{318}{10^2} \rfloor\ = 3.
є префіксом , оскільки \lfloor \frac{31}{10^1} \rfloor\ = 3.
є префіксом , оскільки \lfloor \frac{318}{10^1} \rfloor\ = 31.
У другому прикладі оптимальне розбиття виглядає наступним чином:
, , , ,
У зеленій підмножині:
є префіксом , оскільки \lfloor \tfrac{1001}{10^1} \rfloor = 100.
У червоній підмножині:
не є префіксом жодного іншого числа в цій підмножині.
У синій підмножині:
є префіксом , оскільки \lfloor \tfrac{130}{10^2} \rfloor = 1.
Ви отримаєте не менше балів, якщо ваш розв'язок буде коректно працювати для n \leq 18.
Ви отримаєте не менше балів, якщо ваш розв'язок буде коректно працювати для n \leq 500.