Qızların Bayramı
Tsinghua Universitetinin 100-cü ildönümünü qeyd etmək üçün, n qız bir parti təşkil etməyi planlaşdırır. Onlar mahnı oxumaq və rəqs etməkdə mütəxəssisdirlər və qruplarda çıxış etməyi sevirlər. Hazırkı dizaynlarında, bir səhnə və bir sıra oturacaqlar olacaq. Qızlar səhnədə mahnı oxumaq və ya rəqs etmək üçün oturacaqlarından qalxıb səhnəyə gedirlər. Çıxışlarını bitirdikdən sonra, öz oturacaqlarına qayıdırlar (oturacaqlarını dəyişmirlər, çünki hər qızın oturacağında çoxlu şəxsi əşyaları var).
Bu prosedurun sərin görünməsini istəyirlər, buna görə hər çıxış üçün aktrisaların oturacaqları ardıcıl olmalıdır. Məsələn, əgər 4 qız varsa və çıxış qız 1, 2 və 4 tərəfindən edilirsə, onlar 1-2-3-4 sırasıyla otura bilməzlər, çünki qız 1, 2 və 4 qalxanda, qız 2 və 4 arasında aktrisa olmayan (qız 3) oturması qəribə görünür.
Dediyim kimi, onlar mahnı oxumaq və rəqs etməkdə çox yaxşıdırlar, buna görə çoxlu kombinasiya fikirləşiblər. İndi bir az narahat olurlar: bütün qızları elə oturtmaq mümkündürmü ki, yuxarıdakı tələb yerinə yetirilsin (yəni hər kombinasiya üçün aktrisaların oturacaqları ardıcıl olsun).
Yaxşı bir proqramçı kimi, qərar verirsiniz (əslində sizin yerinizə qərar verilir, amma...) bir proqram yazmağa ki, oturacaq düzülüşlərinin sayını hesablaya bilsin. Qızlar daim yeni kombinasiya fikirləşdikləri üçün, proqramınız yeni kombinasiyaları oxuyub cavabı uyğunlaşdırmalıdır. Yalnız bir neçə mümkün düzülüş olduqda (yəni ən çox k uyğun həll), proqramınız onların hamısını çap etməlidir.
Giriş verilənləri
Bir neçə test halı var. İlk sətir üç tam ədəd n, m, k (1 ≤ n, m, k ≤ 200) ehtiva edir, burada n qızların sayı, m kombinasiya sayı və k yuxarıda təsvir edilən parametrlərdir. Növbəti m sətirdən hər biri sıfırla bitən tam ədədlər dəstini ehtiva edir. Bu tam ədədlər kombinasiyadakı qızların ID-ləridir (qızlar 1 ilə n arasında nömrələnir). Giriş faylı son-of-file (EOF) ilə bitir. Giriş faylının ölçüsü 1 MB-dan çox deyil.
Çıxış verilənləri
Hər yeni kombinasiya üçün, bu kombinasiyanı nəzərə alaraq oturacaq düzülüşlərinin sayını çıxış edin. Əgər heç bir yol yoxdursa, 0 çap edin və kombinasiyanı nəzərə almayın. Əgər ən çox k yol varsa, onları bir sətirdə, leksik sıralama ilə çap edin.