Гра з кубиками#10557

Гра з кубиками

1 секунда

128 мегабайтів

Легка

Фермер Джон намагається навчити своїх корів читати, надавши їм набір з $n$ дощок для навчання читанню, які зазвичай використовуються з дошкільнятами. На кожній стороні дошки знаходиться слово та відповідне йому зображення. Наприклад, на одній стороні може бути написано слово ' $c a t$ ' і зображено кота, а на іншій стороні — слово ' $d o g$ ' і зображено собаку. Коли всі дошки лежать на землі, видно рівно $n$ слів. Якщо перевернути деякі дошки, можна отримати інший набір із $n$ видимих слів.

Щоб допомогти коровам навчитися писати слова, фермер Джон хоче виготовити набір деревʼяних кубиків, на кожному з яких вигравіювано одну букву алфавіту. Він хоче мати достатньо кубиків кожної букви, щоб незалежно від того, який набір із $n$ слів опиниться видимим на верхніх сторонах дощок, корови могли скласти всі ці слова, використовуючи наявні кубики.

Наприклад, якщо $n = 3$ n = 3 і зверху видно слова ' $b o x$ ', ' $c a t$ ' і ' $c a r$ ', коровам знадобиться щонайменше один кубик із буквою ' $b$ ', один кубик із буквою ' $o$ ', один кубик із буквою ' $x$ ', два кубики з буквою ' $c$ ', два кубики з буквою ' $a$ ', один кубик із буквою ' $t$ ' і один кубик із буквою ' $r$ '.

Допоможіть фермеру Джону визначити мінімальну кількість кубиків для кожної букви алфавіту, яку йому необхідно виготовити, щоб незалежно від того, яка сторона кожної дошки опиниться зверху, корови могли скласти всі $n$ видимих слів.

Вхідні дані

У першому рядку міститься ціле число $n (1 \leq n \leq 100)$ n~(1 \le n \le 100).

У наступних $n$ рядках містяться по два слова, що відповідають словам, написаним на протилежних сторонах однієї дошки. Кожне слово складається не більше ніж з $10$ малих літер англійського алфавіту.

Вихідні дані

Виведіть $26$ рядків. У першому рядку має міститися кількість кубиків із буквою ' $a$ ', необхідна для розвʼязання задачі. У наступному рядку має міститися кількість кубиків із буквою ' $b$ ', і так далі до букви ' $z$ '.

Приклади

У цьому прикладі є $n = 3$ n = 3 дошки, тому існує $2^{3} = 8$ 2^3 = 8 можливих наборів слів, які можуть опинитися зверху:

fox dog car
fox dog bus
fox cat car
fox cat bus
box dog car
box dog bus
box cat car
box cat bus

Нам необхідно мати достатню кількість кубиків кожної букви алфавіту, щоб скласти всі три слова незалежно від того, який із цих восьми варіантів буде обрано.

Приклад 1