include Set.Make(struct type t = (int * int) * int let compare = compare end)
 
let (@) g f x = g (f x) and id x = x and sw f x y = f y x and zip x y = (x, y)
 
let fold9 f = let rec loop i = if i>8 then id else loop (i+1) @ f i in loop 0
 
let fold81 f = fold9 (fold9 @ (@) f @ zip)
 
let mark ((i,j),x as e) : t -> t =
  add e @ fold9 (fun k -> remove ((i/3*3 + k/3, j/3*3 + k mod 3), x) @
    remove ((i,j),k) @ remove ((i,k),x) @ remove ((k,j),x))
 
let search =
  let g p f s = fold (f @ sw mark s) (filter ((=) p @ fst) s) in
  fold81 g
 
let read () =
  let f p = Scanf.scanf "%d " (fun x -> if x>0 then mark (p,x-1) else id) in
  fold81 f (fold81 (fold9 @ ((@) add @ zip)) empty)
 
let print s () =
  let pr ((i,j),x) = Printf.printf "%d%c" (x+1) (if j=8 then '\n' else ' ') in
  iter pr s; print_newline ();;
 
search print (read ()) ()