Kombinator Dövrələrinin Optimallaşdırılması

Nathan O. Davis inteqrasiya olunmuş sistemlər şöbəsinin tələbəsidir. Bu gün o, rəqəmsal dövrə dərsində iştirak edir. Mühazirənin mövzusu kombinatorial dövrələrin optimallaşdırılmasıdır. Kombinatorial dövrələr AND və OR qapıları ilə boolean məntiqini həyata keçirən rəqəmsal dövrələrdir. Onlar adətən çoxlu girişlərə və bir çıxışa malikdir.

Mühazirənin sonunda Nathan, hər zamanki kimi, ev tapşırığı aldı. Tapşırıq kombinatorial dövrələri optimallaşdıran bir proqram yazmaqdır.

Orijinal (optimizasiya olunmamış) dövrənin spesifikasiyası həqiqət cədvəli şəklində verilir, məsələn, aşağıdakı kimi:

Bu cədvəl dörd girişli bir dövrəni təmsil edir. Birinci sıra göstərir ki, giriş b '0' və giriş d '1' olduqda, çıxış '1' olmalıdır. Çıxış 'x' "önəmli deyil" deməkdir, yəni müvafiq nümunə üçün çıxışın '0' və ya '1' olması fərq etməz. Ümumilikdə, bu cədvəl (¬b ∧ d) ∨ (a ∧ c ∧ ¬d) şərtini təmin edən girişlər üçün '1', (¬b ∧ c) ∨ (¬a ∧ b) ∨ (a ∧ d) şərtini təmin edən girişlər üçün ya '0', ya da '1', və digər bütün giriş nümunələri üçün '0' çıxışını verən bir dövrəni təmsil edir.

Bu dövrənin optimallaşdırılmış versiyaları necə görünür? Budur bir nümunə:

Bu həqiqət cədvəli ilə nəzərdə tutulan dövrə (c∨d) şərtini təmin edən girişlər üçün '1' və digər bütün nümunələr üçün '0' çıxışını verir. Qeyd etməlisiniz ki, bu dövrə orijinal dövrənin spesifikasiyasına uyğundur.

Görə bilərsiniz ki, dövrənin ölçüsü orijinalından azaldılıb. Əslində, yuxarıdakı dövrə orijinal spesifikasiyaya uyğun olan bütün dövrələr arasında ən optimallaşdırılmışdır. Burada, bir dövrə digərindən daha optimallaşdırılmışdır deyirik ki, o, cədvəldə daha az sayda sıraya malikdir. İki dövrənin eyni sayda sırası olduqda, cədvəldə daha az sayda 0/1 olan dövrə daha optimallaşdırılmış sayılır.

İndi, Nathan'a kömək etmək üçün bu optimallaşdırmanı edən bir proqram yazın!

Giriş verilənləri

Giriş bir neçə test halından ibarətdir.

Hər test halının ilk sətri iki tam ədəd N və M ibarətdir. Tam ədəd N (1 ≤ N ≤ 6) giriş siqnallarının sayıdır və M (1 ≤ M ≤ 2^N) cədvəlin sətirlərinin sayıdır.

Sonra giriş dövrəsini təsvir edən M sətir gəlir. Hər sətir uzunluğu N olan bir S sətirindən və bir C simvolundan ibarətdir. S sətiri giriş nümunəsini təmsil edir. S hər bir simvolu ya '0', ya '1', ya da '-' ola bilər. C simvolu ya '1', ya da 'x' ola bilər, yəni giriş nümunəsi üçün arzu olunan çıxış müvafiq olaraq '1' və ya "önəmli deyil" deməkdir. Girişdə C simvolunun '1' olduğu ən azı bir sətirin olduğunu qəbul edə bilərsiniz.

Girişin sonu "0 0" sətiri ilə göstərilir.

Çıxış verilənləri

Hər test halı üçün ən optimallaşdırılmış dövrəni göstərən cədvəli çıxarın. Çıxış dövrəsini təmsil edən cədvəlin hər bir sətri üçün giriş nümunəsinə uyğun olan bir sətir çıxarmalısınız. Ən optimallaşdırılmış dövrənin qeyri-müəyyən çıxış nümunələri olmadığı üçün çıxış spesifikasiyasını '1' və ya 'x' yazmağa ehtiyac yoxdur.

Bir neçə mümkün həll olduqda, onlardan hər hansı birini çap edə bilərsiniz. Həmçinin, cədvəldəki sətirləri istənilən sırada çap edə bilərsiniz.

Hər çıxış test halının nömrəsini göstərən bir sətirlə başlamalıdır. Fərqli test halları arasındakı çıxışlar bir boş sətirlə ayrılmalıdır.