Moo Language

Farmer John muốn học ngôn ngữ Moo, có bốn loại từ: danh từ, động từ ngoại, động từ nội và liên từ. Ngôn ngữ có quy tắc ngữ pháp chặt chẽ.

Các dạng câu hợp lệ:

• Loại 1: danh từ + động từ nội.
• Loại 2: danh từ + động từ ngoại + danh từ(, danh từ)*, trong đó ít nhất một danh từ theo sau động từ, và dấu phẩy đứng trước mỗi danh từ sau danh từ đầu tiên.

Hai câu đơn có thể nối bằng một liên từ tạo thành câu ghép (không thể nối thêm nữa). Mỗi câu đơn hoặc câu ghép kết thúc bằng dấu chấm.

Cho $N$ từ, $C$ dấu phẩy và $P$ dấu chấm, hãy xuất ra dãy câu sử dụng số lượng từ tối đa.

Dữ liệu vào

• Dòng 1: $T$ (số test case, $1\le T\le 100$)
• Mỗi test case:
  • Dòng 1: $N$, $C$, $P$ ($1\le P,C\le N\le {10}^3$)
  • $N$ dòng tiếp: từ và loại (noun, transitive-verb, intransitive-verb, hoặc conjunction)

Dữ liệu ra

Với mỗi test case:

• Dòng 1: Số lượng từ tối đa sử dụng được
• Dòng 2: Dãy câu hợp lệ đạt số từ tối đa (nếu số từ > 0)

Số từ tối đa là duy nhất, nhưng dãy câu đạt được nó thì không. Nếu có nhiều dãy câu hợp lệ cùng đạt số từ tối đa, in ra dãy bất kỳ.

Ràng buộc

• $N\le 1000$, $P,C\le N$
• Từ có 1-10 ký tự viết thường
• Cùng một từ xuất hiện nhất quán cùng loại

Ví dụ