Фермер Джон зацікавлений у кращому спілкуванні зі своїми побратимами-коровами, тому він вирішив, що він вивчить мову мукання!

Мова Moo насправді дуже схожа на англійську, але більш мінімалістична. Там всього чотири типи слів: іменники, перехідні дієслова, неперехідні дієслова та сполучники. Кожні два послідовні слова повинні бути розділені пробілом. Там також всього два види розділових знаків: крапки і коми. Коли крапка або кома ставиться після слова, вона ставиться відразу після слова, а потім з наступним пробілом, якщо поруч з'являється інше слово.

Пропозиція повинна відповідати одному з таких форматів:

• Тип 1: іменник + неперехідне дієслово.
• Тип 2: іменник + перехідне дієслово + іменник(и). Зокрема, хоча б один іменник повинен слідувати за перехідним дієсловом, і перед кожним має стояти кома, наступний іменник, крім першого іменника після перехідного дієслова.

Дві пропозиції можна поєднати в складносурядне, якщо поставити сполучник між ними. Отримане складносурядне речення не може бути далі об'єднане з іншими реченнями чи іншими складними реченнями. Кожне речення (або складне речення, якщо два речення з'єднані) має закінчуватися крапкою.

У фермера Джона є банк слів з \(N\) слів, \(C\) ком і \(P\) крапок. (\( 1 \leq P, C \le N \leq 10^3 \)). Він може використовувати слово або розділовий знак стільки разів, скільки це з'являється у банку слів. Допоможіть йому вивести послідовність речень, що містить максимально можливу кількість слів.

Кожен вхідний потік містить \(T\) (\(1\le T\le 100\)) підтестів.

Формат вхідних даних

Перший рядок містить \(T\), кількість підтестів. Кожен підтест вказує наступне:

Перший рядок складається з трьох цілих чисел: \(N\), \(C\) та \(P\).

Наступні \(N\) рядків будуть складатися з двох підрядків, розділених пропуском. Перший підрядок буде саме слово, яке може використовувати ФД (рядок не менше 1 і не більше 10 малих літер), а другий підрядок буде одним з наступних: noun, transitive-verb, intransitive-verb, conjunction, ( відповідно іменник, перехідне дієслово, неперехідне дієслово або сполучник) що позначають тип цього слова. Можливо, те саме слово зустрічається більше одного разу в банку слів ФД, але воно завжди матиме той самий тип при кожній появі.

Формат вихідних даних

У першому рядку виведіть максимальну кількість слів.

У другому рядку виведіть будь-яку послідовність пропозицій з максимально можливим числом слів. Будь-яку допустиму послідовність буде прийнято.

Грейдер чутливий до пробілів, тому переконайтеся, що не виводяться зайві пробіли, особливо наприкінці кожного рядка.

Приклад вхідних даних

3
1 1 1
bessie noun
10 5 4
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
24 5 4
but conjunction
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
bob noun
impressed transitive-verb
cow noun
impressed transitive-verb
leaped intransitive-verb
elsie noun
bella noun
buttercup noun
pushed transitive-verb
mooed intransitive-verb
envy noun
john noun
nhoj noun

Приклад вихідних даних

0

9
nhoj mooed. farmer taught elsie, bessie and john flew.
23
nhoj mooed. nhoj impressed john, farmer, elsie, bessie and cow impressed bob. bella pushed elsie and buttercup flew. envy mooed but john leaped.

Для першого тестового прикладу єдино допустимою послідовністю є порожня послідовність. Для кожного з наступних двох тестових випадків можна побудувати послідовність речень, використовуючи кожне слово з банку слів, крім одного.

ОЦІНЮВАННЯ:

• Тести 2–6: \(N\le 10\)
• Тести 7–11: \(N\le 100\)
• Тести 12–16: \(N\le 1000\)
• Тести із залишком 2 при розподілі на 5: немає транзитивних дієслів.
• Тести із залишком 3 при розподілі на 5: немає неперехідних дієслів.
• Тести із залишком 4 при розподілі на 5: немає сполучників.