#!/usr/bin/ruby def popcnt(n) r=0 while n>0 r+=n%2 n/=2 end r end def lightsout(x,y) a=(x*y).times.map{[0,0]} #create problem x.times{|i| y.times{|j| a[i+j*x][0]=1<<(i+j*x) a[i+j*x][1]= 0 + (1<<(i+j*x)) | (i>0 ? 1<<(i-1+j*x) : 0) | (i0 ? 1<<(i+(j-1)*x) : 0) | (j0 && j>0 ? 1<<(i-1+(j-1)*x) : 0) | (i0 ? 1<<(i+1+(j-1)*x) : 0) | (i>0 && j>i)&1)>0 t<0} return -1 end tlst=[0]*(1<<(x*y-k)) (1<<(x*y-k)).times{|l| r=0 (x*y-k).times{|j| if (l&(1<0 r^=t[j] end } tlst[l]=r } r0=1<<29 c0=0 a_ok.each{|j| if (input&(1<0 c0^=j[1] end } #0解の重ね合わせをすべて試す (1<<(x*y-k)).times{|l| r1=c0 r1^=tlst[l] r0=[r0,popcnt(r1)].min } r0 end while gets m,n=$_.split.map(&:to_i) r=lightsout(n,m) puts r<0 ? :Impossible : r end