module Main where

import Data.Array
import System.Environment

import Util.Grid
import Util

import Util.Search

{-# NOTINLINE grid #-}
grid :: Array Position Int
grid = listArray ((0,0),(75,95)) [10,10,1,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,1,1,1,10,1,1,10,10,10,1,10,10,10,10,1,1,1,1,10,1,1,10,1,1,1,10,10,10,10,10,10,1,1,1,10,1,1,1,10,10,10,1,10,1,10,10,10,1,1,1,1,1,10,10,10,1,1,1,1,1,1,1,10,1,10,1,1,1,10,10,1,1,1,1,1,1,1,1,1,1,10,10,10,1,1,1,1,1,10,1,10,1,10,1,10,10,1,1,10,10,10,1,10,10,1,1,1,1,1,10,10,10,10,1,10,10,10,1,1,1,1,1,10,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,10,10,10,1,10,1,1,1,1,1,10,1,10,1,1,1,1,1,1,1,10,1,10,1,1,1,10,10,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,10,10,10,10,1,10,1,10,1,10,10,1,1,10,10,1,1,10,10,10,10,1,1,1,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,1,1,10,10,10,10,1,1,1,1,1,1,1,1,10,10,10,1,1,1,1,1,10,1,1,1,10,1,1,1,1,1,1,1,10,1,1,1,1,1,10,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,1,1,1,10,10,1,1,1,1,1,10,10,10,1,10,1,1,1,10,10,10,10,1,1,1,1,1,1,1,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,10,1,1,1,1,1,1,1,1,1,10,10,10,1,1,1,1,1,10,1,1,1,1,1,1,1,1,1,1,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,1,1,1,1,10,10,10,1,1,1,1,10,10,10,1,1,1,10,10,10,10,10,10,1,1,1,1,1,1,1,1,10,10,10,10,1,1,1,1,1,1,1,10,1,10,10,10,10,1,10,10,1,1,10,10,10,10,10,10,1,1,1,1,10,10,1,1,1,1,1,1,1,1,1,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,1,1,1,10,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,10,1,1,1,10,10,10,1,10,10,10,10,1,10,1,1,1,10,10,10,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,1,1,10,1,1,1,1,1,1,10,10,1,1,1,1,10,10,1,1,1,1,1,1,1,10,10,1,10,10,1,10,10,1,1,1,1,1,1,10,10,10,10,10,1,1,1,10,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,10,10,10,10,10,10,10,1,1,1,10,10,10,10,10,10,1,1,1,1,1,1,10,10,1,1,1,10,1,1,1,1,10,10,10,1,1,1,1,1,1,1,1,10,10,1,1,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,10,10,10,10,1,1,1,1,1,1,10,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,1,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,10,1,10,1,1,10,10,1,1,1,1,10,10,10,10,10,10,1,10,1,10,10,10,10,1,1,1,1,1,1,10,10,10,1,10,10,10,10,10,1,1,1,1,1,10,10,10,10,10,10,10,1,10,1,10,1,1,10,10,10,1,1,1,1,10,10,10,1,10,10,10,10,10,10,1,1,1,1,1,1,1,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,10,10,1,1,1,10,10,10,10,1,10,10,1,1,1,10,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,10,10,10,1,1,10,10,10,1,10,10,10,10,10,10,1,10,1,10,10,10,10,10,10,10,10,10,1,10,10,10,1,1,1,1,10,10,1,1,1,1,1,1,1,1,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,10,10,1,10,10,10,10,1,1,1,1,1,1,1,10,1,10,10,10,10,1,1,1,10,1,10,10,1,1,1,10,10,10,10,1,10,10,10,10,10,10,10,1,1,10,1,1,1,10,10,10,10,10,10,1,10,10,10,10,10,10,10,10,10,1,10,10,10,1,1,1,1,1,1,1,10,1,10,1,1,1,1,1,1,1,1,1,1,1,1,1,10,1,1,10,10,10,10,10,10,10,10,10,1,10,1,1,1,1,10,10,10,10,10,10,10,1,1,1,10,10,1,1,1,1,1,10,10,10,10,1,10,10,10,10,10,10,10,1,1,10,1,10,1,10,10,10,10,10,10,10,10,10,1,1,1,10,10,10,1,1,1,10,1,1,1,1,1,1,1,1,1,10,10,1,1,1,1,1,1,1,1,1,10,10,10,1,10,1,1,1,1,10,10,10,1,10,10,10,10,10,1,1,10,10,10,10,1,10,1,10,1,1,1,10,10,10,10,10,1,1,1,10,10,10,10,10,10,10,1,1,10,10,1,1,1,1,1,10,10,1,1,1,10,10,10,10,10,1,1,1,1,1,10,10,1,1,1,10,10,10,1,1,10,10,1,1,1,10,10,10,10,1,1,1,1,1,10,10,10,1,1,1,10,1,1,1,1,10,10,1,10,10,10,1,10,10,10,10,10,10,1,1,1,10,1,1,1,1,1,10,10,10,10,10,1,10,10,10,10,10,10,1,10,10,1,1,1,10,1,10,10,10,1,10,1,1,1,1,1,10,10,10,10,1,1,1,1,1,1,1,1,1,1,10,10,10,10,1,10,10,10,1,1,10,10,10,1,1,1,1,10,10,10,10,1,1,10,10,10,10,1,1,1,1,10,10,10,10,1,1,1,1,1,1,10,10,1,1,10,1,1,1,1,1,10,10,10,10,10,10,1,10,10,10,10,10,10,10,10,10,1,1,1,1,10,10,10,1,1,1,1,1,1,1,1,10,1,10,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,1,10,10,10,10,1,10,10,10,10,10,10,1,10,10,10,10,1,1,1,1,1,1,1,1,1,1,10,10,10,10,1,1,1,1,1,1,1,10,10,1,1,1,1,1,1,1,1,10,10,10,10,10,10,10,1,1,10,10,10,10,10,10,1,1,1,1,10,10,10,1,10,10,1,1,1,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,1,10,10,10,1,1,1,1,1,1,10,10,1,1,10,10,10,10,1,1,1,1,10,10,10,10,1,10,10,10,10,1,1,1,1,1,10,10,10,10,10,1,1,1,1,1,1,1,10,1,10,10,10,1,1,1,1,10,10,10,10,10,1,1,1,10,10,10,1,1,1,10,10,10,1,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,1,1,1,1,1,1,1,1,10,1,1,1,1,1,1,10,10,10,10,1,1,10,10,10,1,1,1,10,1,10,1,10,10,1,1,1,10,1,10,10,10,1,1,1,1,1,1,1,1,1,10,10,10,1,1,10,1,10,10,10,10,10,10,10,10,10,10,1,1,1,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,1,10,10,10,1,1,10,10,10,1,1,1,10,1,10,1,10,10,10,1,10,10,10,1,10,10,1,1,1,1,1,1,1,10,1,1,1,1,1,1,10,10,10,10,10,10,1,1,1,10,10,10,1,1,1,10,10,10,1,1,1,1,1,10,10,10,1,1,1,1,1,1,10,10,10,1,1,10,10,10,10,1,1,1,10,1,1,1,1,1,1,1,1,10,10,10,10,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,1,10,10,10,10,10,1,1,1,10,1,1,1,1,1,1,1,10,1,1,1,1,1,10,10,10,10,10,1,10,10,10,1,1,1,1,1,1,1,10,10,1,1,1,1,10,10,10,10,10,10,10,1,1,1,1,10,1,1,1,1,10,10,10,10,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,10,10,1,10,10,1,10,10,10,10,10,1,1,1,1,1,1,10,10,10,10,10,1,1,1,1,1,1,1,1,1,10,10,10,1,1,1,1,1,1,1,10,10,10,1,10,1,10,1,1,1,10,1,1,10,10,10,10,1,1,1,1,1,10,1,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,10,1,1,1,10,1,1,1,1,10,10,10,1,1,1,1,1,1,1,1,1,1,10,10,10,1,10,1,1,1,1,1,1,1,10,10,10,10,10,10,10,1,1,1,1,10,10,1,10,10,10,1,1,1,1,10,10,10,10,10,1,1,1,1,10,1,1,1,1,10,10,10,10,10,10,1,1,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,1,1,1,1,10,1,1,1,1,10,10,1,1,1,1,1,1,1,1,10,1,1,1,1,10,1,10,10,10,1,1,1,1,1,10,10,1,1,1,10,10,10,1,1,1,10,10,1,10,10,1,1,1,10,1,10,10,10,10,10,1,1,1,1,1,1,1,1,10,1,1,10,10,10,10,10,10,10,10,1,1,1,1,10,1,1,1,1,1,1,1,1,1,1,1,10,1,1,1,10,10,10,1,1,10,10,10,1,1,1,10,10,1,1,1,1,1,10,10,10,10,10,1,1,1,10,1,1,1,1,1,10,1,10,10,10,10,10,10,1,1,10,10,1,10,1,1,1,1,1,1,10,10,10,10,1,1,1,10,1,10,1,1,1,1,1,1,1,1,10,10,10,10,10,10,1,1,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,10,1,1,10,10,10,1,1,1,10,10,1,1,1,10,10,1,10,10,10,1,1,1,1,10,10,10,1,1,10,10,10,10,10,10,10,10,10,1,1,10,10,1,1,1,1,10,1,10,10,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,10,1,10,10,10,10,10,10,1,1,1,1,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,1,10,10,10,10,1,10,10,10,10,10,1,1,1,1,1,1,1,10,10,10,10,10,10,10,10,1,1,1,10,10,1,1,1,1,10,10,10,10,10,10,10,10,1,1,1,1,1,1,1,1,10,1,1,10,10,10,10,10,10,10,1,1,1,1,1,1,1,1,1,10,10,1,1,1,1,1,1,1,1,1,10,10,10,1,1,10,1,1,1,1,10,10,10,1,1,1,1,10,1,1,1,1,1,1,1,10,1,1,1,1,1,10,1,10,10,10,1,1,1,1,10,1,1,1,10,10,10,1,1,1,10,1,1,1,1,10,10,10,10,1,1,1,1,1,1,1,10,10,10,10,10,10,1,10,10,10,1,1,1,1,1,1,1,1,1,10,10,1,1,1,1,1,1,1,1,10,10,10,1,1,10,10,10,1,1,1,1,1,10,10,1,10,10,10,10,1,1,1,1,10,10,10,1,1,1,1,1,10,10,10,10,10,10,1,1,1,10,1,1,1,10,10,10,1,1,1,10,1,10,10,10,10,10,1,10,1,1,1,1,10,1,10,10,10,10,10,10,10,1,10,10,10,1,1,1,1,10,10,1,1,1,10,10,10,1,10,1,1,1,1,1,10,10,10,1,1,1,10,1,1,1,10,10,10,10,10,1,10,1,10,1,1,1,10,10,10,1,1,1,10,10,10,10,10,10,1,1,10,10,1,1,1,10,1,1,1,10,10,10,1,10,10,10,1,1,1,10,1,1,1,10,10,1,1,1,10,1,10,10,10,10,10,10,10,10,10,10,10,1,1,1,1,10,10,10,10,10,1,10,1,1,10,1,1,1,1,1,1,10,10,1,1,10,10,1,1,1,1,1,1,10,10,10,10,10,10,10,10,10,10,10,1,1,1,1,10,10,10,10,10,10,10,10,10,10,1,1,1,1,1,10,10,10,10,1,1,10,10,10,1,1,10,10,10,10,1,10,10,1,1,1,1,1,10,10,1,1,10,10,1,10,1,10,10,10,1,1,10,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,10,10,1,1,10,10,1,1,1,1,10,10,10,10,10,1,1,10,10,10,10,10,1,1,1,1,1,10,10,1,1,1,1,1,10,10,10,1,1,1,1,1,10,1,10,10,1,10,10,10,1,1,1,1,10,10,10,10,10,10,10,1,1,1,10,1,10,1,10,10,10,1,1,1,10,10,10,1,1,1,1,1,1,1,1,1,1,10,10,1,1,1,10,1,10,1,1,1,1,1,10,10,1,1,1,1,10,10,10,1,1,1,10,10,10,10,10,1,1,1,1,1,10,10,10,1,1,1,1,1,10,10,10,10,1,1,10,10,10,1,10,10,1,1,1,1,1,1,1,10,10,10,10,10,10,10,10,1,1,1,1,1,1,1,1,10,10,1,1,1,10,1,10,1,1,1,10,1,10,1,1,1,10,10,10,10,10,1,10,1,1,1,1,1,1,10,10,10,10,1,10,10,10,10,1,1,1,1,10,10,10,10,10,1,1,1,1,10,10,10,10,1,1,1,1,10,1,1,1,1,1,1,10,10,10,1,10,10,1,10,1,1,1,1,1,10,10,10,10,10,10,10,10,1,1,1,1,1,1,1,10,10,10,10,10,10,10,10,1,1,1,1,1,10,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,10,10,10,10,10,10,10,1,10,10,10,1,1,1,1,1,1,10,10,10,1,1,1,1,10,10,10,1,1,1,1,10,10,10,10,10,10,1,1,10,10,10,1,10,10,1,10,10,10,10,1,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,1,10,1,1,10,10,10,10,1,1,1,1,1,10,10,10,10,10,10,10,10,10,10,10,1,1,1,1,10,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,1,1,1,1,10,10,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,1,10,10,10,10,10,10,10,1,1,10,10,1,1,1,1,1,10,10,1,1,10,10,1,1,10,10,10,10,1,1,1,10,10,1,1,10,10,10,10,10,10,10,10,10,1,1,1,10,10,10,10,10,1,1,1,10,1,1,1,10,10,10,10,10,10,10,1,1,10,10,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,10,10,10,10,10,1,1,10,10,10,1,1,10,1,1,1,1,1,1,1,10,10,1,10,10,10,10,10,10,1,1,10,1,1,1,1,10,10,10,1,1,1,10,10,10,1,1,10,10,10,10,10,10,1,1,10,10,1,10,10,10,1,1,1,1,1,1,1,1,1,10,10,10,10,10,10,10,10,10,10,10,1,1,10,10,1,1,1,1,10,10,10,10,1,1,1,1,1,10,10,1,1,1,1,10,10,10,1,1,1,1,1,1,1,1,1,10,10,1,1,10,10,10,10,10,10,10,1,1,1,1,10,1,10,10,1,1,1,10,10,1,1,1,1,1,10,1,1,1,1,1,1,1,1,1,1,1,1,10,1,1,1,1,1,1,1,10,10,10,10,10,10,1,1,1,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,1,1,1,1,10,10,1,1,1,1,10,10,10,1,1,1,10,10,1,1,1,1,10,10,1,10,10,10,10,10,10,10,10,1,1,10,10,10,1,1,10,10,1,1,10,10,10,1,1,10,10,10,10,10,10,1,1,10,10,1,1,1,1,1,1,1,1,1,1,1,10,10,10,1,10,1,10,1,1,1,1,10,10,10,10,10,10,10,10,1,1,10,10,10,10,10,10,10,10,1,1,10,10,1,1,1,10,10,10,10,1,1,10,10,10,1,1,1,10,10,1,10,10,10,10,1,10,1,10,1,1,1,10,10,1,10,10,10,10,1,10,10,10,10,1,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,1,1,1,1,10,10,10,1,10,1,10,1,1,1,1,1,1,1,10,10,10,10,10,10,10,10,1,1,1,1,1,10,1,10,1,1,1,10,10,10,10,10,10,10,10,10,1,1,10,10,10,1,1,1,10,10,10,10,10,10,1,1,1,1,10,1,1,1,10,10,1,1,10,10,10,1,1,10,10,10,10,10,10,10,1,1,10,10,10,10,10,1,1,1,1,10,1,1,1,1,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,10,10,10,1,1,1,10,10,1,10,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,10,1,1,1,10,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,1,1,1,10,10,10,10,1,1,1,1,10,10,10,1,10,10,1,1,1,10,1,1,1,1,1,10,10,10,1,1,1,1,10,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,1,1,1,1,10,10,10,1,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,10,10,1,1,1,10,1,1,10,10,1,1,1,1,1,1,1,1,1,1,10,1,10,10,1,1,1,1,10,1,1,1,10,10,10,10,10,10,1,1,1,1,1,1,10,1,1,1,1,1,1,10,10,1,1,1,1,1,1,1,10,10,10,10,10,10,1,1,10,10,10,10,1,1,1,1,10,10,10,10,10,10,10,10,10,10,10,10,10,10,1,1,1,1,1,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,10,10,1,1,1,1,10,10,10,1,1,1,10,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,1,1,1,10,10,1,1,1,1,1,10,10,10,10,1,10,10,10,10,1,1,1,10,10,1,1,1,1,1,10,10,1,10,1,10,10,10,10,10,1,1,1,1,1,1,10,10,1,1,1,10,1,1,10,10,10,10,1,10,1,1,10,10,10,10,10,1,1,1,1,1,1,1,1,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,1,1,10,10,1,1,1,1,10,1,1,1,1,10,10,10,1,1,1,1,10,10,10,1,1,10,10,1,1,1,1,1,10,1,1,1,1,10,10,10,10,10,1,10,10,10,10,10,10,10,1,1,1,1,1,1,1,1,1,10,10,1,1,1,10,10,10,10,10,1,1,1,1,1,1,1,1,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,1,1,1,10,10,10,1,1,1,10,10,1,1,10,10,10,10,10,1,1,1,10,10,1,1,10,10,10,1,10,1,1,1,1,1,10,1,1,1,1,10,10,10,1,1,10,10,10,10,10,10,10,10,1,10,1,1,1,1,1,1,1,1,1,1,10,10,1,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,1,10,1,10,1,1,1,10,1,1,1,10,10,10,1,1,1,10,10,10,10,1,10,1,10,1,1,1,1,10,10,10,10,10,10,10,1,1,1,1,1,1,1,10,10,10,1,1,1,1,1,1,1,10,10,10,10,10,10,1,10,1,10,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,10,1,1,1,10,1,1,1,1,1,10,10,10,10,10,10,10,10,10,10,10,10,1,1,10,1,10,1,10,10,10,1,1,1,1,1,10,10,10,10,10,10,10,1,1,1,1,10,10,10,1,10,10,10,1,1,1,1,1,10,1,10,10,10,10,1,1,1,1,1,1,1,10,10,10,1,10,1,10,1,1,1,1,10,10,1,1,1,1,10,10,10,10,10,10,10,10,10,1,10,1,1,1,1,1,1,10,10,10,10,1,1,10,10,10,10,10,1,1,1,1,1,10,10,10,10,10,1,1,1,1,1,1,10,10,1,1,1,10,1,1,1,1,10,1,10,10,10,10,10,10,1,10,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,1,10,1,1,1,1,10,10,1,1,1,10,10,1,1,1,10,10,10,10,10,10,10,10,1,1,10,10,1,1,1,1,1,10,10,10,10,10,10,1,1,1,10,10,10,10,10,1,10,1,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,10,1,1,1,1,1,1,1,1,1,10,10,10,1,10,10,10,10,10,10,1,10,10,1,1,1,1,10,1,1,1,10,10,1,1,10,10,10,1,1,1,1,10,1,1,1,1,1,10,10,10,1,10,10,10,1,10,10,10,10,1,10,1,10,10,10,10,10,1,1,10,1,10,1,10,10,10,1,10,1,1,1,1,1,10,10,1,10,10,10,1,1,10,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,1,1,10,10,10,10,10,1,1,1,1,1,1,1,10,1,10,1,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,1,1,1,1,10,10,10,10,10,10,10,10,10,10,10,10,10,10,1,1,1,10,10,10,1,10,10,1,1,1,1,10,10,1,1,1,1,1,1,10,10,10,1,1,1,1,1,10,1,10,1,1,1,10,10,10,1,1,10,10,10,1,10,1,1,1,1,1,1,10,10,1,1,1,1,10,10,1,10,1,1,1,1,1,1,1,10,1,10,1,1,1,1,1,1,1,10,1,1,1,10,10,10,10,1,1,1,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,1,1,1,1,1,1,1,10,10,10,10,1,1,1,1,1,10,10,10,10,1,1,10,10,10,10,10,10,1,1,1,10,1,1,1,1,1,1,1,10,10,10,10,10,10,1,1,1,1,1,1,1,1,1,10,10,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,10,1,10,10,10,10,10,1,1,10,1,1,1,1,1,1,1,1,1,1,10,1,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,10,10,1,10,10,10,1,1,1,1,10,10,10,1,1,1,1,1,1,1,1,1,10,1,10,1,1,10,10,10,10,10,10,10,1,1,1,1,1,1,1,10,10,10,10,10,10,10,10,10,1,1,1,10,10,10,1,1,1,10,1,1,1,1,1,1,1,1,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,1,1,10,10,1,10,1,10,1,10,10,10,10,10,10,1,1,1,1,1,10,10,10,1,1,1,1,10,1,10,10,10,10,10,10,10,1,1,1,1,1,1,1,10,10,10,1,1,10,10,10,10,1,1,1,1,10,10,10,10,10,10,10,10,10,10,1,1,1,1,1,10,1,1,1,1,1,10,1,1,1,10,1,1,1,1,1,1,1,1,1,10,10,10,1,10,1,1,1,10,10,10,1,1,1,1,10,10,10,10,10,1,1,1,1,1,10,1,1,1,1,1,1,10,10,10,10,10,10,10,10,10,10,10,1,10,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,10,1,10,10,10,10,10,10,1,1,1,1,1,1,1,10,1,1,1,10,10,10,1,10,10,10,1,10,10,1,1,1,10,10,10,10,10,1,1,1,1,1,1,1,10,10,10,1,1,10,10,10,10,10,1,1,1,1,10,10,10,1,1,1,1,1,1,1,10,10,1,10,10,10,10,10,10,10,1,10,10,1,1,10,10,1,1,1,1,1,10,10,10,10,10,10,10,1,1,10,10,10,10,10,1,1,1,1,10,1,1,10,1,1,1,10,1,1,1,10,10,10,1,10,10,10,1,1,10,10,10,10,10,10,1,1,1,1,1,1,10,10,10,1,1,1,10,10,10,10,10,10,1,1,1,1,1,1,1,1,10,10,10,10,10,1,1,1,10,10,10,10,10,10,1,1,1,1,1,10,10,10,10,1,1,1,10,10,10,10,10,10,1,1,10,10,10,1,1,10,10,10,1,10,10,10,10,1,1,1,1,10,1,1,1,1,1,10,10,10,10,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,10,10,10,1,1,1,10,10,10,10,10,10,1,1,1,10,1,1,1,1,10,1,1,1,1,1,1,1,10,10,10,10,10,1,1,1,1,1,1,10,10,10,10,10,10,1,10,10,10,10,10,10,10,10,1,1,1,1,1,10,10,10,10,10,10,10,1,1,1,1,1,10,1,1,1,1,1,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,1,10,10,1,1,1,10,10,1,1,10,10,1,1,10,10,10,1,1,10,1,1,1,1,1,1,10,10,10,10,1,1,10,10,10,1,10,1,1,1,1,1,1,10,10,10,10,10,10,1,10,10,10,10,1,10,1,10,10,10,1,1,1,10,10,10,10,10,10,10,1,1,1,1,1,10,10,10,10,1,1,1,10,10,1,10,1,10,1,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,1,1,10,10,1,1,10,10,1,1,1,10,1,1,1,1,1,1,1,1,10,10,10,10,10,1,10,1,10,10,1,10,10,10,10,10,10,10,10,10,10,10,1,1,1,1,1,10,10,10,10,10,1,10,10,10,10,10,10,10,10,10,1,1,10,1,1,1,10,10,10,10,1,1,1,1,1,10,1,1,1,1,10,10,10,1,1,10,10,10,10,10,10,1,10,10,1,1,10,10,1,1,1,10,1,1,1,10,1,1,1,1,1,1,1,1,10,10,10,10,10,10,10,1,10,10,1,1,1,10,10,10,1,10,10,10,10,10,10,1,1,1,1,10,10,10,10,10,10,10,10,10,1,10,1,10,1,1,1,1,10,1,1,1,10,10,10,10,1,1,1,1,1,10,1,1,1,1,10,1,10,1,1,1,1,10,10,10,10,10,1,1,1,1,10,10,1,1,1,1,1,1,1,10,10,10,1,1,1,1,1,1,1,10,10,10,10,10,10,1,10,10,10,1,1,10,10,10,1,1,10,10,10,10,1,1,1,1,10,10,1,10,10,10,10,10,1,1,1,1,1,10,1,1,1,10,10,10,1,1,10,10,10,10,1,1,1,1,1,1,1,1,10,1,10,10,10,1,1,1,10,1,10,1,10,10,1,1,1,1,10,10,1,1,1,1,1,1,1,1,10,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,10,10,1,1,1,10,10,1,1,1,10,10,10,10,10,1,1,10,10,1,1,1,1,10,10,1,1,1,1,1,1,1,1,1,1,1,10,10,10,1,10,10,10,10,10,1,1,1,1,1,1,1,10,10,10,10,1,1,1,1,10,10,10,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,10,1,10,1,1,1,10,1,10,10,10,10,10,10,10,1,1,1,1,10,1,1,1,10,10,10,10,10,10,1,10,10,1,1,1,1,10,10,1,10,10,1,1,1,1,1,1,1,10,10,10,1,1,10,10,10,10,1,1,1,1,1,1,1,1,10,1,10,1,1,1,1,10,10,10,10,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,10,10,1,1,1,10,10,10,10,10,1,10,10,10,10,10,10,10,10,10,1,1,1,1,10,1,1,10,10,10,10,10,10,10,10,10,10,10,1,10,10,10,10,10,10,1,10,1,1,1,1,10,10,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,10,10,10,10,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,10,10,10,10,1,10,10,10,1,1,1,1,10,1,1,1,10,10,10,10,1,1,1,1,10,10,1,1,1,10,1,1,10,10,10,10,1,10,10,10,10,10,10,10,10,10,10,1,1,1,10,10,10,10,10,10,10,10,1,1,1,1,1,1,10,10,1,10,1,1,1,1,1,1,1,1,1,1,1,10,1,1,1,10,1,10,10,10,10,10,1,1,1,1,1,1,10,10,10,10,10,10,1,1,1,1,1,10,1,1,1,1,1,10,10,10,10,1,1,10,10,10,1,1,1,1,1,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,1,1,1,1,10,10,10,10,1,1,1,10,1,10,1,1,10,10,10,10,10,10,1,1,1,1,1,1,1,1,1,1,1,10,10,10,1,10,1,1,1,10,10,1,1,1,1,1,10,1,1,1,1,10,10,10,1,1,1,10,10,10,1,1,1,1,1,1,1,10,1,1,1,10,10,10,1,1,1,1,1,10,1,10,1,10,10,10,1,1,1,1,10,10,10,1,1,1,1,1,1,1,1,1,1,1,1,10,1,10,1,10,10,10,1,1,1,10,10,10,1,1,1,1,10,1,1,1,1,1,1,1,1,10,1,1,1,10,10,1,1,1,1,10,10,1,1,1,1,1,10,10,10,10,10,10,10,10,1,1,1,1,1,1,1,10,10,10,10,1,10,10,10,1,10,10,10,10,10,10,1,10,10,10,10,1,1,1,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,1,10,10,10,10,10,1,1,1,10,10,10,1,1,1,1,1,10,10,10,1,1,1,1,1,10,10,10,1,1,10,10,1,10,10,1,1,1,10,10,10,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,1,10,10,10,10,1,10,10,10,10,10,10,10,1,1,10,10,10,1,1,1,1,1,10,10,10,1,1,1,10,1,1,1,1,1,1,1,10,1,1,1,1,1,1,1,1,1,1,1,1,1,10,1,1,1,1,1,10,10,10,10,1,1,1,10,10,10,10,10,1,10,10,10,10,10,1,10,1,1,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,1,1,1,10,10,10,10,1,10,10,10,10,10,10,10,10,10,10,10,10,10,1,1,1,10,10,10,10,10,1,10,10,1,1,1,1,1,10,10,10,10,1,1,1,10,10,1,1,10,1,10,1,10,10,10,10,1,1,1,1,1,10,10,1,1,1,1,1,10,1,10,1,10,10,10,10,10,10,10,1,1,1,10,10,10,10,10,10,10,10,10,10,1,1,1,1,1,1,1,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,1,1,1,1,1,10,10,1,1,10,1,1,1,1,1,1,10,10,10,1,1,1,1,1,10,10,1,10,1,1,1,10,10,10,10,1,1,1,1,1,1,10,1,1,1,10,10,10,1,10,1,10,10,1,1,1,10,1,1,1,1,1,10,10,1,10,10,10,10,1,1,1,1,1,1,1,1,1,10,10,10,10,10,10,1,1,1,1,1,1,10,10,1,10,10,10,1,1,1,10,10,10,1,1,1,1,1,1,1,10,10,1,1,10,10,10,10,1,1,10,10,1,1,1,1,10,10,10,10,10,10,10,1,1,1,1,1,1,1,1,1,10,1,1,1,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,1,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]

costf :: Position -> Int
costf pos = lookupA grid 10 pos

next :: Position -> Position -> [(Position, Int)]
next parent pos = zip n (map costf n)
  where n = next_steps parent pos

total_cost :: [Position] -> Int
total_cost [] = 0
total_cost (p : ps) = costf p + total_cost ps

validate_path :: String -> [Position] -> IO ()
validate_path _ [] = return ()
validate_path _ [_] = return ()
validate_path hdr (p1 : p2 : ps) = do
  if not (is_neighbour p1 p2)
    then putStrLn (hdr ++ "tries to step from " ++ show p1 ++
                   " to " ++ show p2)
    else return ()
  validate_path hdr (p2 : ps)

{-# NOTINLINE run_test #-}
run_test :: Position -> Position -> Int -> IO ()
run_test from to cost = do
  let path = astar next (to `posdist`) (to ==) from
  let path_hdr = "Search: Path " ++ show from ++ " -> " ++ show to ++ ": "
  if head path /= from
    then putStrLn (path_hdr ++ "path starts at " ++ show (head path))
    else return ()
  if last path /= to
    then putStrLn (path_hdr ++ "path starts at " ++ show (last path))
    else return ()
  if total_cost (tail path) /= cost
    then putStrLn (path_hdr ++ "cost " ++ show (total_cost path) ++
                   " is not expected " ++ show cost ++ "\n")
    else return ()
  validate_path path_hdr path

test_paths :: [(Position, Position, Int)]
test_paths = [
  ((5,5),(60,60),100),
  ((14,81),(3,7),115),
  ((40,40),(50,50),35),
  ((30,10),(10,30),37),
  ((70,50),(5,50),73)
  ]

run_tests :: IO ()
run_tests =
  sequence_ (map (\(from, to, cost) -> run_test from to cost) test_paths)

-- Support a repeat count in order to make this module useful
-- for profiling (otherwise the test is far too fast)
repeats :: IO Int
repeats = do
  args <- getArgs
  if length args > 0
    then return (read (head args))
    else return 1

main :: IO ()
main = do
  reps <- repeats
  sequence_ (replicate reps run_tests)