Pis Elektrik Qurğusu
Ninja Ryu Kölgə Klanının qalasına girib uzun bir dəhlizdə özünü tapır. Ninjalər əla döyüşçülərdir, lakin missiyalarını yerinə yetirmək üçün əsasən gizlilikdən istifadə edirlər. Dəhlizdə çoxlu işıqlar yanır və bu vəziyyətdə Ryu tezliklə bir mühafizəçi tərəfindən görüləcək. Görünməz qalmaq üçün Ryu mümkün qədər tez bütün işıqları söndürməlidir.
Dəhlizdə n işıq L_1...L_n ardıcıllığı var. Bu işıqlardan bəziləri yanır. Şurikenlərlə işıqları məhv etmək çox səs-küylü olardı, ona görə də onları köhnə üsulla, işıq açarları ilə söndürməlidir. Xoşbəxtlikdən, hər bir işıq L_i üçün bir işıq açarı S_i olan bir açar qutusu var. Lakin, açarlardan birini sınadıqdan sonra, maraqlı bir şey fərq edir. S_i açarını çevirdikdə, yalnız L_i işığını yandırıb/söndürmür, həm də bəzi qonşu işıqları da təsir edir. Ryu fərq edir ki, elə bir parametr D var ki, S_i açarını çevirmək L_{i-D}...L_{i+D} işıqlarını, əgər mövcuddursa, yandırıb/söndürür (Bu o deməkdir ki, S_1 L_1...L_{D+1} işıqlarını və S_n L_{n-D}...L_n işıqlarını yandırıb/söndürür. Əlbəttə, əgər D ≥ n olarsa, onda L_{D+1} və L_{n-D} də mövcud olmayacaq.). İşıqları yandırıb/söndürmək mühafizəçilərin diqqətini cəlb edə bilər, ona görə də Ryu bütün işıqları minimum sayda açar çevirməklə söndürmək istəyir. Ona kömək edə bilərsinizmi?
Giriş verilənləri
Girişin ilk sətri test hallarının sayını göstərən bir ədəd ehtiva edir. Hər bir test halı aşağıdakı formata malikdir:
Bir sətirdə iki tam ədəd n (1 ≤ n ≤ 100) və D (0 ≤ D ≤ 15): işıqların sayı və yuxarıda qeyd olunan parametr.
Bir sətirdə n tam ədəd. i-ci tam ədəd işıq L_i-nin cari vəziyyətini təsvir edir, burada 0 sönük və 1 yanıq deməkdir.
Çıxış verilənləri
Girişdəki hər bir test halı üçün çıxışda tək sətirdə bir tam ədəd olmalıdır: Ryu-nun bütün işıqları söndürmək üçün açarı çevirməli olduğu minimum say. Əgər bütün işıqları söndürmək mümkün deyilsə, onda "impossible" sözünü çıxış edin.
Nümunə
Aşağıdakı birinci nümunədə, S_4 açarını çevirmək və sonra S_7 açarını çevirmək bütün işıqları söndürəcək.