Смішна мова
У цій задачі вам потрібно створити новий словник, використовуючи гру зі словами. Вам надано початкове слово, і ваше завдання — скласти якомога більше інших слів, використовуючи літери з цього слова. Якщо в початковому слові якась літера повторюється, ви можете використовувати її стільки ж разів у нових словах. Порядок літер у початковому слові не має значення. Наприклад, з даного слова CONTEST можна скласти такі слова, як NOTE, NET, ON, TEST, SET тощо.
Ви повинні додати n нових слів до словника. Ви вже знаєте m слів Wi (1 <=i<=m), з якими будете працювати, і ваше завдання — визначити, які нові n слова додати до словника, щоб максимізувати загальну кількість слів, які можна скласти з цих m слів.
Більш формально, знайдіть такий набір непорожніх слів S, де |S| = n, W_i S для будь-якого i, і ∑_1_{≤}_i_{≤}_m |S_i| є максимальним, де Si S - це набір слів, які можна скласти, використовуючи літери з Wi.
Вхідні дані
Перша строка вхідного файлу містить два цілі числа n (1 <=n<= 100) — кількість нових слів, які ви можете додати до словника, і m (1 <=m<= 1 000) — кількість слів, з якими ви будете працювати. Наступні m рядків містять початкові слова. Кожне слово складається з не більше ніж 100 великих літер від A до Z.
Вихідні дані
Запишіть у вихідний файл n рядків з новим словом у кожному рядку.