Lights Out
Зимни Състезания по Информатика, 2015
Time Limit: 0.1s, Memory Limit: 64MiB
Стаята в жилището на Ели, в която тя спи, има интересна декорация. Подът е облицован с N реда с по M на брой квадратни, светещи плочки. В момента, в който човек стъпи на някоя от тях, тя, и съседните ѝ по хоризонтала и вертикала плочки (които, естествено, са най-много четири) сменят своето състояние: всяка светва, ако е била изгасена, или изгасва, ако е била светната. Считаме, че човек може да започне от произволна плочка и да скача на произволна друга.

Всяка вечер, когато се прибере у тях, Ели заварва плочките светещи в някаква конфигурация. С това Станчо няма нищо общо: той си стои отстрани и се хили ехидно докато наблюдава реакцията ѝ. А колкото и красив да е светещият под по принцип, когато стане време за спане, той става учудващо дразнещ.

K вечери вие я изпращахте до тях и всеки път тя ви молеше да изгасите текущата конфигурация, за да... еми за да е тъмно. Можете ли да направите това, или да установите, че Станчо е бил по-гаден от обикновено и това не може да бъде направено?
Вход
На първия ред на стандартния вход са зададени целите числа N и M, показващи, съответно, броя редове и колони на пода. Следва ред с едно цяло число K - колко вечери се опитва да разреши проблема момичето. Следват K на брой групи с по N на брой реда, всеки от които съдържа по M цифри. Цифрата 0 значи, че съответната плочка в началото е изключена, докато 1 – че в началото е включена. Групите са разделени с празен ред една от друга.
Изход
За всяка от K-те конфигурации, изведете на стандартния изход "Possible", ако е възможно момичето да изгаси всички плочки, или "Impossible" в противен случай. Ако отговорът е положителен, след това изведете N реда с по M цифри 0 или 1 (като с 1 са отбелязани плочките, които момичето трябва да натисне). Изпечатайте празен ред между отговорите за различните конфигурации.
Ограничения
  • 1 ≤ K ≤ 10
  • Подът няма да има повече от 1000 плочки.
Примерен Вход Примерен Изход
5 7 3 1111001 1001101 0000010 0100100 1111110 1010100 0101001 1111100 0101001 1010100 1011111 1110001 1100000 1000110 1011100 Possible 1000010 0011110 0100010 1101011 0001110 Impossible Possible 0001001 1000000 0011000 0000100 1010000
Можете да ползвате следния симулатор, за да видите как точно се променят светещите плочки при стъпване върху тях.
Мрън!