################### ### utility ### ################### type lint = int64 template exit = quit 0 proc write[T]( x :T ) = stdout.write( $x ) proc alloc( T :typedesc ) :ptr T = cast[ptr T]( T.sizeof.alloc ) proc make[T]( f :proc():T ) :T = f() # template make[T]( body :untyped ) :T = # block: # proc f() :T = # body # f() #################### ### function ### #################### proc less[T1,T2]( x :T1, y :T2 ) :bool = x < y proc more[T1,T2]( x :T1, y :T2 ) :bool = x > y #proc add[T1,T2]( x :T1, y :T2 ) :T1 = x + y proc mul[T1,T2]( x :T1, y :T2 ) :T1 = x * y proc big[T1,T2]( x :T1, y :T2 ) :T1 = max(x, y) proc sml[T1,T2]( x :T1, y :T2 ) :T1 = min(x, y) # proc id[T]( x :T ) :T = x proc `max=`*[T]( x :var T; y :T ) = if x < y: x = y #################### ### iterator ### #################### iterator items( p :(int,int) ) :int = let (L,R) = p for i in L.. L: i.dec yield i iterator reverse( N :int ) :int = for i in reverse(0, N): yield i ################ ### vect ### ################ type vect[T] = seq[T] proc Vect[T]( n :int ): vect[T] = newSeq[T]( result, n ) proc Vect[T]( N :int; X :T ) :vect[T] = result = Vect[T] N for i in N: result[i] = X proc Vect[T]( S :openArray[T] ) :vect[T] = result = Vect[T]( S.len ) for i, e in S: result[i] = e proc elem[T]( e :T, s :varargs[T] ) :bool = for a in s: if e == a: return true return false proc append[T]( V :var vect[T]; X :T ) = V = V & X proc countIf[T]( S :openArray[T], f :proc(x:T):bool ) :int = for e in S: if f(e): result.inc proc each*[T1;T2]( V :vect[T1]; F :proc(x:T1):T2 ) :vect[T2] = let N = V.len result = Vect[T2] N for i in N: result[i] = F V[i] ################ ### tens ### ################ type tens[T] = object data :vect[T] shape :vect[int] proc Tens[T]( S :varargs[int] ) :tens[T] = var N :int = 1 for s in S: N *= s result.data = Vect[T](N) result.shape = @S proc `[]`[T]( t :tens[T], s :varargs[int] ) :T = var n = 0 var r = 1 for i in reverse(s.len): n += s[i] * r r *= t.shape[i] return t.data[n] proc `[]=`[T]( t :var tens[T], s :varargs[int], e :T ) = var n = 0 var r = 1 for i in reverse(s.len): n += s[i] * r r *= t.shape[i] t.data[n] = e proc full[T]( S :var tens[T]; X :T ) = S.data.full X iterator items[T]( t :tens[T] ) :T = items(t.data) #################### ### priority ### #################### type priority[T] = object data :vect[T] compare :proc(x,y:T):bool proc Priority[T]() :priority[T] = result.data = Vect[T](1) result.compare = less proc Priority[T]( compare :proc(x,y:T):bool ) :priority[T] = result.data = Vect[T](1) result.compare = compare proc exist[T]( p :priority[T] ) :bool = p.data.len > 1 proc push[T]( p :var priority[T], e :T ) = var n = p.data.len p.data.add(e) while n div 2 != 0 and p.compare( p.data[n], p.data[n div 2] ): swap( p.data[n], p.data[n div 2] ) n = n div 2 proc front[T]( p :priority[T] ) :T = p.data[1] proc trash[T]( p :var priority[T] ) = let N = p.data.len - 1 p.data[1] = p.data[N] p.data.setLen(N) var n = 1 while true: if n * 2 >= N: break if n * 2 + 1 >= N: if p.compare( p.data[n], p.data[n * 2] ): break swap( p.data[n], p.data[n * 2] ) n = n * 2 continue if not p.compare( p.data[n * 2], p.data[n] ) and not p.compare( p.data[n * 2 + 1], p.data[n] ): break if p.compare( p.data[n * 2], p.data[n * 2 + 1] ): swap( p.data[n], p.data[n * 2] ) n = n * 2 else: swap( p.data[n], p.data[n * 2 + 1] ) n = n * 2 + 1 proc pop[T]( p :var priority[T] ) :T = result = p.front p.trash ################## ### number ### ################## proc `^`[T](n :T, m :int) :T = var n = n var m = m result = 1.T while m > 0: if m mod 2 != 0: result = result * n n = n * n m = m div 2 proc `%`[N,M]( n :N, m :M ) :N = result = n mod m.N if n < 0: result += m.N proc fact[I]( n :I ) :I = var memo {.global.} :seq[I] = @[I(1)] if n.int >= memo.len: let m :int = memo.len memo.setLen(n.int + 1) for i in m..n.int: memo[i] = memo[i-1] * i return memo[n.int] proc triangular[I]( n :I ) :I = var memo {.global.} :seq[I] = @[I(0)] if n.int >= memo.len: let m :int = memo.len memo.setLen(n.int + 1) for i in m..n.int: memo[i] = memo[i-1] + i return memo[n.int] proc sum[T]( V :vect[T]) :T = result = 0 for x in V: result += x iterator divisor( N :int ) :int = var i = 1 while i * i < N: if N mod i == 0: yield i yield N div i i.inc if i * i == N: yield i proc divisor( N :int ) :vect[int] = result = @[] for d in N.divisor: result.add d proc perm[N,K]( n :N, k :K ) :N = fact(n) div fact(n-k) proc comb[N,K]( n :N, k :K ) :N = fact(n) div fact(k.N) div fact(n-k) proc eratos( N :int ) :vect[bool] = result = Vect[bool](N+1) for i in (2,N+1): result[i] = true var i = 2 while i * i <= N: if result[i]: var j = i * 2 while j <= N: result[j] = false j += i i += 1 proc ceilDiv( n: int, m: int ) :int = return (n + m - 1) div m ################ ### list ### ################ const ListNodeSize = 1024 type listNode[T] = object data :array[ListNodeSize,T] prev, next :ptr listNode[T] type list[T] = object head, tail :ptr listNode[T] first, last :int proc List[T]() :list[T] = result.head = listNode[T].alloc result.tail = result.head proc empty[T]( li :list[T] ) :bool = li.head == li.tail and li.first == li.last proc exist[T]( li :list[T] ) :bool = not li.empty() proc len[T]( li :list[T] ) :int = var now = li.head while now != nil: result += ListNodeSize now = now.next result -= ListNodeSize + li.first - li.last proc mostLeft[T]( li :list[T] ) :T = li.head.data[li.first] proc mostRight[T]( li :list[T] ) :T = if li.last == 0: li.tail.prev.data[ListNodeSize-1] else: li.tail.data[li.last-1] proc pushLeft[T]( li :var list[T], e :T ) = if li.first == 0: li.head.prev = alloc( listNode[T] ) li.head.prev.next = li.head li.head = li.head.prev li.first = (li.first - 1) % ListNodeSize li.head.data[li.first] = e proc pushRight[T]( li :var list[T], e :T ) = li.tail.data[li.last] = e li.last = (li.last + 1) % ListNodeSize if li.last == 0: li.tail.next = alloc( listNode[T] ) li.tail.next.prev = li.tail li.tail = li.tail.next proc trashLeft[T]( li :var list[T] ) = li.first = (li.first + 1) mod ListNodeSize if li.first == 0: li.head = li.head.next li.head.prev.dealloc li.head.prev = nil proc trashRight[T]( li :var list[T] ) = if li.last == 0: li.tail = li.tail.prev li.tail.next.dealloc li.tail.next = nil li.last = (li.last - 1) % ListNodeSize proc popLeft[T]( li :var list[T] ) :T = result = li.mostLeft li.trashLeft proc popRight[T]( li :var list[T] ) :T = result = li.mostRight li.trashRight proc `[]`[T]( li :list[T], n :int ) :T = var p = li.head for _ in (n + li.first) div ListNodeSize: p = p.next return p.data[(li.first + n) % ListNodeSize] proc `[]=`[T]( li :var list[T], n :int, e :T ) = var p = li.head for _ in (n + li.first) div ListNodeSize: p = p.next p.data[(li.first + n) % ListNodeSize] = e iterator items[T]( li :list[T] ) :T = var i = li.first var now = li.head while now != li.tail: while i != ListNodeSize: yield now.data[i] i.inc i = 0 now = now.next while i != li.last: yield now.data[i] i.inc proc `$`[T]( li :list[T] ) :string = if li.empty: return "list[]" result = "list[" for e in li: result &= $e result &= ", " result.setLen(result.len - 2) result &= "]" ################# ### stack ### ################# type stack[T] = object data :list[T] proc Stack[T]() :stack[T] = result.data = List[T]() proc exist[T]( s :stack[T] ) :bool = s.data.exist proc empty[T]( s :stack[T] ) :bool = s.data.empty proc push[T]( s :var stack[T], e :T ) = s.data.pushRight(e) proc front[T]( s :stack[T] ) :T = s.data.mostRight proc trash[T]( s :var stack[T] ) = s.data.trashRight proc pop[T]( s :var stack[T] ) :T = s.data.popRight proc Stack[T](e:T):stack[T] = result = Stack[T](); result.push(e) ################# ### queue ### ################# type queue[T] = object data :list[T] proc Queue[T]() :queue[T] = result.data = List[T]() proc exist[T]( q :queue[T] ) :bool = q.data.exist proc empty[T]( q :queue[T] ) :bool = q.data.empty proc push[T]( q :var queue[T], e :T ) = q.data.pushRight(e) proc front[T]( q :queue[T] ) :T = q.data.mostLeft proc trash[T]( q :var queue[T] ) :T = q.data.trashLeft proc pop[T]( q: var queue[T] ) :T = q.data.popLeft proc Queue[T](e:T):queue[T] = result = Queue[T](); result.push(e) ################ ### sort ### ################ proc sort[T]( S :var vect[T], compare :proc(x,y:T):bool ) = var stack = Stack[ (bool,int,int) ]() stack.push( (true, 0, S.len) ) while stack.exist: var (B, L, R) = stack.pop if R - L < 2: continue if B: stack.push( (false, L, R) ) stack.push( (true, L, (L+R) div 2) ) stack.push( (true, (L+R) div 2, R) ) continue var temp = Vect[T]( (L+R) div 2 - L ) for i in temp.len: temp[i] = S[L+i] var (t, r) = (0, (L+R) div 2) for i in (L,R): if r == R or t != temp.len and compare(temp[t], S[r] ): S[i] = temp[t] t.inc else: S[i] = S[r] r.inc proc sort[T]( S :var vect[T] ) = S.sort(less) proc Sort[T]( S :vect[T], comp :proc(x,y:T):bool ) :vect[T] = result = Vect[T](S) sort[T](result,comp) proc Sort[T]( S :vect[T] ) :vect[T] = result = Vect[T](S) result.sort #################### ### min, max ### ################### proc argMax[T]( V :openArray[T] ) :int = var max = T.low for i, e in V: if e > max: result = i max = e proc upperBound[T]( L, R :T, f :proc(n:T):bool ) :T = var (ok, ng) = (L, R) while ng - ok > 1: let mid = (ng + ok) div 2 if f( mid ): ok = mid else: ng = mid return ok proc lowerBound[T]( L, R :T, f :proc(n:T):bool ) :T = upperBound( L, R, proc(n:T) :bool = not f(n) ) + 1 ################ ### read ### ################ proc read( T :typedesc ) :T = proc getchar() :char {.header:"stdio.h",importc:"getchar_unlocked".} when T is char: result = getchar() discard getchar() when T is string: result = "" while true: var c = getchar() if c.elem( ' ', '\10', '\255' ): break result.add c when T is (int or lint): var sign = 1 c = getchar() if c == '-': sign = -1 c = getchar() while '0' <= c and c <= '9': result *= 10 result += c.int() - '0'.int() c = getchar() result *= sign when T is tuple: for r in result.fields: r = r.type.read proc read( T :typedesc, N :int ) :vect[T] = result = Vect[T](N) for i in N: result[i] = T.read #################### ### disjoint ### #################### type disjoint = object data :vect[int] proc Disjoint( n :int ) :disjoint = result.data = Vect[int](n) for i in n: result.data[i] = -1 proc find( d :var disjoint, n :int ) :int = if d.data[n] < 0: return n d.data[n] = d.find( d.data[n] ) return d.data[n] proc union( d :var disjoint, n, m :int ) = var n = d.find(n) var m = d.find(m) if n == m: return if d.data[m] < d.data[n]: swap( n, m ) d.data[m] += d.data[n] d.data[n] = m proc same( d :var disjoint, n, m :int ) :bool = d.find(n) == d.find(m) proc size( d :var disjoint, n :int ) :int = - d.data[d.find(n)] ############### ### bit ### ############### iterator allBit[I]() :I = var i :I = 1.I while i != 0.I: yield i i = i shl 1.I proc bitCount( b :int ) :int = var b :int64 = b b = (b and 0x5555555555555555) + (b shr 1 and 0x5555555555555555) b = (b and 0x3333333333333333) + (b shr 2 and 0x3333333333333333) b = (b and 0x0f0f0f0f0f0f0f0f) + (b shr 4 and 0x0f0f0f0f0f0f0f0f) b = (b and 0x00ff00ff00ff00ff) + (b shr 8 and 0x00ff00ff00ff00ff) b = (b and 0x0000ffff0000ffff) + (b shr 16 and 0x0000ffff0000ffff) b = (b and 0x00000000ffffffff) + (b shr 32 and 0x00000000ffffffff) result = b.int ################### ### segment ### ################### type segment[T] = object size :int data :vect[T] id :T op :proc(x,y:T):T proc Segment[T]( V :vect[T], e :T, F :proc(x,y:T):T ) :segment[T] = result.id = e result.op = F result.size = 1 while result.size < V.len: result.size = result.size shl 1 result.data = Vect[T](result.size * 2) for i in V.len: result.data[result.size + i] = V[i] for i in (V.len,result.size): result.data[result.size+i] = e for i in reverse(1,result.size): result.data[i] = F( result.data[2*i], result.data[2*i+1] ) proc update[T]( S :var segment[T], K :int, X :T ) = var k = K + S.size S.data[k] = X while(k != 0): k = k div 2 S.data[k] = S.op( S.data[k*2], S.data[2*k+1] ) proc query[T]( S :segment[T], L, R :int ) :T = var X = S.id Y = S.id L = L + S.size R = R + S.size while L < R: if (L and 1) != 0: X = S.op( X, S.data[L] ) L.inc if (R and 1) != 0: R.dec Y = S.op( S.data[R], Y ) L = L div 2 R = R div 2 return S.op(X,Y) ##################### ### shakutori ### ##################### proc shakutori( N, M :int, C :proc(x,y:int):bool ) :int = result = 0 var R = N for L in (N,M): while R < M and C(L, R+1): R.inc result += R - L if L == R: R.inc ################ ### mint ### ################ const MOD :int = 1000000007 type mint = distinct int proc Mint[I]( n :I ) :mint = var n = n.int mod MOD if n < 0: n = n + MOD return n.mint proc `$`( m :mint ) :string = $m.int proc `+`[I]( m: mint, n: I ) :mint = (m.int + n.int).Mint proc `-`[I]( m: mint, n: I ) :mint = (m.int - n.int).Mint proc `*`[I]( m: mint, n: I ) :mint = (m.int * n.int).Mint proc `/`[I]( m :mint, n :I ) :mint = var a = n.int b = MOD u = 1 v = 0 while b > 0: var t = a div b a -= t * b u -= t * v swap( a, b ) swap( u, v ) return m * u proc `div`[I]( m :mint, n :I ) :mint = m / n proc `+=`[I]( m :var mint, n :I ) = m = m + n proc `-=`[I]( m :var mint, n :I ) = m = m - n proc `*=`[I]( m :var mint, n :I ) = m = m * n proc `/=`[I]( m :var mint, n :I ) = m = m / n proc `==`[I]( m :mint, n :I ) :bool = m.int == n.Mint.int ####################### ### topological ### ####################### proc topological( G :vect[vect[int]] ) :vect[int] = let N = G.len var h = Vect[int] N for p in G: for c in p: h[c].inc var q = Queue[int]() for i in N: if h[i] == 0: q.push i result = Vect[int] N var now = 0 while q.exist: let n = q.pop result[now] = n now.inc for c in G[n]: h[c].dec if h[c] == 0: q.push c for i in N: if h[i] != 0: raise ########################## #### #### #### main #### #### #### ########################## let (W, H) = (int,int).read var M = Tens[int]( H, W ) for y in H: for x in W: M[y,x] = int.read var v = Tens[bool]( H, W ) for y in H: for x in W: if v[y,x] == true: continue var q = Stack[(int,int,int,int)]() q.push (-1,-1,x,y) while q.exist: let (px, py, X, Y) = q.pop v[Y,X] = true let D = [(0,1),(0,-1),(1,0),(-1,0)] for d in D: let (nx,ny) = (X+d[0], Y+d[1]) if (px, py) == (nx, ny): continue if nx < 0 or ny < 0 or nx >= W or ny >= H: continue if M[y,x] != M[ny,nx]: continue if v[ny,nx] == true: "possible".echo exit q.push (X, Y, nx, ny) "impossible".echo