Фермер Джон заинтересован в лучшем общении со своими собратьями-коровами, поэтому он
решил, что он выучит язык мычания!
Язык 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\) строк будут состоять из двух подстрок, разделённых одиночным пробелом.
Первая подстрока будет само слово, которое может использовать FJ (строка не менее 1 и не более 10 строчных букв
буквы), а вторая подстрока будет одной из следующих: noun,
transitive-verb, intransitive-verb, conjunction, ( соответсвенно существительное,
переходный глагол, непереходный глагол или союз) обозначающие тип этого
слова. Возможно, одно и то же слово встречается более одного раза в банке слов FJ, но
оно всегда будет иметь один и тот же тип при каждом появлении.
ФОРМАТ ВЫВОДА (на терминал / стандартный вывод):
В первой строке выведите максимально возможное количество слов.
Во второй строке выведите любую последовательность предложений с максимально возможным
числом слов. Любая допустимая последовательность будет принята.
Грейдер чувствителен к пробелам, поэтому убедитесь, что не выводятся
лишние пробелы, особенно в конце каждой строки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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.
|