Farmer John is interested in better interacting with his fellow cows, so he decided he will learn the moo language!

Moo language is actually quite similar to English, but more minimalistic. There are only four types of words: nouns, transitive verbs, intransitive verbs, and conjunctions. Every two consecutive words must be separated by a space. There are also only two types of punctuation: periods and commas. When a period or comma appears after a word, it appears directly after the word, and is then followed by a space if another word appears next.

A sentence needs to follow one of the following formats:

Type 1: noun + intransitive verb.

Type 2: noun + transitive verb + noun(s). Specifically, at least one noun must follow the transitive verb, and there must be a comma in front of every following noun besides the first following noun.

Two sentences may be joined into a compound sentence if a conjunction is placed in between them. The resulting compound sentence cannot be further joined with other sentences or other compound sentences. Every sentence (or compound sentence, if two sentences are joined) must end with a period.

Farmer John has a word bank of N words, C commas, and P periods (1≤P,C≤N≤10³). He may only use a word or punctuation mark as many times as it appears in the word bank. Help him output a sequence of sentences containing the maximum possible number of words.

Each input file contains T (1≤T≤100) independent instances of this problem.

#5632 upload 2 done - how_to_reg -

Moo Language timer 1s memory 32MB

#5632

Moo Language 1s 32MB