marching-cubes (empty) → 0.1.0.0
raw patch · 11 files changed
+1784/−0 lines, 11 filesdep +arraydep +basedep +containerssetup-changed
Dependencies added: array, base, containers, extra, linear, matrix, split, vector
Files
- CHANGELOG.md +6/−0
- LICENSE +30/−0
- README.md +10/−0
- Setup.hs +2/−0
- marching-cubes.cabal +49/−0
- src/MarchingCubes.hs +12/−0
- src/MarchingCubes/Internal.hs +274/−0
- src/MarchingCubes/MarchingCubes.hs +179/−0
- src/MarchingCubes/Mesh.hs +124/−0
- src/MarchingCubes/Tables.hs +996/−0
- src/MarchingCubes/Utils.hs +102/−0
+ CHANGELOG.md view
@@ -0,0 +1,6 @@+# Changelog for `marching-cubes`+++## 0.1.0.0 - 2023-20-02++First release
+ LICENSE view
@@ -0,0 +1,30 @@+Copyright Stéphane Laurent (c) 2023++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++ * Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer.++ * Redistributions in binary form must reproduce the above+ copyright notice, this list of conditions and the following+ disclaimer in the documentation and/or other materials provided+ with the distribution.++ * Neither the name of Stéphane Laurent nor the names of other+ contributors may be used to endorse or promote products derived+ from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ README.md view
@@ -0,0 +1,10 @@+# marching-cubes++<!-- badges: start -->+[](https://github.com/stla/marching-cubes/actions/workflows/Stack-lts.yml)+[](https://github.com/stla/marching-cubes/actions/workflows/Stack-nightly.yml)+<!-- badges: end -->+++Pure Haskell implementation of the marching cubes algorithm. +See [some examples here](https://github.com/stla/isosurfaces).
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ marching-cubes.cabal view
@@ -0,0 +1,49 @@+name: marching-cubes+version: 0.1.0.0+synopsis: Marching Cubes+description: Pure Haskell implementation of the marching cubes algorithm.+homepage: https://github.com/stla/marching-cubes#readme+license: BSD3+license-file: LICENSE+author: Stéphane Laurent+maintainer: laurent_step@outlook.fr+copyright: 2023 Stéphane Laurent+category: Computational geometry+build-type: Simple+extra-source-files: README.md+ CHANGELOG.md+cabal-version: >=1.10++library+ hs-source-dirs: src+ exposed-modules: MarchingCubes+ other-modules: MarchingCubes.Utils+ , MarchingCubes.Tables+ , MarchingCubes.Internal+ , MarchingCubes.MarchingCubes+ , MarchingCubes.Mesh+ other-extensions: BangPatterns+ , FlexibleContexts+ , TupleSections+ build-depends: base >= 4.7 && < 5+ , vector >= 0.12.3.1+ , matrix >= 0.3.6.1+ , array >= 0.5.4.0+ , extra >= 1.7.9+ , split >= 0.2.3.4+ , linear >= 1.21.6+ , containers >= 0.6.4.1+ default-language: Haskell2010+ ghc-options: -Wall+ -Wcompat+ -Widentities+ -Wincomplete-record-updates+ -Wincomplete-uni-patterns+ -Wmissing-export-lists+ -Wmissing-home-modules+ -Wpartial-fields+ -Wredundant-constraints++source-repository head+ type: git+ location: https://github.com/stla/marching-cubes
+ src/MarchingCubes.hs view
@@ -0,0 +1,12 @@+module MarchingCubes+ ( module X+ ) where+import MarchingCubes.MarchingCubes as X+ ( Voxel+ , XYZ+ , makeVoxel+ )+import MarchingCubes.Mesh as X+ ( Mesh (..)+ , makeMesh+ )
+ src/MarchingCubes/Internal.hs view
@@ -0,0 +1,274 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE FlexibleContexts #-}+module MarchingCubes.Internal+ ( module MarchingCubes.Internal+ ) where+import Data.Array.Unboxed ( IArray(..)+ , UArray+ )+import qualified Data.Array.Unboxed as A+import Data.Bits ( shiftL )+import qualified Data.Foldable as F+import Data.List ( zipWith4 )+import Data.Matrix ( Matrix(..)+ , elementwiseUnsafe+ , fromLists+ , getElem+ , getRow+ , matrix+ , minorMatrix+ , scaleMatrix+ )+import qualified Data.Matrix as M+import Data.Sequence ( Seq+ , (|>)+ )+import qualified Data.Sequence as S+import qualified Data.Vector as V+import Data.Vector.Unboxed ( (!)+ , Unbox+ , Vector+ )+import qualified Data.Vector.Unboxed as UV+import MarchingCubes.Tables ( crf+ , facePoints+ , indexArray+ )+import MarchingCubes.Utils ( arrayToMatrix+ , kro1+ , kro2+ , levelMatrix+ , whichIndicesAndItems+ )++facesNo7+ :: (Num a, Ord a, Unbox a)+ => Vector Int+ -> Vector Int+ -> Vector a+ -> Int+ -> Int+ -> [Int]+facesNo7 faces p1 values l j = map fun [0 .. l - 1]+ where+ fun i = if temp == 1 then shiftL 1 (j - 1) else 0+ where+ f = abs (faces ! i) - 1+ e = facePoints V.! f+ e1 = e ! 1+ e2 = e ! 2+ e3 = e ! 3+ e4 = e ! 4+ p = p1 ! i - 2+ a = values ! (p + e1)+ b = values ! (p + e2)+ c = values ! (p + e3)+ d = values ! (p + e4)+ temp =+ (if faces ! i > 0 then 1 :: Int else -1)+ * (if a * b - c * d > 0 then 1 else -1)++faces7+ :: (RealFloat a, Unbox a)+ => Vector Int+ -> Vector Int+ -> Vector a+ -> Int+ -> Int+ -> [Int]+faces7 faces p1 values l j = map fun [0 .. l - 1]+ where+ fun i = if temp == 1 then shiftL 1 (j - 1) else 0+ where+ p = (p1 ! i) - 1+ a0 = values ! p+ b0 = values ! (p + 3)+ c0 = values ! (p + 2)+ d0 = values ! (p + 1)+ a1 = values ! (p + 4)+ b1 = values ! (p + 7)+ c1 = values ! (p + 6)+ d1 = values ! (p + 5)+ a = (a1 - a0) * (c1 - c0) - (b1 - b0) * (d1 - d0)+ b = c0 * (a1 - a0) + a0 * (c1 - c0) - d0 * (b1 - b0) - b0 * (d1 - d0)+ c = a0 * c0 - b0 * d0+ tmax = -b / 2 / a+ mxmm = a * tmax * tmax + b * tmax + c+ mxmm' = if isNaN mxmm then -1 else mxmm+ cond1 = a < 0+ cond2 = tmax > 0+ cond3 = tmax < 1+ cond4 = mxmm' > 0+ totalcond = cond1 && cond2 && cond3 && cond4+ temp =+ (if faces ! i > 0 then 1 :: Int else -1) * (if totalcond then 1 else -1)++faceType :: Real a => Matrix a -> a -> a -> Matrix Int+faceType mtrx level mx = elementwiseUnsafe (+) sum1 sum2+ where+ lm = levelMatrix mtrx level (level < mx)+ m = nrows mtrx+ n = ncols mtrx+ minorMat = minorMatrix m n lm+ sminorMat2 = scaleMatrix 2 (minorMatrix 1 n lm)+ sminorMat4 = scaleMatrix 4 (minorMatrix 1 1 lm)+ sminorMat8 = scaleMatrix 8 (minorMatrix m 1 lm)+ sum1 = elementwiseUnsafe (+) minorMat sminorMat2+ sum2 = elementwiseUnsafe (+) sminorMat4 sminorMat8++levCells+ :: (Real a, IArray UArray a)+ => UArray (Int, Int, Int) a+ -> a+ -> a+ -> Matrix Int+levCells a level mx = out+ where+ bottomTypes = faceType (arrayToMatrix a 0) level mx+ (_, (nx', ny', nz')) = bounds a+ -- nx = nx' + 1+ -- ny = ny' + 1+ -- nz = nz' + 1+ (lengths, cells, types) = go 0 S.empty bottomTypes S.empty S.empty+ go+ :: Int+ -> Seq Int+ -> Matrix Int+ -> Seq (Seq Int)+ -> Seq (Seq Int)+ -> (Seq Int, Seq (Seq Int), Seq (Seq Int))+ go k !lngths !bTypes !clls !tps+ | k == nz' = (lngths, clls, tps)+ | otherwise = go (k + 1) (lngths |> l) tTypes (clls |> cll) (tps |> tp)+ where+ tTypes = faceType (arrayToMatrix a (k + 1)) level mx+ cellTypes = elementwiseUnsafe (+) bTypes (scaleMatrix 16 tTypes)+ goodcells = whichIndicesAndItems cellTypes+ l = S.length goodcells+ cll = fmap (\(i, _) -> i + nx' * ny' * k + 1) goodcells+ tp = fmap snd goodcells+ out = M.transpose (fromLists (concatMap f [0 .. nz' - 1]))+ f k = map (g k) [0 .. S.index lengths k - 1]+ g k l =+ [ c `mod` nx' + 1+ , (c `div` nx') `mod` ny' + 1+ , c `div` (nx' * ny') + 1+ , S.index (S.index types k) l+ ]+ where c = S.index (S.index cells k) l - 1++getBasic1 :: Vector Int -> Matrix Int -> Matrix Int+getBasic1 r vivjvk = elementwiseUnsafe (+) k1 k2+ where+ nR = UV.length r+ cube1 = matrix nR 3 (\(i, j) -> getElem (r ! (i - 1) + 1) j vivjvk)+ k1 = kro1 indexArray nR+ k2 = kro2 cube1 8++getBasic2+ :: (Num a, Unbox a, IArray UArray a)+ => UArray (Int, Int, Int) a+ -> a+ -> Matrix Int+ -> Vector a+getBasic2 a level cubeco = UV.fromList values+ where+ f i j = getElem i j cubeco - 1+ values =+ [ a A.! (f i 1, f i 2, f i 3) - level | i <- [1 .. nrows cubeco - 1] ]+ ++ [0]++getTcase :: V.Vector Int -> Vector Int+getTcase types =+ UV.fromList [ crf ! (types V.! i) - 1 | i <- [0 .. V.length types - 1] ]++getR :: Vector Int -> Vector Int+getR tcase = UV.fromList $ F.toList $ go 0 S.empty+ where+ n = UV.length tcase+ go :: Int -> Seq Int -> Seq Int+ go i !out+ | i == n+ = out+ | otherwise+ = if tc == 1+ || tc == 2+ || tc == 5+ || tc == 8+ || tc == 9+ || tc == 11+ || tc == 14+ then+ go (i + 1) (out |> i)+ else+ go (i + 1) out+ where tc = tcase ! i++lambdaMu :: RealFrac a => [a] -> ([a], [a])+lambdaMu x1 = (lambda, mu)+ where+ lambda = map (\x -> fromInteger $ floor (x / 9)) x1+ mu = map (1 -) lambda++average :: Num a => ([a], [a]) -> [a] -> [a] -> [a]+average (lambda, mu) = zipWith4 (\a b c d -> b * c + a * d) lambda mu++average7 :: Num a => ([a], [a]) -> [a] -> [a]+average7 (lambda, mu) = zipWith3 (\a b c -> b * c + a) lambda mu++average8 :: Num a => ([a], [a]) -> [a] -> [a]+average8 (lambda, mu) = zipWith3 (\a b c -> b * c - a) lambda mu++getPoints+ :: (Unbox a, RealFrac a)+ => Matrix Int+ -> Vector a+ -> [Int]+ -> [Int]+ -> [Int]+ -> Matrix a+getPoints cubeco values p1 x1 x2 = fromLists+ [out0, out1, out2, out3, out4, out5, out6, out7]+ where+ p1x1 = zipWith (+) p1 x1+ p1x2 = zipWith (+) p1 x2+ xx1 = map fromIntegral x1+ lambdamu = lambdaMu xx1+ v1 = map (\j -> fromIntegral $ getElem (j - 1) 1 cubeco) p1x1+ w1 = map (\j -> fromIntegral $ getElem j 1 cubeco) p1+ v2 = map (\j -> fromIntegral $ getElem (j - 1) 1 cubeco) p1x2+ w2 = map (\j -> fromIntegral $ getElem (j + 1) 1 cubeco) p1+ v3 = map (\j -> fromIntegral $ getElem (j - 1) 2 cubeco) p1x1+ w3 = map (\j -> fromIntegral $ getElem (j + 1) 2 cubeco) p1+ v4 = map (\j -> fromIntegral $ getElem (j - 1) 2 cubeco) p1x2+ w4 = map (\j -> fromIntegral $ getElem (j + 2) 2 cubeco) p1+ v5 = map (\j -> fromIntegral $ getElem (j - 1) 3 cubeco) p1x1+ w5 = map (\j -> fromIntegral $ getElem (j + 1) 3 cubeco) p1+ v6 = map (\j -> fromIntegral $ getElem (j - 1) 3 cubeco) p1x2+ w6 = map (\j -> fromIntegral $ getElem (j + 5) 3 cubeco) p1+ v7 = map (\j -> values ! (j - 2)) p1x1+ v8 = map (\j -> values ! (j - 2)) p1x2+ out0 = average lambdamu v1 w1+ out1 = average lambdamu v2 w2+ out2 = average lambdamu v3 w3+ out3 = average lambdamu v4 w4+ out4 = average lambdamu v5 w5+ out5 = average lambdamu v6 w6+ out6 = average7 lambdamu v7+ out7 = average8 lambdamu v8++calPoints :: Fractional a => Matrix a -> Matrix a+calPoints points = M.transpose $ fromLists [x, y, z]+ where+ x1 = getRow 1 points+ x2 = getRow 2 points+ y1 = getRow 3 points+ y2 = getRow 4 points+ z1 = getRow 5 points+ z2 = getRow 6 points+ v1 = getRow 7 points+ v2 = getRow 8 points+ s = V.zipWith (\a b -> a / (a - b)) v1 v2+ x = V.toList $ V.zipWith3 (\a b c -> a + c * (b - a)) x1 x2 s+ y = V.toList $ V.zipWith3 (\a b c -> a + c * (b - a)) y1 y2 s+ z = V.toList $ V.zipWith3 (\a b c -> a + c * (b - a)) z1 z2 s
+ src/MarchingCubes/MarchingCubes.hs view
@@ -0,0 +1,179 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE FlexibleContexts #-}+module MarchingCubes.MarchingCubes+ ( Voxel+ , XYZ+ , marchingCubes+ , makeVoxel+ ) where+import Data.Array.Unboxed ( IArray+ , UArray+ , listArray+ )+import qualified Data.Foldable as F+import Data.List ( elemIndices+ , findIndices+ )+import Data.Matrix ( (<->)+ , Matrix(ncols)+ , getCol+ , getRow+ , mapCol+ , submatrix+ )+import qualified Data.Matrix as M+import Data.Maybe ( catMaybes+ , mapMaybe+ )+import qualified Data.Vector as V+import Data.Vector.Unboxed ( (!)+ , Unbox+ )+import qualified Data.Vector.Unboxed as UV+import MarchingCubes.Internal ( calPoints+ , faces7+ , facesNo7+ , getBasic1+ , getBasic2+ , getPoints+ , getR+ , getTcase+ , levCells+ )+import MarchingCubes.Tables ( edgePoints+ , edgesLengths+ , edgesTable+ , edgesTable2+ , facesTable+ , specialInd+ , specialName+ , specialNedge+ , specialNface+ , specialPos+ )+import MarchingCubes.Utils ( cbind+ , jthColumn+ , matrix2listMinusFirstColumn+ , replicateEach+ , replicateEach'+ , subMatrix+ , vector2matrix+ )++type Bounds a = ((a, a), (a, a), (a, a))+type Dims = (Int, Int, Int)+type Voxel a = ((UArray Dims a, a), (Bounds a, Dims))+type XYZ a = (a, a, a)++-- | Make the voxel. +makeVoxel+ :: (RealFloat a, IArray UArray a)+ => (XYZ a -> a) -- ^ the function defining the isosurface+ -> Bounds a -- ^ bounds of the grid+ -> Dims -- ^ numbers of subdivisions of the grid+ -> Voxel a+makeVoxel fun bds@((xm, xM), (ym, yM), (zm, zM)) dims@(nx, ny, nz) =+ ((listArray ((0, 0, 0), (nx - 1, ny - 1, nz - 1)) values, mxmm), (bds, dims))+ where+ x_ = [ xm + (xM - xm) * fracx i | i <- [0 .. nx - 1] ]+ fracx p = realToFrac p / (realToFrac nx - 1)+ y_ = [ ym + (yM - ym) * fracy i | i <- [0 .. ny - 1] ]+ fracy p = realToFrac p / (realToFrac ny - 1)+ z_ = [ zm + (zM - zm) * fracz i | i <- [0 .. nz - 1] ]+ fracz p = realToFrac p / (realToFrac nz - 1)+ values = [ fun (x, y, z) | x <- x_, y <- y_, z <- z_ ]+ mxmm = maximum (filter (not . isNaN) values)++rescale :: Fractional a => (a, a) -> Int -> a -> a+rescale (minmm, maxmm) n w = minmm + (maxmm - minmm) * w / fromIntegral (n - 1)++rescaleMatrix :: Fractional a => Matrix a -> Bounds a -> Dims -> Matrix a+rescaleMatrix mtrx (xbds, ybds, zbds) (nx, ny, nz) = mtrx'''+ where+ mtrx' = mapCol (\_ w -> rescale xbds nx (w - 1)) 1 mtrx+ mtrx'' = mapCol (\_ w -> rescale ybds ny (w - 1)) 2 mtrx'+ mtrx''' = mapCol (\_ w -> rescale zbds nz (w - 1)) 3 mtrx''++marchingCubes+ :: (RealFloat a, Unbox a, IArray UArray a) => Voxel a -> a -> Matrix a+marchingCubes ((voxel, mx), (bds, dims)) level = rescaleMatrix+ (maybe triangles1 (triangles1 <->) triangles2)+ bds+ dims+ where+ ijkt = levCells voxel level mx+ vt = getRow 4 ijkt+ tcase = getTcase vt+ r = getR tcase+ nR = UV.length r+ ijk = submatrix 1 3 1 (ncols ijkt) ijkt+ vivjvk = M.transpose ijk+ cubeco = getBasic1 r vivjvk+ values = getBasic2 voxel level cubeco+ p1 = [ 8 * i + 1 | i <- [0 .. nR - 1] ]+ cases = UV.map (\j -> vt V.! j - 1) r+ edgeslengths = UV.map (edgesLengths UV.!) cases+ p1rep = F.toList $ replicateEach p1 (UV.toList edgeslengths)+ edges =+ [ (edgesTable V.! (cases ! i)) ! j+ | i <- [0 .. nR - 1]+ , j <- [0 .. edgeslengths ! i - 1]+ ]+ epoints = map (\j -> edgePoints V.! (j - 1)) edges+ x1 = map (! 1) epoints+ x2 = map (! 2) epoints+ points = getPoints cubeco values p1rep x1 x2+ triangles1 = calPoints points+ -- ~~## special cases ##~~+ specialCases = map (`UV.elemIndices` tcase) specialName+ r3s = filter (not . UV.null) specialCases+ cs = findIndices (not . UV.null) specialCases+ setOfTriangles = catMaybes (zipWith special cs r3s)+ special c r3 = if null newtriangles+ then Nothing+ else Just $ foldl1 (<->) newtriangles+ where+ nR3 = UV.length r3+ cubeco3 = getBasic1 r3 vivjvk+ values3 = getBasic2 voxel level cubeco3+ p13 = UV.map (\i -> 8 * i + 1) (UV.enumFromN 0 nR3)+ cases3 = [ vt V.! (r3 ! i) - 1 | i <- [0 .. nR3 - 1] ]+ nedge = specialNedge ! c+ faces3 = UV.concat $ map (facesTable V.!) cases3+ index3 = case c of+ 0 -> facesNo7 faces3 p13 values3 nR3 1+ 1 -> faces7 faces3 p13 values3 nR3 1+ _ -> index3'+ where+ nface = specialNface ! c+ facelast = jthColumn faces3 nface (nface - 1)+ index3' = loop 0 (faces7 facelast p13 values3 nR3 nface)+ loop j !idx+ | j == nface - 1+ = idx+ | otherwise+ = let facej = jthColumn faces3 nface j+ in let temp = facesNo7 facej p13 values3 nR3 (j + 1)+ in loop (j + 1) (zipWith (+) idx temp)+ edges3' = UV.toList $ UV.concat $ map (edgesTable2 V.!) cases3+ edges3 = vector2matrix edges3' nedge+ edgesp1index = cbind edges3 (UV.toList p13) index3+ ind3 = specialInd V.! c+ newtriangles = mapMaybe f [0 .. UV.length ind3 - 1]+ f j = triangles3+ where+ wrows = elemIndices (ind3 ! j) index3+ triangles3 = if null wrows then Nothing else Just $ calPoints points3+ where+ wcols = UV.cons nedge ((specialPos V.! c) V.! j)+ ed = subMatrix edgesp1index wrows wcols+ col0ed = V.toList $ getCol 1 ed+ col0edrep = F.toList $ replicateEach' col0ed (UV.length wcols - 1)+ edge1 = matrix2listMinusFirstColumn ed+ epoints' = map (\k -> edgePoints V.! (k - 1)) edge1+ x1' = map (! 1) epoints'+ x2' = map (! 2) epoints'+ points3 = getPoints cubeco3 values3 col0edrep x1' x2'+ triangles2 = if null setOfTriangles+ then Nothing+ else Just $ foldl1 (<->) setOfTriangles
+ src/MarchingCubes/Mesh.hs view
@@ -0,0 +1,124 @@+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE TupleSections #-}+module MarchingCubes.Mesh+ ( makeMesh+ , Mesh (..)+ ) where+import Data.Array.Unboxed ( IArray+ , UArray+ )+import Data.Bifunctor ( bimap )+import Data.Foldable ( foldl' )+import Data.IntMap.Strict ( IntMap+ , elems+ , unionWith+ )+import qualified Data.IntMap.Strict as IM+import Data.List.Split ( chunksOf )+import Data.Map.Strict ( insertLookupWithKey )+import qualified Data.Map.Strict as M+import Data.Matrix ( Matrix+ , nrows+ , toLists+ )+import Data.Tuple.Extra ( (***)+ , curry3+ , second+ , thd3+ )+import Data.Vector.Unboxed ( (!)+ , Unbox+ , Vector+ , fromList+ )+import Linear ( V3(..)+ , (^+^)+ , (^-^)+ , cross+ , signorm+ )+import MarchingCubes.MarchingCubes ( Voxel+ , marchingCubes+ )++-- type Mesh a = ((Vector (a, a, a), [[Int]]), Vector (a, a, a))++data Mesh a = Mesh + { + _vertices :: Vector (a, a, a)+ , _faces :: [(Int, Int, Int)] + , _normals :: Vector (a, a, a)+ } + deriving Show++matrix2listOfTriples :: Matrix a -> [(a, a, a)]+matrix2listOfTriples mtrx =+ map (\row -> (row !! 0, row !! 1, row !! 2)) (toLists mtrx)++uniqueWithIndices :: (Unbox a, Ord a) => [a] -> (Vector a, Vector Int)+uniqueWithIndices list = (fromList *** fromList) $ go 0 M.empty list+ where+ go _ _ [] = ([], [])+ go i m (x : xs) = case insertLookupWithKey (curry3 thd3) x i m of+ (Nothing, m') -> bimap (x :) (i :) (go (i + 1) m' xs)+ (Just j , m') -> second (j :) (go i m' xs)++undupMesh+ :: (Unbox a, Ord a) => ([(a, a, a)], [[Int]]) -> (Vector (a, a, a), [[Int]])+undupMesh (vertices, faces) = (vertices', faces')+ where+ (vertices', idx) = uniqueWithIndices vertices+ faces' = map (map (idx !)) faces++normal :: Floating a => (a, a, a) -> (a, a, a) -> (a, a, a) -> V3 a+normal v1 v2 v3 = signorm $ cross (v3' ^-^ v1') (v2' ^-^ v1') -- (NaN,NaN,NaN) if degenerate face+ where+ toV3 (x, y, z) = V3 x y z+ v1' = toV3 v1+ v2' = toV3 v2+ v3' = toV3 v3++faceNormals+ :: (Floating a, Unbox a) => Vector (a, a, a) -> [Int] -> IntMap (V3 a)+faceNormals vs face = IM.fromList nrmls+ where+ nrml = normal (vs ! (face !! 0)) (vs ! (face !! 1)) (vs ! (face !! 2))+ nrmls = map (, nrml) face++normalsV3+ :: (Floating a, Unbox a) => (Vector (a, a, a), [[Int]]) -> IntMap (V3 a)+normalsV3 (vs, faces) = IM.map+ signorm+ (foldl' (unionWith (^+^)) IM.empty (map (faceNormals vs) faces))++normals+ :: (Floating a, Unbox a) => (Vector (a, a, a), [[Int]]) -> Vector (a, a, a)+normals mesh = fromList $ map fromV3 (elems $ normalsV3 mesh)+ where fromV3 (V3 x y z) = (x, y, z)++degenerateFace :: (Unbox a, Eq a) => Vector (a, a, a) -> [Int] -> Bool+degenerateFace vertices face = v1 == v2 || v1 == v3 || v2 == v3+ where+ v1 = vertices ! (face !! 0)+ v2 = vertices ! (face !! 1)+ v3 = vertices ! (face !! 2)++-- | Make mesh of isosurface.+makeMesh :: + (Unbox a, RealFloat a, IArray UArray a) + => Voxel a -- ^ voxel obtained with `makeVoxel`+ -> a -- ^ isovalue+ -> Mesh a+makeMesh voxel level = Mesh + {+ _vertices = vertices', _faces = faces''', _normals = normals mesh+ }+ where+ mtrx = marchingCubes voxel level+ vertices = matrix2listOfTriples mtrx+ faces = chunksOf 3 [0 .. nrows mtrx - 1]+ (vertices', faces') = undupMesh (vertices, faces)+ faces'' = filter (not . degenerateFace vertices') faces'+ faces''' = map toTriplet faces''+ mesh = (vertices', faces'')+ toTriplet ikj = (ikj !! 0, ikj !! 2, ikj !! 1)
+ src/MarchingCubes/Tables.hs view
@@ -0,0 +1,996 @@+module MarchingCubes.Tables+ ( module MarchingCubes.Tables+ ) where+import Data.Matrix ( Matrix+ , fromLists+ )+import qualified Data.Vector as V+import qualified Data.Vector.Unboxed as UV+++indexArray :: Matrix Int+indexArray = fromLists+ [ [0, 0, 0]+ , [1, 0, 0]+ , [1, 1, 0]+ , [0, 1, 0]+ , [0, 0, 1]+ , [1, 0, 1]+ , [1, 1, 1]+ , [0, 1, 1]+ ]++edgesLengths :: UV.Vector Int+edgesLengths = UV.fromList+ [3, 3, 6, 3, 0, 6, 9, 3, 6, 0, 9, 6, 9, 9, 6, 3, 6, 0, 9, 0,+ 0, 0, 12, 0, 9, 0, 12, 0, 12, 0, 9, 3, 0, 6, 9, 0, 0, 9, 12,+ 0, 0, 0, 12, 0, 0, 12, 9, 6, 9, 9, 6, 0, 0, 12, 9, 0, 12, 0,+ 9, 0, 0, 0, 6, 3, 0, 0, 0, 6, 0, 9, 12, 0, 0, 0, 0, 9, 12, 12,+ 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 9, 12,+ 9, 0, 6, 9, 0, 0, 0, 0, 12, 0, 9, 6, 9, 12, 12, 9, 12, 0, 9,+ 6, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 0, 0, 0, 0, 0, 0, 6, 9, 0, 12,+ 9, 12, 12, 9, 6, 9, 0, 12, 0, 0, 0, 0, 9, 6, 0, 9, 12, 9, 0,+ 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 12, 12,+ 9, 0, 0, 0, 0, 12, 9, 0, 6, 0, 0, 0, 3, 6, 0, 0, 0, 9, 0, 12,+ 0, 9, 12, 0, 0, 6, 9, 9, 6, 9, 12, 0, 0, 12, 0, 0, 0, 12, 9,+ 0, 0, 9, 6, 0, 3, 9, 0, 12, 0, 12, 0, 9, 0, 12, 0, 0, 0, 9, 0,+ 6, 3, 6, 9, 9, 6, 9, 0, 6, 3, 9, 6, 0, 3, 6, 3, 3]++edgePoints :: V.Vector (UV.Vector Int)+edgePoints = V.fromList+ (map+ UV.fromList+ [ [1, 1, 2]+ , [2, 2, 3]+ , [3, 3, 4]+ , [4, 4, 1]+ , [5, 5, 6]+ , [6, 6, 7]+ , [7, 7, 8]+ , [8, 8, 5]+ , [9, 1, 5]+ , [10, 2, 6]+ , [11, 3, 7]+ , [12, 4, 8]+ , [13, 9, 9]+ ]+ )++edgesTable :: V.Vector (UV.Vector Int)+edgesTable = V.fromList+ (map+ UV.fromList+ [ [4, 9, 1]+ , [1, 10, 2]+ , [9, 10, 4, 10, 2, 4]+ , [2, 11, 3]+ , [0]+ , [10, 11, 1, 11, 3, 1]+ , [4, 9, 3, 3, 9, 11, 9, 10, 11]+ , [12, 4, 3]+ , [12, 9, 3, 9, 1, 3]+ , [0]+ , [3, 12, 2, 2, 12, 10, 12, 9, 10]+ , [4, 2, 12, 2, 11, 12]+ , [2, 11, 1, 1, 11, 9, 11, 12, 9]+ , [1, 10, 4, 4, 10, 12, 10, 11, 12]+ , [11, 9, 10, 11, 12, 9]+ , [8, 5, 9]+ , [5, 1, 8, 1, 4, 8]+ , [0]+ , [10, 2, 5, 5, 2, 8, 2, 4, 8]+ , [0]+ , [0]+ , [0]+ , [3, 4, 8, 3, 8, 10, 3, 10, 11, 8, 5, 10]+ , [0]+ , [8, 5, 12, 12, 5, 3, 5, 1, 3]+ , [0]+ , [2, 5, 10, 2, 3, 8, 2, 8, 5, 8, 3, 12]+ , [0]+ , [2, 11, 12, 2, 12, 5, 2, 5, 1, 8, 12, 5]+ , [0]+ , [8, 5, 12, 5, 10, 12, 12, 10, 11]+ , [6, 10, 5]+ , [0]+ , [1, 5, 2, 5, 6, 2]+ , [5, 6, 9, 9, 6, 4, 6, 2, 4]+ , [0]+ , [0]+ , [11, 3, 6, 6, 3, 5, 3, 1, 5]+ , [6, 9, 5, 6, 11, 4, 6, 4, 9, 4, 11, 3]+ , [0]+ , [0]+ , [0]+ , [3, 6, 2, 3, 9, 6, 3, 12, 9, 5, 9, 6]+ , [0]+ , [0]+ , [6, 1, 5, 6, 12, 1, 6, 11, 12, 1, 12, 4]+ , [5, 6, 9, 6, 11, 9, 9, 11, 12]+ , [8, 6, 9, 6, 10, 9]+ , [1, 4, 10, 10, 4, 6, 4, 8, 6]+ , [9, 8, 1, 1, 8, 2, 8, 6, 2]+ , [4, 8, 6, 4, 6, 2]+ , [0]+ , [0]+ , [9, 3, 1, 9, 6, 3, 9, 8, 6, 11, 6, 3]+ , [11, 3, 6, 3, 4, 6, 6, 4, 8]+ , [0]+ , [10, 1, 3, 10, 3, 8, 10, 8, 6, 3, 12, 8]+ , [0]+ , [3, 12, 2, 12, 8, 2, 2, 8, 6]+ , [0]+ , [0]+ , [0]+ , [12, 8, 11, 11, 8, 6]+ , [6, 7, 11]+ , [0]+ , [0]+ , [0]+ , [2, 6, 3, 6, 7, 3]+ , [0]+ , [6, 7, 10, 10, 7, 1, 7, 3, 1]+ , [6, 7, 3, 6, 3, 9, 6, 9, 10, 4, 3, 9]+ , [0]+ , [0]+ , [0]+ , [0]+ , [12, 4, 7, 7, 4, 6, 4, 2, 6]+ , [1, 12, 9, 1, 6, 12, 1, 2, 6, 12, 6, 7]+ , [4, 7, 12, 4, 1, 6, 4, 6, 7, 6, 1, 10]+ , [6, 7, 10, 7, 12, 10, 10, 12, 9]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [5, 7, 10, 7, 11, 10]+ , [0]+ , [2, 1, 11, 11, 1, 7, 1, 5, 7]+ , [9, 5, 7, 9, 7, 2, 9, 2, 4, 7, 11, 2]+ , [10, 5, 2, 2, 5, 3, 5, 7, 3]+ , [0]+ , [3, 1, 5, 3, 5, 7]+ , [4, 9, 3, 9, 5, 3, 3, 5, 7]+ , [0]+ , [0]+ , [0]+ , [0]+ , [10, 5, 7, 10, 7, 4, 10, 4, 2, 12, 7, 4]+ , [0]+ , [12, 4, 7, 4, 1, 7, 7, 1, 5]+ , [9, 5, 12, 12, 5, 7]+ , [7, 11, 8, 8, 11, 9, 11, 10, 9]+ , [1, 11, 10, 1, 8, 11, 1, 4, 8, 7, 8, 11]+ , [8, 1, 9, 8, 7, 2, 8, 2, 1, 2, 7, 11]+ , [7, 11, 8, 11, 2, 8, 8, 2, 4]+ , [2, 10, 9, 2, 9, 7, 2, 7, 3, 9, 8, 7]+ , [0]+ , [9, 8, 1, 8, 7, 1, 1, 7, 3]+ , [8, 7, 4, 4, 7, 3]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [8, 7, 12]+ , [8, 12, 7]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [8, 4, 7, 4, 3, 7]+ , [9, 1, 8, 8, 1, 7, 1, 3, 7]+ , [0]+ , [2, 9, 10, 2, 7, 9, 2, 3, 7, 9, 7, 8]+ , [7, 8, 11, 11, 8, 2, 8, 4, 2]+ , [8, 9, 1, 8, 2, 7, 8, 1, 2, 2, 11, 7]+ , [1, 10, 11, 1, 11, 8, 1, 8, 4, 7, 11, 8]+ , [7, 8, 11, 8, 9, 11, 11, 9, 10]+ , [9, 12, 5, 12, 7, 5]+ , [12, 7, 4, 4, 7, 1, 7, 5, 1]+ , [0]+ , [10, 7, 5, 10, 4, 7, 10, 2, 4, 12, 4, 7]+ , [0]+ , [0]+ , [0]+ , [0]+ , [4, 3, 9, 9, 3, 5, 3, 7, 5]+ , [3, 5, 1, 3, 7, 5]+ , [0]+ , [10, 2, 5, 2, 3, 5, 5, 3, 7]+ , [9, 7, 5, 9, 2, 7, 9, 4, 2, 7, 2, 11]+ , [2, 11, 1, 11, 7, 1, 1, 7, 5]+ , [0]+ , [5, 10, 7, 7, 10, 11]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [6, 10, 7, 7, 10, 12, 10, 9, 12]+ , [4, 12, 7, 4, 6, 1, 4, 7, 6, 6, 10, 1]+ , [1, 9, 12, 1, 12, 6, 1, 6, 2, 12, 7, 6]+ , [12, 7, 4, 7, 6, 4, 4, 6, 2]+ , [0]+ , [0]+ , [0]+ , [0]+ , [6, 3, 7, 6, 9, 3, 6, 10, 9, 4, 9, 3]+ , [6, 10, 7, 10, 1, 7, 7, 1, 3]+ , [0]+ , [2, 3, 6, 6, 3, 7]+ , [0]+ , [0]+ , [0]+ , [6, 11, 7]+ , [12, 11, 8, 11, 6, 8]+ , [0]+ , [0]+ , [0]+ , [3, 2, 12, 12, 2, 8, 2, 6, 8]+ , [0]+ , [10, 3, 1, 10, 8, 3, 10, 6, 8, 3, 8, 12]+ , [0]+ , [11, 6, 3, 3, 6, 4, 6, 8, 4]+ , [9, 1, 3, 9, 3, 6, 9, 6, 8, 11, 3, 6]+ , [0]+ , [0]+ , [4, 6, 8, 4, 2, 6]+ , [9, 1, 8, 1, 2, 8, 8, 2, 6]+ , [1, 10, 4, 10, 6, 4, 4, 6, 8]+ , [8, 9, 6, 6, 9, 10]+ , [5, 9, 6, 6, 9, 11, 9, 12, 11]+ , [6, 5, 1, 6, 1, 12, 6, 12, 11, 1, 4, 12]+ , [0]+ , [0]+ , [3, 2, 6, 3, 6, 9, 3, 9, 12, 5, 6, 9]+ , [0]+ , [0]+ , [0]+ , [6, 5, 9, 6, 4, 11, 6, 9, 4, 4, 3, 11]+ , [11, 6, 3, 6, 5, 3, 3, 5, 1]+ , [0]+ , [0]+ , [5, 9, 6, 9, 4, 6, 6, 4, 2]+ , [1, 2, 5, 5, 2, 6]+ , [0]+ , [6, 5, 10]+ , [8, 12, 5, 5, 12, 10, 12, 11, 10]+ , [0]+ , [2, 12, 11, 2, 5, 12, 2, 1, 5, 8, 5, 12]+ , [0]+ , [2, 10, 5, 2, 8, 3, 2, 5, 8, 8, 12, 3]+ , [0]+ , [8, 12, 5, 12, 3, 5, 5, 3, 1]+ , [0]+ , [3, 8, 4, 3, 10, 8, 3, 11, 10, 8, 10, 5]+ , [0]+ , [0]+ , [0]+ , [10, 5, 2, 5, 8, 2, 2, 8, 4]+ , [0]+ , [5, 8, 1, 1, 8, 4]+ , [8, 9, 5]+ , [11, 10, 9, 11, 9, 12]+ , [1, 4, 10, 4, 12, 10, 10, 12, 11]+ , [2, 1, 11, 1, 9, 11, 11, 9, 12]+ , [4, 12, 2, 2, 12, 11]+ , [3, 2, 12, 2, 10, 12, 12, 10, 9]+ , [0]+ , [12, 3, 9, 9, 3, 1]+ , [12, 3, 4]+ , [4, 3, 9, 3, 11, 9, 9, 11, 10]+ , [10, 1, 11, 11, 1, 3]+ , [0]+ , [2, 3, 11]+ , [9, 4, 10, 10, 4, 2]+ , [1, 2, 10]+ , [4, 1, 9]+ ]+ )++facesTable :: V.Vector (UV.Vector Int)+facesTable = V.fromList+ (map+ UV.fromList+ [ [0]+ , [0]+ , [0]+ , [0]+ , [5]+ , [0]+ , [0]+ , [0]+ , [0]+ , [-5]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [-1]+ , [0]+ , [7]+ , [5, 7]+ , [-1, 7]+ , [0]+ , [-4]+ , [0]+ , [-5, -1, -4, 7]+ , [0]+ , [-4, 7]+ , [0]+ , [-4, -1, 7]+ , [0]+ , [0]+ , [1]+ , [0]+ , [0]+ , [-2]+ , [-2, 1, 5, -7]+ , [0]+ , [0]+ , [-7]+ , [1, -7]+ , [-5, -7]+ , [0]+ , [-2, -7]+ , [-2, 1, -7]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [-2, 7]+ , [5, -2, 7]+ , [0]+ , [0]+ , [-4, -7]+ , [0]+ , [-4, -5, -7]+ , [0]+ , [-2, -4, 7]+ , [2, -7]+ , [4, 7]+ , [0]+ , [0]+ , [7]+ , [2]+ , [2, 7]+ , [0]+ , [5, 7]+ , [0]+ , [0]+ , [3]+ , [3, 7]+ , [-5, 3, 2, 7]+ , [2, 3, 7]+ , [0]+ , [0]+ , [0]+ , [0]+ , [6]+ , [6, 7]+ , [6, -1, 2, -7]+ , [2, 6, 7]+ , [6, 7]+ , [6, 5, 7]+ , [6, -1, 7]+ , [-6, -7]+ , [6, 3, -4, -7]+ , [6, 3, 7]+ , [-5, -1, 6, 3, 2, -4, 7]+ , [-3, -6, -2, 7]+ , [-4, 6, 7]+ , [-6, -7]+ , [-6, 4, 1, 7]+ , [-6]+ , [0]+ , [1, 7]+ , [0]+ , [0]+ , [0]+ , [5, 1, 7]+ , [0]+ , [0]+ , [3, -7]+ , [1, 3, 7]+ , [-5, 3, -7]+ , [-3, 7]+ , [0]+ , [-1, -7]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [-5, -7]+ , [0]+ , [0]+ , [-4, 3, -7]+ , [-3, -7]+ , [4, -3, 5, -7]+ , [-3]+ , [4, -7]+ , [-7]+ , [4]+ , [0]+ , [0]+ , [4]+ , [-7]+ , [4, -7]+ , [-3]+ , [4, -3, 5, -7]+ , [-3, -7]+ , [4, -3, -7]+ , [0]+ , [0]+ , [-5, -7]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [-1, -7]+ , [0]+ , [-3, 7]+ , [5, -3, 7]+ , [-1, -3, 7]+ , [3, -7]+ , [0]+ , [0]+ , [-5, -1, -7]+ , [0]+ , [0]+ , [0]+ , [1, 7]+ , [0]+ , [-6]+ , [-6, 4, 1, 7]+ , [-6, -7]+ , [4, -6, -7]+ , [-3, -6, -2, 7]+ , [5, 1, -6, -3, -2, 4, 7]+ , [-6, -3, -7]+ , [6, 3, -4, -7]+ , [-6, -7]+ , [-6, 1, -7]+ , [-6, -5, -7]+ , [6, 7]+ , [-2, -6, -7]+ , [6, -1, 2, -7]+ , [6, 7]+ , [6]+ , [0]+ , [0]+ , [0]+ , [0]+ , [-2, -3, 7]+ , [-5, 3, 2, 7]+ , [3, 7]+ , [3]+ , [0]+ , [0]+ , [5, 7]+ , [0]+ , [2, 7]+ , [2]+ , [7]+ , [0]+ , [0]+ , [4, 7]+ , [2, -7]+ , [2, 4, 7]+ , [0]+ , [4, 5, 7]+ , [0]+ , [-4, -7]+ , [0]+ , [0]+ , [-5, 2, -7]+ , [-2, 7]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [2, -1, -7]+ , [-2, -7]+ , [0]+ , [-5, -7]+ , [1, -7]+ , [-7]+ , [0]+ , [0]+ , [-2, 1, 5, -7]+ , [-2]+ , [0]+ , [0]+ , [1]+ , [0]+ , [0]+ , [4, 1, 7]+ , [0]+ , [-4, 7]+ , [0]+ , [-5, -1, -4, 7]+ , [0]+ , [-4]+ , [0]+ , [-1, 7]+ , [5, 7]+ , [7]+ , [0]+ , [-1]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [0]+ , [-5]+ , [0]+ , [0]+ , [0]+ , [0]+ , [5]+ , [0]+ , [0]+ , [0]+ , [0]+ ]+ )++facePoints :: V.Vector (UV.Vector Int)+facePoints = V.fromList+ (map+ UV.fromList+ [ [1, 1, 6, 2, 5, 60]+ , [2, 2, 7, 3, 6, 252]+ , [3, 4, 7, 3, 8, 672]+ , [4, 1, 8, 4, 5, 160]+ , [5, 1, 3, 2, 4, 24]+ , [6, 5, 7, 6, 8, 1680]+ ]+ )++edgesTable2 :: V.Vector (UV.Vector Int)+edgesTable2 = V.fromList + (map + UV.fromList+ [+ [0],+ [0],+ [0],+ [0],+ [2, 11, 3, 4, 9, 1, 2, 11, 1, 11, 9, 1, 11, 4, 9, 11, 3, 4],+ [0],+ [0],+ [0],+ [0],+ [1, 10, 2, 3, 12, 4, 1, 10, 4, 10, 12, 4, 10, 3, 12, 10, 2, 3],+ [0],+ [0],+ [0],+ [0],+ [0],+ [0],+ [0],+ [10, 2, 1, 9, 8, 5, 10, 2, 5, 2, 8, 5, 2, 9, 8, 2, 1, 9],+ [0],+ [2, 11, 3, 9, 8, 5, 2, 9, 3, 9, 8, 3, 11, 3, 8, 2, 11, 5, 2, 5, 9, 11, 8, 5],+ [4, 8, 1, 8, 5, 1, 2, 11, 3, 4, 8, 3, 8, 11, 3, 8, 5, 11, 2, 11, 5, 2, 5, 1, 4, 1, 2, 4, 2, 3, 3, 2, 11, 4, 8, 3, 8, 11, 3, 8, 5, 11, 2, 11, 5, 2, 5, 1],+ [10, 11, 1, 11, 3, 1, 9, 8, 5, 10, 11, 5, 11, 8, 5, 11, 3, 8, 9, 8, 3, 9, 3, 1, 10, 1, 9, 10, 9, 5, 5, 9, 8, 10, 11, 5, 11, 8, 5, 11, 3, 8, 9, 8, 3, 9, 3, 1],+ [0],+ [8, 5, 9, 4, 3, 12, 8, 5, 12, 5, 3, 12, 5, 4, 3, 5, 9, 4],+ [0],+ [2, 1, 10, 4, 3, 12, 9, 8, 5, 2, 1, 10, 4, 5, 9, 4, 3, 5, 8, 5, 3, 8, 3, 12, 4, 3, 12, 2, 1, 9, 2, 9, 8, 2, 5, 10, 2, 8, 5, 9, 8, 5, 2, 3, 12, 2, 12, 10, 10, 12, 4, 10, 4, 1, 2, 13, 10, 10, 13, 5, 8, 5, 13, 8, 13, 12, 12, 13, 3, 4, 3, 13, 4, 13, 9, 9, 13, 1, 2, 1, 13, 2, 13, 10, 2, 13, 3, 12, 13, 3, 8, 13, 12, 8, 5, 13, 9, 5, 13, 4, 13, 9, 4, 1, 13, 10, 13, 1, 8, 5, 13, 10, 13, 5, 2, 13, 10, 2, 3, 13, 12, 13, 3, 4, 13, 12, 4, 1, 13, 9, 13, 1, 9, 8, 13, 2, 3, 12, 2, 12, 5, 2, 5, 10, 8, 5, 12, 4,+ 1, 9, 2, 3, 1, 4, 1, 3, 4, 3, 12, 4, 12, 8, 4, 8, 9, 9, 8, 5, 9, 5, 1, 10, 1, 5, 2, 1, 10],+ [0],+ [4, 2, 12, 2, 11, 12, 8, 5, 9, 4, 2, 9, 2, 5, 9, 2, 11, 5, 8, 5, 11, 8, 11, 12, 4, 12, 8, 4, 8, 9, 9, 8, 5, 4, 2, 9, 2, 5, 9, 2, 11, 5, 8, 5, 11, 8, 11, 12],+ [0],+ [8, 5, 12, 5, 10, 12, 4, 1, 9, 12, 10, 11, 8, 4, 9, 8, 12, 4, 4, 11, 12, 4, 1, 11, 5, 10, 1, 5, 1, 9, 8, 5, 9, 1, 10, 11, 8, 5, 13, 5, 9, 13, 4, 13, 9, 1, 10, 13, 4, 1, 13, 11, 13, 10, 12, 13, 11, 8, 12, 13, 1, 9, 13, 8, 13, 9, 8, 5, 13, 5, 10, 13, 11, 13, 10, 12, 11, 13, 4, 13, 12, 4, 1, 13, 8, 5, 9, 4, 1, 10, 4, 10, 12, 12, 10, 11],+ [0],+ [0],+ [5, 6, 10, 1, 4, 9, 5, 6, 9, 6, 4, 9, 6, 1, 4, 6, 10, 1],+ [0],+ [0],+ [10, 5, 6, 11, 3, 2, 10, 5, 2, 5, 3, 2, 5, 11, 3, 5, 6, 11],+ [6, 10, 5, 2, 11, 3, 1, 4, 9, 6, 10, 5, 2, 9, 1, 2, 11, 9, 4, 9, 11, 4, 11, 3, 2, 11, 3, 6, 10, 1, 6, 1, 4, 6, 9, 5, 6, 4, 9, 1, 4, 9, 6, 11, 3, 6, 3, 5, 5, 3, 2, 5, 2, 10, 6, 13, 5, 5, 13, 9, 4, 9, 13, 4, 13, 3, 3, 13, 11, 2, 11, 13, 2, 13, 1, 1, 13, 10, 6, 10, 13, 6, 13, 5, 6, 13, 11, 3, 13, 11, 4, 13, 3, 4, 9, 13, 1, 9, 13, 2, 13, 1, 2, 10, 13, 5, 13, 10, 4, 9, 13, 5, 13, 9, 6, 13, 5, 6, 11, 13, 3, 13, 11, 2, 13, 3, 2, 10, 13, 1, 13, 10, 1, 4, 13, 6, 11, 3, 6, 3, 9, 6, 9, 5, 4, 9, 3, 2, 10, 1,+ 6, 11, 10, 2, 10, 11, 2, 11, 3, 2, 3, 4, 2, 4, 1, 1, 4, 9, 1, 9, 10, 5, 10, 9, 6, 10, 5],+ [0],+ [0],+ [6, 10, 5, 12, 4, 3, 6, 12, 5, 12, 4, 5, 10, 5, 4, 6, 10, 3, 6, 3, 12, 10, 4, 3],+ [1, 3, 9, 3, 12, 9, 5, 6, 10, 1, 3, 10, 3, 6, 10, 3, 12, 6, 5, 6, 12, 5, 12, 9, 1, 9, 5, 1, 5, 10, 10, 5, 6, 1, 3, 10, 3, 6, 10, 3, 12, 6, 5, 6, 12, 5, 12, 9],+ [1, 5, 2, 5, 6, 2, 3, 12, 4, 1, 5, 4, 5, 12, 4, 5, 6, 12, 3, 12, 6, 3, 6, 2, 1, 2, 3, 1, 3, 4, 4, 3, 12, 1, 5, 4, 5, 12, 4, 5, 6, 12, 3, 12, 6, 3, 6, 2],+ [0],+ [11, 12, 2, 12, 4, 2, 10, 5, 6, 11, 12, 6, 12, 5, 6, 12, 4, 5, 10, 5, 4, 10, 4, 2, 11, 2, 10, 11, 10, 6, 6, 10, 5, 11, 12, 6, 12, 5, 6, 12, 4, 5, 10, 5, 4, 10, 4, 2],+ [2, 11, 1, 1, 11, 9, 6, 10, 5, 11, 12, 9, 2, 10, 6, 2, 6, 11, 6, 11, 12, 6, 12, 5, 1, 5, 9, 1, 10, 5, 2, 10, 1, 5, 12, 9, 2, 13, 1, 1, 13, 10, 6, 10, 13, 5, 13, 9, 6, 13, 5, 12, 9, 13, 11, 12, 13, 2, 13, 11, 5, 13, 10, 2, 10, 13, 2, 13, 1, 1, 13, 9, 12, 9, 13, 11, 13, 12, 6, 11, 13, 6, 13, 5, 2, 10, 1, 6, 9, 5, 6, 11, 9, 11, 12, 9],+ [0],+ [0],+ [0],+ [0],+ [0],+ [0],+ [10, 9, 6, 9, 8, 6, 11, 3, 2, 10, 9, 2, 9, 3, 2, 9, 8, 3, 11, 3, 8, 11, 8, 6, 10, 6, 11, 10, 11, 2, 2, 11, 3, 10, 9, 2, 9, 3, 2, 9, 8, 3, 11, 3, 8, 11, 8, 6],+ [1, 4, 10, 10, 4, 6, 3, 2, 11, 4, 8, 6, 1, 2, 3, 1, 3, 4, 3, 4, 8, 3, 8, 11, 10, 11, 6, 10, 2, 11, 1, 2, 10, 11, 8, 6, 1, 13, 10, 10, 13, 2, 3, 2, 13, 11, 13, 6, 3, 13, 11, 8, 6, 13, 4, 8, 13, 1, 13, 4, 11, 13, 2, 1, 2, 13, 1, 13, 10, 10, 13, 6, 8, 6, 13, 4, 13, 8, 3, 4, 13, 3, 13, 11, 1, 2, 10, 3, 6, 11, 3, 4, 6, 4, 8, 6],+ [0],+ [0],+ [8, 6, 9, 6, 10, 9, 4, 3, 12, 8, 6, 12, 6, 3, 12, 6, 10, 3, 4, 3, 10, 4, 10, 9, 8, 9, 4, 8, 4, 12, 12, 4, 3, 8, 6, 12, 6, 3, 12, 6, 10, 3, 4, 3, 10, 4, 10, 9],+ [0],+ [9, 8, 1, 1, 8, 2, 12, 4, 3, 8, 6, 2, 9, 4, 12, 9, 12, 8, 12, 8, 6, 12, 6, 3, 1, 3, 2, 1, 4, 3, 9, 4, 1, 3, 6, 2, 9, 13, 1, 1, 13, 4, 12, 4, 13, 3, 13, 2, 12, 13, 3, 6, 2, 13, 8, 6, 13, 9, 13, 8, 3, 13, 4, 9, 4, 13, 9, 13, 1, 1, 13, 2, 6, 2, 13, 8, 13, 6, 12, 8, 13, 12, 13, 3, 9, 4, 1, 12, 2, 3, 12, 8, 2, 8, 6, 2],+ [0],+ [2, 11, 4, 10, 9, 6, 6, 9, 8, 11, 12, 4, 2, 11, 6, 2, 6, 10, 6, 11, 12, 6, 12, 8, 4, 12, 9, 9, 12, 8, 2, 10, 9, 2, 9, 4, 2, 10, 13, 2, 13, 4, 4, 13, 12, 11, 12, 13, 6, 11, 13, 6, 13, 8, 9, 8, 13, 10, 9, 13, 4, 13, 9, 2, 13, 4, 2, 11, 13, 11, 12, 13, 8, 13, 12, 6, 13, 8, 10, 13, 6, 10, 9, 13, 2, 10, 4, 10, 9, 4, 6, 11, 12, 6, 12, 8],+ [6, 11, 8, 8, 11, 12, 2, 10, 1, 6, 10, 8, 8, 10, 1, 8, 1, 12, 2, 12, 1, 2, 11, 12, 6, 2, 11, 6, 10, 2, 10, 1, 2, 6, 10, 8, 8, 10, 1, 8, 1, 12, 2, 12, 1, 2, 11, 12],+ [12, 8, 11, 11, 8, 6, 9, 4, 1, 12, 4, 11, 11, 4, 1, 11, 1, 6, 9, 6, 1, 9, 8, 6, 12, 9, 8, 12, 4, 9, 4, 1, 9, 12, 4, 11, 11, 4, 1, 11, 1, 6, 9, 6, 1, 9, 8, 6],+ [0],+ [0],+ [6, 7, 11, 1, 4, 9, 6, 1, 11, 1, 4, 11, 7, 11, 4, 6, 7, 9, 6, 9, 1, 7, 4, 9],+ [6, 7, 11, 2, 1, 10, 6, 7, 10, 7, 1, 10, 7, 2, 1, 7, 11, 2],+ [2, 4, 10, 4, 9, 10, 6, 7, 11, 2, 4, 11, 4, 7, 11, 4, 9, 7, 6, 7, 9, 6, 9, 10, 2, 10, 6, 2, 6, 11, 11, 6, 7, 2, 4, 11, 4, 7, 11, 4, 9, 7, 6, 7, 9, 6, 9, 10],+ [0],+ [2, 6, 3, 6, 7, 3, 4, 9, 1, 2, 6, 1, 6, 9, 1, 6, 7, 9, 4, 9, 7, 4, 7, 3, 2, 3, 4, 2, 4, 1, 1, 4, 9, 2, 6, 1, 6, 9, 1, 6, 7, 9, 4, 9, 7, 4, 7, 3],+ [0],+ [0],+ [12, 4, 3, 11, 6, 7, 12, 4, 7, 4, 6, 7, 4, 11, 6, 4, 3, 11],+ [12, 9, 3, 9, 1, 3, 11, 6, 7, 12, 9, 7, 9, 6, 7, 9, 1, 6, 11, 6, 1, 11, 1, 3, 12, 3, 11, 12, 11, 7, 7, 11, 6, 12, 9, 7, 9, 6, 7, 9, 1, 6, 11, 6, 1, 11, 1, 3],+ [4, 3, 12, 2, 1, 10, 11, 6, 7, 4, 3, 12, 2, 7, 11, 2, 1, 7, 6, 7, 1, 6, 1, 10, 2, 1, 10, 4, 3, 11, 4, 11, 6, 4, 7, 12, 4, 6, 7, 11, 6, 7, 4, 1, 10, 4, 10, 12, 12, 10, 2, 12, 2, 3, 4, 13, 12, 12, 13, 7, 6, 7, 13, 6, 13, 10, 10, 13, 1, 2, 1, 13, 2, 13, 11, 11, 13, 3, 4, 3, 13, 4, 13, 12, 4, 13, 1, 10, 13, 1, 6, 13, 10, 6, 7, 13, 11, 7, 13, 2, 13, 11, 2, 3, 13, 12, 13, 3, 6, 7, 13, 12, 13, 7, 4, 13, 12, 4, 1, 13, 10, 13, 1, 2, 13, 10, 2, 3, 13, 11, 13, 3, 11, 6, 13, 4, 1, 10, 4, 10, 7, 4, 7, 12, 6,+ 7, 10, 2, 3, 11, 4, 1, 3, 2, 3, 1, 2, 1, 10, 2, 10, 6, 2, 6, 11, 11, 6, 7, 11, 7, 3, 12, 3, 7, 4, 3, 12],+ [6, 7, 10, 7, 12, 10, 2, 3, 11, 10, 12, 9, 6, 2, 11, 6, 10, 2, 2, 9, 10, 2, 3, 9, 7, 12, 3, 7, 3, 11, 6, 7, 11, 3, 12, 9, 6, 7, 13, 7, 11, 13, 2, 13, 11, 3, 12, 13, 2, 3, 13, 9, 13, 12, 10, 13, 9, 6, 10, 13, 3, 11, 13, 6, 13, 11, 6, 7, 13, 7, 12, 13, 9, 13, 12, 10, 9, 13, 2, 13, 10, 2, 3, 13, 6, 7, 11, 2, 3, 12, 2, 12, 10, 10, 12, 9],+ [0],+ [0],+ [0],+ [0],+ [7, 11, 6, 5, 9, 8, 7, 11, 8, 11, 9, 8, 11, 5, 9, 11, 6, 5],+ [5, 1, 8, 1, 4, 8, 7, 11, 6, 5, 1, 6, 1, 11, 6, 1, 4, 11, 7, 11, 4, 7, 4, 8, 5, 8, 7, 5, 7, 6, 6, 7, 11, 5, 1, 6, 1, 11, 6, 1, 4, 11, 7, 11, 4, 7, 4, 8],+ [8, 5, 9, 6, 7, 11, 10, 2, 1, 8, 5, 9, 6, 1, 10, 6, 7, 1, 2, 1, 7, 2, 7, 11, 6, 7, 11, 8, 5, 10, 8, 10, 2, 8, 1, 9, 8, 2, 1, 10, 2, 1, 8, 7, 11, 8, 11, 9, 9, 11, 6, 9, 6, 5, 8, 13, 9, 9, 13, 1, 2, 1, 13, 2, 13, 11, 11, 13, 7, 6, 7, 13, 6, 13, 10, 10, 13, 5, 8, 5, 13, 8, 13, 9, 8, 13, 7, 11, 13, 7, 2, 13, 11, 2, 1, 13, 10, 1, 13, 6, 13, 10, 6, 5, 13, 9, 13, 5, 2, 1, 13, 9, 13, 1, 8, 13, 9, 8, 7, 13, 11, 13, 7, 6, 13, 11, 6, 5, 13, 10, 13, 5, 10, 2, 13, 8, 7, 11, 8, 11, 1, 8, 1, 9, 2, 1, 11, 6, 5,+ 10, 8, 7, 5, 6, 5, 7, 6, 7, 11, 6, 11, 2, 6, 2, 10, 10, 2, 1, 10, 1, 5, 9, 5, 1, 8, 5, 9],+ [10, 2, 5, 5, 2, 8, 11, 6, 7, 2, 4, 8, 10, 6, 11, 10, 11, 2, 11, 2, 4, 11, 4, 7, 5, 7, 8, 5, 6, 7, 10, 6, 5, 7, 4, 8, 10, 13, 5, 5, 13, 6, 11, 6, 13, 7, 13, 8, 11, 13, 7, 4, 8, 13, 2, 4, 13, 10, 13, 2, 7, 13, 6, 10, 6, 13, 10, 13, 5, 5, 13, 8, 4, 8, 13, 2, 13, 4, 11, 2, 13, 11, 13, 7, 10, 6, 5, 11, 8, 7, 11, 2, 8, 2, 4, 8],+ [7, 3, 6, 3, 2, 6, 5, 9, 8, 7, 3, 8, 3, 9, 8, 3, 2, 9, 5, 9, 2, 5, 2, 6, 7, 6, 5, 7, 5, 8, 8, 5, 9, 7, 3, 8, 3, 9, 8, 3, 2, 9, 5, 9, 2, 5, 2, 6],+ [6, 7, 2, 5, 1, 8, 8, 1, 4, 7, 3, 2, 6, 7, 8, 6, 8, 5, 8, 7, 3, 8, 3, 4, 2, 3, 1, 1, 3, 4, 6, 5, 1, 6, 1, 2, 6, 5, 13, 6, 13, 2, 2, 13, 3, 7, 3, 13, 8, 7, 13, 8, 13, 4, 1, 4, 13, 5, 1, 13, 2, 13, 1, 6, 13, 2, 6, 7, 13, 7, 3, 13, 4, 13, 3, 8, 13, 4, 5, 13, 8, 5, 1, 13, 6, 5, 2, 5, 1, 2, 8, 7, 3, 8, 3, 4],+ [6, 7, 10, 10, 7, 1, 8, 5, 9, 7, 3, 1, 6, 5, 8, 6, 8, 7, 8, 7, 3, 8, 3, 9, 10, 9, 1, 10, 5, 9, 6, 5, 10, 9, 3, 1, 6, 13, 10, 10, 13, 5, 8, 5, 13, 9, 13, 1, 8, 13, 9, 3, 1, 13, 7, 3, 13, 6, 13, 7, 9, 13, 5, 6, 5, 13, 6, 13, 10, 10, 13, 1, 3, 1, 13, 7, 13, 3, 8, 7, 13, 8, 13, 9, 6, 5, 10, 8, 1, 9, 8, 7, 1, 7, 3, 1],+ [8, 7, 4, 4, 7, 3, 6, 5, 10, 8, 5, 4, 4, 5, 10, 4, 10, 3, 6, 3, 10, 6, 7, 3, 8, 6, 7, 8, 5, 6, 5, 10, 6, 8, 5, 4, 4, 5, 10, 4, 10, 3, 6, 3, 10, 6, 7, 3],+ [6, 7, 11, 8, 5, 9, 12, 4, 3, 6, 7, 11, 8, 3, 12, 8, 5, 3, 4, 3, 5, 4, 5, 9, 8, 5, 9, 6, 7, 12, 6, 12, 4, 6, 3, 11, 6, 4, 3, 12, 4, 3, 6, 5, 9, 6, 9, 11, 11, 9, 8, 11, 8, 7, 6, 13, 11, 11, 13, 3, 4, 3, 13, 4, 13, 9, 9, 13, 5, 8, 5, 13, 8, 13, 12, 12, 13, 7, 6, 7, 13, 6, 13, 11, 6, 13, 5, 9, 13, 5, 4, 13, 9, 4, 3, 13, 12, 3, 13, 8, 13, 12, 8, 7, 13, 11, 13, 7, 4, 3, 13, 11, 13, 3, 6, 13, 11, 6, 5, 13, 9, 13, 5, 8, 13, 9, 8, 7, 13, 12, 13, 7, 12, 4, 13, 6, 5, 9, 6, 9, 3, 6, 3, 11, 4, 3, 9, 8, 7, 12,+ 6, 5, 7, 8, 7, 5, 8, 5, 9, 8, 9, 4, 8, 4, 12, 12, 4, 3, 12, 3, 7, 11, 7, 3, 6, 7, 11],+ [8, 5, 12, 12, 5, 3, 6, 7, 11, 5, 1, 3, 8, 7, 6, 8, 6, 5, 6, 5, 1, 6, 1, 11, 12, 11, 3, 12, 7, 11, 8, 7, 12, 11, 1, 3, 8, 13, 12, 12, 13, 7, 6, 7, 13, 11, 13, 3, 6, 13, 11, 1, 3, 13, 5, 1, 13, 8, 13, 5, 11, 13, 7, 8, 7, 13, 8, 13, 12, 12, 13, 3, 1, 3, 13, 5, 13, 1, 6, 5, 13, 6, 13, 11, 8, 7, 12, 6, 3, 11, 6, 5, 3, 5, 1, 3],+ [8, 7, 12, 10, 5, 6, 2, 3, 11, 4, 1, 9, 10, 5, 6, 8, 7, 12, 3, 11, 4, 4, 9, 11, 11, 2, 9, 9, 1, 2, 2, 3, 11, 8, 7, 12, 1, 4, 10, 10, 6, 4, 4, 9, 6, 6, 5, 9, 4, 1, 9, 2, 3, 11, 5, 10, 8, 8, 12, 10, 10, 6, 12, 12, 7, 6, 4, 1, 9, 10, 5, 6, 7, 8, 11, 11, 2, 8, 8, 12, 2, 2, 3, 12, 4, 1, 9, 8, 7, 12, 10, 2, 5, 5, 3, 2, 5, 6, 3, 3, 11, 6, 10, 5, 6, 11, 3, 2, 4, 12, 1, 1, 7, 12, 1, 9, 7, 7, 8, 9, 8, 7, 12, 13, 5, 6, 13, 9, 5, 13, 4, 9, 13, 3, 4, 13, 11, 3, 13, 2, 11, 13, 1, 2, 13, 10, 1, 13, 6, 10, 10,+ 5, 6, 13, 1, 9, 13, 2, 1, 13, 11, 2, 13, 7, 11, 13, 8, 7, 13, 12, 8, 13, 3, 12, 13, 4, 3, 13, 9, 4, 8, 7, 12, 13, 4, 9, 13, 3, 4, 13, 11, 3, 13, 6, 11, 13, 5, 6, 13, 10, 5, 13, 2, 10, 13, 1, 2, 13, 9, 1, 10, 5, 6, 13, 2, 11, 13, 1, 2, 13, 9, 1, 13, 8, 9, 13, 7, 8, 13, 12, 7, 13, 4, 12, 13, 3, 4, 13, 11, 3, 2, 3, 11, 13, 7, 12, 13, 6, 7, 13, 10, 6, 13, 1, 10, 13, 4, 1, 13, 9, 4, 13, 5, 9, 13, 8, 5, 13, 12, 8, 8, 7, 12, 13, 9, 4, 13, 5, 9, 13, 6, 5, 13, 11, 6, 13, 3, 11, 13, 2, 3, 13, 10, 2, 13, 1,+ 10, 13, 4, 1, 2, 3, 11, 13, 10, 6, 13, 1, 10, 13, 4, 1, 13, 12, 4, 13, 7, 12, 13, 8, 7, 13, 9, 8, 13, 5, 9, 13, 6, 5, 4, 1, 9, 13, 3, 2, 13, 12, 3, 13, 8, 12, 13, 5, 8, 13, 10, 5, 13, 6, 10, 13, 7, 6, 13, 11, 7, 13, 2, 11, 4, 1, 9, 13, 8, 12, 13, 5, 8, 13, 10, 5, 13, 2, 10, 13, 3, 2, 13, 11, 3, 13, 6, 11, 13, 7, 6, 13, 12, 7, 2, 3, 11, 13, 6, 10, 13, 7, 6, 13, 12, 7, 13, 4, 12, 13, 1, 4, 13, 9, 1, 13, 8, 9, 13, 5, 8, 13, 10, 5, 4, 1, 9, 13, 12, 8, 13, 3, 12, 13, 2, 3, 13, 10, 2, 13, 5, 10, 13, 6,+ 5, 13, 11, 6, 13, 7, 11, 13, 8, 7, 10, 5, 6, 13, 11, 2, 13, 7, 11, 13, 8, 7, 13, 9, 8, 13, 1, 9, 13, 4, 1, 13, 12, 4, 13, 3, 12, 13, 2, 3, 13, 5, 6, 13, 9, 5, 13, 8, 9, 13, 7, 8, 13, 12, 7, 13, 4, 12, 13, 3, 4, 13, 11, 3, 13, 2, 11, 13, 1, 2, 13, 10, 1, 13, 6, 10, 13, 7, 11, 13, 8, 7, 13, 12, 8, 13, 3, 12, 13, 4, 3, 13, 9, 4, 13, 1, 9, 13, 2, 1, 13, 10, 2, 13, 5, 10, 13, 6, 5, 13, 11, 6, 13, 1, 10, 13, 4, 1, 13, 9, 4, 13, 5, 9, 13, 8, 5, 13, 12, 8, 13, 7, 12, 13, 6, 7, 13, 11, 6, 13, 3, 11, 13, 2,+ 3, 13, 10, 2, 13, 3, 2, 13, 12, 3, 13, 4, 12, 13, 1, 4, 13, 9, 1, 13, 8, 9, 13, 5, 8, 13, 10, 5, 13, 6, 10, 13, 7, 6, 13, 11, 7, 13, 2, 11, 8, 7, 12, 10, 1, 2, 6, 5, 11, 11, 9, 5, 11, 3, 9, 9, 4, 3, 6, 5, 10, 12, 3, 4, 11, 7, 2, 2, 8, 7, 2, 1, 8, 8, 9, 1, 2, 3, 11, 9, 5, 8, 10, 1, 6, 6, 4, 1, 6, 7, 4, 4, 12, 7, 4, 1, 9, 11, 7, 6, 2, 3, 10, 10, 12, 3, 10, 5, 12, 12, 8, 5, 2, 1, 10, 12, 3, 4, 12, 11, 3, 12, 7, 11, 11, 6, 7, 7, 5, 6, 7, 8, 5, 5, 9, 8, 8, 12, 9, 9, 4, 12, 12, 3, 4, 6, 7, 11, 6, 8, 7,+ 6, 5, 8, 8, 9, 5, 5, 1, 9, 5, 10, 1, 1, 2, 10, 10, 6, 2, 2, 11, 6, 9, 5, 8, 2, 1, 10, 2, 4, 1, 2, 3, 4, 4, 12, 3, 3, 7, 12, 3, 11, 7, 7, 6, 11, 11, 2, 6, 6, 10, 2, 6, 7, 11, 9, 5, 8, 9, 10, 5, 9, 1, 10, 10, 2, 1, 1, 3, 2, 1, 4, 3, 4, 12, 3, 4, 9, 12, 12, 8, 9],+ [12, 8, 7, 11, 2, 3, 6, 5, 10, 12, 8, 7, 11, 6, 5, 11, 5, 3, 10, 3, 5, 10, 2, 3, 11, 2, 3, 12, 6, 7, 12, 10, 6, 12, 8, 5, 12, 5, 10, 6, 5, 10, 12, 2, 3, 12, 8, 2, 8, 11, 2, 8, 7, 11, 12, 8, 13, 8, 5, 13, 10, 13, 5, 10, 2, 13, 2, 3, 13, 11, 13, 3, 11, 6, 13, 6, 7, 13, 12, 13, 7, 12, 8, 13, 12, 3, 13, 2, 3, 13, 10, 2, 13, 10, 13, 5, 6, 13, 5, 11, 6, 13, 11, 13, 7, 8, 7, 13, 10, 13, 5, 8, 5, 13, 12, 8, 13, 12, 13, 3, 2, 3, 13, 11, 2, 13, 11, 13, 7, 6, 7, 13, 6, 13, 10, 12, 2, 3, 12, 5, 2, 12, 8, 5,+ 10, 2, 5, 11, 6, 7, 12, 7, 3, 11, 3, 7, 11, 2, 3, 11, 10, 2, 11, 6, 10, 6, 5, 10, 6, 7, 5, 8, 5, 7, 12, 8, 7],+ [12, 4, 7, 7, 4, 6, 9, 8, 5, 4, 2, 6, 12, 8, 9, 12, 9, 4, 9, 4, 2, 9, 2, 5, 7, 5, 6, 7, 8, 5, 12, 8, 7, 5, 2, 6, 12, 13, 7, 7, 13, 8, 9, 8, 13, 5, 13, 6, 9, 13, 5, 2, 6, 13, 4, 2, 13, 12, 13, 4, 5, 13, 8, 12, 8, 13, 12, 13, 7, 7, 13, 6, 2, 6, 13, 4, 13, 2, 9, 4, 13, 9, 13, 5, 12, 8, 7, 9, 6, 5, 9, 4, 6, 4, 2, 6],+ [6, 5, 2, 2, 5, 1, 8, 7, 12, 6, 7, 2, 2, 7, 12, 2, 12, 1, 8, 1, 12, 8, 5, 1, 6, 8, 5, 6, 7, 8, 7, 12, 8, 6, 7, 2, 2, 7, 12, 2, 12, 1, 8, 1, 12, 8, 5, 1],+ [7, 12, 8, 5, 10, 6, 9, 4, 1, 7, 12, 8, 5, 9, 4, 5, 4, 6, 1, 6, 4, 1, 10, 6, 5, 10, 6, 7, 9, 8, 7, 1, 9, 7, 12, 4, 7, 4, 1, 9, 4, 1, 7, 10, 6, 7, 12, 10, 12, 5, 10, 12, 8, 5, 7, 12, 13, 12, 4, 13, 1, 13, 4, 1, 10, 13, 10, 6, 13, 5, 13, 6, 5, 9, 13, 9, 8, 13, 7, 13, 8, 7, 12, 13, 7, 6, 13, 10, 6, 13, 1, 10, 13, 1, 13, 4, 9, 13, 4, 5, 9, 13, 5, 13, 8, 12, 8, 13, 1, 13, 4, 12, 4, 13, 7, 12, 13, 7, 13, 6, 10, 6, 13, 5, 10, 13, 5, 13, 8, 9, 8, 13, 9, 13, 1, 7, 10, 6, 7, 4, 10, 7, 12, 4, 1, 10, 4, 5,+ 9, 8, 7, 8, 6, 5, 6, 8, 5, 10, 6, 5, 1, 10, 5, 9, 1, 9, 4, 1, 9, 8, 4, 12, 4, 8, 7, 12, 8],+ [8, 7, 12, 6, 5, 10, 8, 5, 12, 12, 5, 10, 12, 10, 6, 12, 6, 7],+ [0],+ [5, 7, 10, 7, 11, 10, 1, 4, 9, 5, 7, 9, 7, 4, 9, 7, 11, 4, 1, 4, 11, 1, 11, 10, 5, 10, 1, 5, 1, 9, 9, 1, 4, 5, 7, 9, 7, 4, 9, 7, 11, 4, 1, 4, 11, 1, 11, 10],+ [0],+ [0],+ [0],+ [4, 9, 3, 9, 5, 3, 2, 10, 1, 3, 5, 7, 4, 2, 1, 4, 3, 2, 2, 7, 3, 2, 10, 7, 9, 5, 10, 9, 10, 1, 4, 9, 1, 10, 5, 7, 4, 9, 13, 9, 1, 13, 2, 13, 1, 10, 5, 13, 2, 10, 13, 7, 13, 5, 3, 13, 7, 4, 3, 13, 10, 1, 13, 4, 13, 1, 4, 9, 13, 9, 5, 13, 7, 13, 5, 3, 7, 13, 2, 13, 3, 2, 10, 13, 4, 9, 1, 2, 10, 5, 2, 5, 3, 3, 5, 7],+ [0],+ [0],+ [11, 10, 7, 10, 5, 7, 12, 4, 3, 11, 10, 3, 10, 4, 3, 10, 5, 4, 12, 4, 5, 12, 5, 7, 11, 7, 12, 11, 12, 3, 3, 12, 4, 11, 10, 3, 10, 4, 3, 10, 5, 4, 12, 4, 5, 12, 5, 7],+ [9, 1, 12, 5, 7, 10, 10, 7, 11, 1, 3, 12, 9, 1, 10, 9, 10, 5, 10, 1, 3, 10, 3, 11, 12, 3, 7, 7, 3, 11, 9, 5, 7, 9, 7, 12, 9, 5, 13, 9, 13, 12, 12, 13, 3, 1, 3, 13, 10, 1, 13, 10, 13, 11, 7, 11, 13, 5, 7, 13, 12, 13, 7, 9, 13, 12, 9, 1, 13, 1, 3, 13, 11, 13, 3, 10, 13, 11, 5, 13, 10, 5, 7, 13, 9, 5, 12, 5, 7, 12, 10, 1, 3, 10, 3, 11],+ [2, 1, 11, 11, 1, 7, 4, 3, 12, 1, 5, 7, 2, 3, 4, 2, 4, 1, 4, 1, 5, 4, 5, 12, 11, 12, 7, 11, 3, 12, 2, 3, 11, 12, 5, 7, 2, 13, 11, 11, 13, 3, 4, 3, 13, 12, 13, 7, 4, 13, 12, 5, 7, 13, 1, 5, 13, 2, 13, 1, 12, 13, 3, 2, 3, 13, 2, 13, 11, 11, 13, 7, 5, 7, 13, 1, 13, 5, 4, 1, 13, 4, 13, 12, 2, 3, 11, 4, 7, 12, 4, 1, 7, 1, 5, 7],+ [7, 12, 5, 5, 12, 9, 3, 11, 2, 7, 11, 5, 5, 11, 2, 5, 2, 9, 3, 9, 2, 3, 12, 9, 7, 3, 12, 7, 11, 3, 11, 2, 3, 7, 11, 5, 5, 11, 2, 5, 2, 9, 3, 9, 2, 3, 12, 9],+ [0],+ [9, 5, 12, 12, 5, 7, 10, 1, 2, 9, 1, 12, 12, 1, 2, 12, 2, 7, 10, 7, 2, 10, 5, 7, 9, 10, 5, 9, 1, 10, 1, 2, 10, 9, 1, 12, 12, 1, 2, 12, 2, 7, 10, 7, 2, 10, 5, 7],+ [0],+ [0],+ [0],+ [0],+ [0],+ [0],+ [0],+ [3, 4, 7, 7, 4, 8, 1, 2, 10, 3, 2, 7, 7, 2, 10, 7, 10, 8, 1, 8, 10, 1, 4, 8, 3, 1, 4, 3, 2, 1, 2, 10, 1, 3, 2, 7, 7, 2, 10, 7, 10, 8, 1, 8, 10, 1, 4, 8],+ [0],+ [0],+ [4, 3, 9, 3, 11, 9, 8, 7, 12, 9, 11, 10, 4, 8, 12, 4, 9, 8, 8, 10, 9, 8, 7, 10, 3, 11, 7, 3, 7, 12, 4, 3, 12, 7, 11, 10, 4, 3, 13, 3, 12, 13, 8, 13, 12, 7, 11, 13, 8, 7, 13, 10, 13, 11, 9, 13, 10, 4, 9, 13, 7, 12, 13, 4, 13, 12, 4, 3, 13, 3, 11, 13, 10, 13, 11, 9, 10, 13, 8, 13, 9, 8, 7, 13, 4, 3, 12, 8, 7, 11, 8, 11, 9, 9, 11, 10],+ [3, 11, 1, 1, 11, 10, 7, 12, 8, 3, 12, 1, 1, 12, 8, 1, 8, 10, 7, 10, 8, 7, 11, 10, 3, 7, 11, 3, 12, 7, 12, 8, 7, 3, 12, 1, 1, 12, 8, 1, 8, 10, 7, 10, 8, 7, 11, 10],+ [8, 7, 12, 4, 1, 9, 3, 11, 2, 8, 7, 12, 4, 3, 11, 4, 11, 9, 2, 9, 11, 2, 1, 9, 4, 1, 9, 8, 3, 12, 8, 2, 3, 8, 7, 11, 8, 11, 2, 3, 11, 2, 8, 1, 9, 8, 7, 1, 7, 4, 1, 7, 12, 4, 8, 7, 13, 7, 11, 13, 2, 13, 11, 2, 1, 13, 1, 9, 13, 4, 13, 9, 4, 3, 13, 3, 12, 13, 8, 13, 12, 8, 7, 13, 8, 9, 13, 1, 9, 13, 2, 1, 13, 2, 13, 11, 3, 13, 11, 4, 3, 13, 4, 13, 12, 7, 12, 13, 2, 13, 11, 7, 11, 13, 8, 7, 13, 8, 13, 9, 1, 9, 13, 4, 1, 13, 4, 13, 12, 3, 12, 13, 3, 13, 2, 8, 1, 9, 8, 11, 1, 8, 7, 11, 2, 1, 11, 4, 3,+ 12, 8, 12, 9, 4, 9, 12, 4, 1, 9, 4, 2, 1, 4, 3, 2, 3, 11, 2, 3, 12, 11, 7, 11, 12, 8, 7, 12],+ [3, 11, 2, 7, 12, 8, 3, 12, 2, 2, 12, 8, 2, 8, 7, 2, 7, 11],+ [9, 4, 10, 10, 4, 2, 12, 8, 7, 9, 8, 10, 10, 8, 7, 10, 7, 2, 12, 2, 7, 12, 4, 2, 9, 12, 4, 9, 8, 12, 8, 7, 12, 9, 8, 10, 10, 8, 7, 10, 7, 2, 12, 2, 7, 12, 4, 2],+ [8, 7, 12, 10, 1, 2, 8, 7, 10, 10, 7, 2, 12, 2, 7, 8, 1, 12, 8, 10, 1, 12, 1, 2],+ [9, 4, 1, 12, 8, 7, 9, 8, 1, 1, 8, 7, 1, 7, 12, 1, 12, 4],+ [0],+ [0],+ [9, 1, 4, 12, 7, 8, 9, 1, 8, 1, 7, 8, 1, 12, 7, 1, 4, 12],+ [8, 12, 7, 10, 2, 1, 8, 10, 7, 10, 2, 7, 12, 7, 2, 8, 12, 1, 8, 1, 10, 12, 2, 1],+ [9, 10, 4, 10, 2, 4, 12, 7, 8, 9, 10, 8, 10, 7, 8, 10, 2, 7, 12, 7, 2, 12, 2, 4, 9, 4, 12, 9, 12, 8, 8, 12, 7, 9, 10, 8, 10, 7, 8, 10, 2, 7, 12, 7, 2, 12, 2, 4],+ [3, 2, 11, 7, 8, 12, 3, 2, 12, 2, 8, 12, 2, 7, 8, 2, 11, 7],+ [8, 12, 7, 4, 9, 1, 3, 2, 11, 8, 12, 7, 4, 11, 3, 4, 9, 11, 2, 11, 9, 2, 9, 1, 4, 9, 1, 8, 12, 3, 8, 3, 2, 8, 11, 7, 8, 2, 11, 3, 2, 11, 8, 9, 1, 8, 1, 7, 7, 1, 4, 7, 4, 12, 8, 13, 7, 7, 13, 11, 2, 11, 13, 2, 13, 1, 1, 13, 9, 4, 9, 13, 4, 13, 3, 3, 13, 12, 8, 12, 13, 8, 13, 7, 8, 13, 9, 1, 13, 9, 2, 13, 1, 2, 11, 13, 3, 11, 13, 4, 13, 3, 4, 12, 13, 7, 13, 12, 2, 11, 13, 7, 13, 11, 8, 13, 7, 8, 9, 13, 1, 13, 9, 4, 13, 1, 4, 12, 13, 3, 13, 12, 3, 2, 13, 8, 9, 1, 8, 1, 11, 8, 11, 7, 2, 11, 1, 4, 12,+ 3, 8, 9, 12, 4, 12, 9, 4, 9, 1, 4, 1, 2, 4, 2, 3, 3, 2, 11, 3, 11, 12, 7, 12, 11, 8, 12, 7],+ [3, 1, 11, 1, 10, 11, 7, 8, 12, 3, 1, 12, 1, 8, 12, 1, 10, 8, 7, 8, 10, 7, 10, 11, 3, 11, 7, 3, 7, 12, 12, 7, 8, 3, 1, 12, 1, 8, 12, 1, 10, 8, 7, 8, 10, 7, 10, 11],+ [4, 9, 3, 3, 9, 11, 8, 12, 7, 9, 10, 11, 4, 12, 8, 4, 8, 9, 8, 9, 10, 8, 10, 7, 3, 7, 11, 3, 12, 7, 4, 12, 3, 7, 10, 11, 4, 13, 3, 3, 13, 12, 8, 12, 13, 7, 13, 11, 8, 13, 7, 10, 11, 13, 9, 10, 13, 4, 13, 9, 7, 13, 12, 4, 12, 13, 4, 13, 3, 3, 13, 11, 10, 11, 13, 9, 13, 10, 8, 9, 13, 8, 13, 7, 4, 12, 3, 8, 11, 7, 8, 9, 11, 9, 10, 11],+ [0],+ [0],+ [3, 7, 4, 7, 8, 4, 1, 10, 2, 3, 7, 2, 7, 10, 2, 7, 8, 10, 1, 10, 8, 1, 8, 4, 3, 4, 1, 3, 1, 2, 2, 1, 10, 3, 7, 2, 7, 10, 2, 7, 8, 10, 1, 10, 8, 1, 8, 4],+ [0],+ [0],+ [0],+ [0],+ [0],+ [0],+ [0],+ [9, 12, 5, 12, 7, 5, 10, 2, 1, 9, 12, 1, 12, 2, 1, 12, 7, 2, 10, 2, 7, 10, 7, 5, 9, 5, 10, 9, 10, 1, 1, 10, 2, 9, 12, 1, 12, 2, 1, 12, 7, 2, 10, 2, 7, 10, 7, 5],+ [0],+ [7, 5, 12, 5, 9, 12, 3, 2, 11, 7, 5, 11, 5, 2, 11, 5, 9, 2, 3, 2, 9, 3, 9, 12, 7, 12, 3, 7, 3, 11, 11, 3, 2, 7, 5, 11, 5, 2, 11, 5, 9, 2, 3, 2, 9, 3, 9, 12],+ [2, 11, 1, 11, 7, 1, 4, 12, 3, 1, 7, 5, 2, 4, 3, 2, 1, 4, 4, 5, 1, 4, 12, 5, 11, 7, 12, 11, 12, 3, 2, 11, 3, 12, 7, 5, 2, 11, 13, 11, 3, 13, 4, 13, 3, 12, 7, 13, 4, 12, 13, 5, 13, 7, 1, 13, 5, 2, 1, 13, 12, 3, 13, 2, 13, 3, 2, 11, 13, 11, 7, 13, 5, 13, 7, 1, 5, 13, 4, 13, 1, 4, 12, 13, 2, 11, 3, 4, 12, 7, 4, 7, 1, 1, 7, 5],+ [9, 12, 1, 5, 10, 7, 10, 11, 7, 1, 12, 3, 9, 10, 1, 9, 5, 10, 10, 3, 1, 10, 11, 3, 12, 7, 3, 7, 11, 3, 9, 7, 5, 9, 12, 7, 9, 13, 5, 9, 12, 13, 12, 3, 13, 1, 13, 3, 10, 13, 1, 10, 11, 13, 7, 13, 11, 5, 13, 7, 12, 7, 13, 9, 12, 13, 9, 13, 1, 1, 13, 3, 11, 3, 13, 10, 11, 13, 5, 10, 13, 5, 13, 7, 9, 12, 5, 5, 12, 7, 10, 3, 1, 10, 11, 3],+ [11, 7, 10, 10, 7, 5, 12, 3, 4, 11, 3, 10, 10, 3, 4, 10, 4, 5, 12, 5, 4, 12, 7, 5, 11, 12, 7, 11, 3, 12, 3, 4, 12, 11, 3, 10, 10, 3, 4, 10, 4, 5, 12, 5, 4, 12, 7, 5],+ [0],+ [0],+ [4, 3, 9, 9, 3, 5, 2, 1, 10, 3, 7, 5, 4, 1, 2, 4, 2, 3, 2, 3, 7, 2, 7, 10, 9, 10, 5, 9, 1, 10, 4, 1, 9, 10, 7, 5, 4, 13, 9, 9, 13, 1, 2, 1, 13, 10, 13, 5, 2, 13, 10, 7, 5, 13, 3, 7, 13, 4, 13, 3, 10, 13, 1, 4, 1, 13, 4, 13, 9, 9, 13, 5, 7, 5, 13, 3, 13, 7, 2, 3, 13, 2, 13, 10, 4, 1, 9, 2, 5, 10, 2, 3, 5, 3, 7, 5],+ [0],+ [0],+ [0],+ [5, 10, 7, 7, 10, 11, 1, 9, 4, 5, 9, 7, 7, 9, 4, 7, 4, 11, 1, 11, 4, 1, 10, 11, 5, 1, 10, 5, 9, 1, 9, 4, 1, 5, 9, 7, 7, 9, 4, 7, 4, 11, 1, 11, 4, 1, 10, 11],+ [0],+ [8, 12, 7, 6, 10, 5, 8, 12, 5, 12, 10, 5, 12, 6, 10, 12, 7, 6],+ [7, 8, 12, 5, 6, 10, 9, 1, 4, 7, 8, 12, 5, 4, 9, 5, 6, 4, 1, 4, 6, 1, 6, 10, 5, 6, 10, 7, 8, 9, 7, 9, 1, 7, 4, 12, 7, 1, 4, 9, 1, 4, 7, 6, 10, 7, 10, 12, 12, 10, 5, 12, 5, 8, 7, 13, 12, 12, 13, 4, 1, 4, 13, 1, 13, 10, 10, 13, 6, 5, 6, 13, 5, 13, 9, 9, 13, 8, 7, 8, 13, 7, 13, 12, 7, 13, 6, 10, 13, 6, 1, 13, 10, 1, 4, 13, 9, 4, 13, 5, 13, 9, 5, 8, 13, 12, 13, 8, 1, 4, 13, 12, 13, 4, 7, 13, 12, 7, 6, 13, 10, 13, 6, 5, 13, 10, 5, 8, 13, 9, 13, 8, 9, 1, 13, 7, 6, 10, 7, 10, 4, 7, 4, 12, 1, 4, 10, 5,+ 8, 9, 7, 6, 8, 5, 8, 6, 5, 6, 10, 5, 10, 1, 5, 1, 9, 9, 1, 4, 9, 4, 8, 12, 8, 4, 7, 8, 12],+ [6, 2, 5, 2, 1, 5, 8, 12, 7, 6, 2, 7, 2, 12, 7, 2, 1, 12, 8, 12, 1, 8, 1, 5, 6, 5, 8, 6, 8, 7, 7, 8, 12, 6, 2, 7, 2, 12, 7, 2, 1, 12, 8, 12, 1, 8, 1, 5],+ [12, 7, 4, 7, 6, 4, 9, 5, 8, 4, 6, 2, 12, 9, 8, 12, 4, 9, 9, 2, 4, 9, 5, 2, 7, 6, 5, 7, 5, 8, 12, 7, 8, 5, 6, 2, 12, 7, 13, 7, 8, 13, 9, 13, 8, 5, 6, 13, 9, 5, 13, 2, 13, 6, 4, 13, 2, 12, 4, 13, 5, 8, 13, 12, 13, 8, 12, 7, 13, 7, 6, 13, 2, 13, 6, 4, 2, 13, 9, 13, 4, 9, 5, 13, 12, 7, 8, 9, 5, 6, 9, 6, 4, 4, 6, 2],+ [12, 7, 8, 11, 3, 2, 6, 10, 5, 12, 7, 8, 11, 5, 6, 11, 3, 5, 10, 5, 3, 10, 3, 2, 11, 3, 2, 12, 7, 6, 12, 6, 10, 12, 5, 8, 12, 10, 5, 6, 10, 5, 12, 3, 2, 12, 2, 8, 8, 2, 11, 8, 11, 7, 12, 13, 8, 8, 13, 5, 10, 5, 13, 10, 13, 2, 2, 13, 3, 11, 3, 13, 11, 13, 6, 6, 13, 7, 12, 7, 13, 12, 13, 8, 12, 13, 3, 2, 13, 3, 10, 13, 2, 10, 5, 13, 6, 5, 13, 11, 13, 6, 11, 7, 13, 8, 13, 7, 10, 5, 13, 8, 13, 5, 12, 13, 8, 12, 3, 13, 2, 13, 3, 11, 13, 2, 11, 7, 13, 6, 13, 7, 6, 10, 13, 12, 3, 2, 12, 2, 5, 12, 5, 8,+ 10, 5, 2, 11, 7, 6, 12, 3, 7, 11, 7, 3, 11, 3, 2, 11, 2, 10, 11, 10, 6, 6, 10, 5, 6, 5, 7, 8, 7, 5, 12, 7, 8],+ [8, 12, 7, 10, 6, 5, 2, 11, 3, 4, 9, 1, 10, 6, 5, 8, 12, 7, 3, 4, 11, 4, 11, 9, 11, 9, 2, 9, 2, 1, 2, 11, 3, 8, 12, 7, 1, 10, 4, 10, 4, 6, 4, 6, 9, 6, 9, 5, 4, 9, 1, 2, 11, 3, 5, 8, 10, 8, 10, 12, 10, 12, 6, 12, 6, 7, 4, 9, 1, 10, 6, 5, 7, 11, 8, 11, 8, 2, 8, 2, 12, 2, 12, 3, 4, 9, 1, 8, 12, 7, 10, 5, 2, 5, 2, 3, 5, 3, 6, 3, 6, 11, 10, 6, 5, 11, 2, 3, 4, 1, 12, 1, 12, 7, 1, 7, 9, 7, 9, 8, 8, 12, 7, 13, 6, 5, 13, 5, 9, 13, 9, 4, 13, 4, 3, 13, 3, 11, 13, 11, 2, 13, 2, 1, 13, 1, 10, 13, 10, 6, 10,+ 6, 5, 13, 9, 1, 13, 1, 2, 13, 2, 11, 13, 11, 7, 13, 7, 8, 13, 8, 12, 13, 12, 3, 13, 3, 4, 13, 4, 9, 8, 12, 7, 13, 9, 4, 13, 4, 3, 13, 3, 11, 13, 11, 6, 13, 6, 5, 13, 5, 10, 13, 10, 2, 13, 2, 1, 13, 1, 9, 10, 6, 5, 13, 11, 2, 13, 2, 1, 13, 1, 9, 13, 9, 8, 13, 8, 7, 13, 7, 12, 13, 12, 4, 13, 4, 3, 13, 3, 11, 2, 11, 3, 13, 12, 7, 13, 7, 6, 13, 6, 10, 13, 10, 1, 13, 1, 4, 13, 4, 9, 13, 9, 5, 13, 5, 8, 13, 8, 12, 8, 12, 7, 13, 4, 9, 13, 9, 5, 13, 5, 6, 13, 6, 11, 13, 11, 3, 13, 3, 2, 13, 2, 10, 13, 10,+ 1, 13, 1, 4, 2, 11, 3, 13, 6, 10, 13, 10, 1, 13, 1, 4, 13, 4, 12, 13, 12, 7, 13, 7, 8, 13, 8, 9, 13, 9, 5, 13, 5, 6, 4, 9, 1, 13, 2, 3, 13, 3, 12, 13, 12, 8, 13, 8, 5, 13, 5, 10, 13, 10, 6, 13, 6, 7, 13, 7, 11, 13, 11, 2, 4, 9, 1, 13, 12, 8, 13, 8, 5, 13, 5, 10, 13, 10, 2, 13, 2, 3, 13, 3, 11, 13, 11, 6, 13, 6, 7, 13, 7, 12, 2, 11, 3, 13, 10, 6, 13, 6, 7, 13, 7, 12, 13, 12, 4, 13, 4, 1, 13, 1, 9, 13, 9, 8, 13, 8, 5, 13, 5, 10, 4, 9, 1, 13, 8, 12, 13, 12, 3, 13, 3, 2, 13, 2, 10, 13, 10, 5, 13, 5,+ 6, 13, 6, 11, 13, 11, 7, 13, 7, 8, 10, 6, 5, 13, 2, 11, 13, 11, 7, 13, 7, 8, 13, 8, 9, 13, 9, 1, 13, 1, 4, 13, 4, 12, 13, 12, 3, 13, 3, 2, 13, 6, 5, 13, 5, 9, 13, 9, 8, 13, 8, 7, 13, 7, 12, 13, 12, 4, 13, 4, 3, 13, 3, 11, 13, 11, 2, 13, 2, 1, 13, 1, 10, 13, 10, 6, 13, 11, 7, 13, 7, 8, 13, 8, 12, 13, 12, 3, 13, 3, 4, 13, 4, 9, 13, 9, 1, 13, 1, 2, 13, 2, 10, 13, 10, 5, 13, 5, 6, 13, 6, 11, 13, 10, 1, 13, 1, 4, 13, 4, 9, 13, 9, 5, 13, 5, 8, 13, 8, 12, 13, 12, 7, 13, 7, 6, 13, 6, 11, 13, 11, 3, 13, 3,+ 2, 13, 2, 10, 13, 2, 3, 13, 3, 12, 13, 12, 4, 13, 4, 1, 13, 1, 9, 13, 9, 8, 13, 8, 5, 13, 5, 10, 13, 10, 6, 13, 6, 7, 13, 7, 11, 13, 11, 2, 8, 12, 7, 10, 2, 1, 6, 11, 5, 11, 5, 9, 11, 9, 3, 9, 3, 4, 6, 10, 5, 12, 4, 3, 11, 2, 7, 2, 7, 8, 2, 8, 1, 8, 1, 9, 2, 11, 3, 9, 8, 5, 10, 6, 1, 6, 1, 4, 6, 4, 7, 4, 7, 12, 4, 9, 1, 11, 6, 7, 2, 10, 3, 10, 3, 12, 10, 12, 5, 12, 5, 8, 2, 10, 1, 12, 4, 3, 12, 3, 11, 12, 11, 7, 11, 7, 6, 7, 6, 5, 7, 5, 8, 5, 8, 9, 8, 9, 12, 9, 12, 4, 12, 4, 3, 6, 11, 7, 6, 7, 8,+ 6, 8, 5, 8, 5, 9, 5, 9, 1, 5, 1, 10, 1, 10, 2, 10, 2, 6, 2, 6, 11, 9, 8, 5, 2, 10, 1, 2, 1, 4, 2, 4, 3, 4, 3, 12, 3, 12, 7, 3, 7, 11, 7, 11, 6, 11, 6, 2, 6, 2, 10, 6, 11, 7, 9, 8, 5, 9, 5, 10, 9, 10, 1, 10, 1, 2, 1, 2, 3, 1, 3, 4, 4, 3, 12, 4, 12, 9, 12, 9, 8],+ [8, 12, 5, 12, 3, 5, 6, 11, 7, 5, 3, 1, 8, 6, 7, 8, 5, 6, 6, 1, 5, 6, 11, 1, 12, 3, 11, 12, 11, 7, 8, 12, 7, 11, 3, 1, 8, 12, 13, 12, 7, 13, 6, 13, 7, 11, 3, 13, 6, 11, 13, 1, 13, 3, 5, 13, 1, 8, 5, 13, 11, 7, 13, 8, 13, 7, 8, 12, 13, 12, 3, 13, 1, 13, 3, 5, 1, 13, 6, 13, 5, 6, 11, 13, 8, 12, 7, 6, 11, 3, 6, 3, 5, 5, 3, 1],+ [6, 11, 7, 8, 9, 5, 12, 3, 4, 6, 11, 7, 8, 12, 3, 8, 3, 5, 4, 5, 3, 4, 9, 5, 8, 9, 5, 6, 12, 7, 6, 4, 12, 6, 11, 3, 6, 3, 4, 12, 3, 4, 6, 9, 5, 6, 11, 9, 11, 8, 9, 11, 7, 8, 6, 11, 13, 11, 3, 13, 4, 13, 3, 4, 9, 13, 9, 5, 13, 8, 13, 5, 8, 12, 13, 12, 7, 13, 6, 13, 7, 6, 11, 13, 6, 5, 13, 9, 5, 13, 4, 9, 13, 4, 13, 3, 12, 13, 3, 8, 12, 13, 8, 13, 7, 11, 7, 13, 4, 13, 3, 11, 3, 13, 6, 11, 13, 6, 13, 5, 9, 5, 13, 8, 9, 13, 8, 13, 7, 12, 7, 13, 12, 13, 4, 6, 9, 5, 6, 3, 9, 6, 11, 3, 4, 9, 3, 8, 12,+ 7, 6, 7, 5, 8, 5, 7, 8, 9, 5, 8, 4, 9, 8, 12, 4, 12, 3, 4, 12, 7, 3, 11, 3, 7, 6, 11, 7],+ [8, 4, 7, 4, 3, 7, 6, 10, 5, 8, 4, 5, 4, 10, 5, 4, 3, 10, 6, 10, 3, 6, 3, 7, 8, 7, 6, 8, 6, 5, 5, 6, 10, 8, 4, 5, 4, 10, 5, 4, 3, 10, 6, 10, 3, 6, 3, 7],+ [6, 10, 7, 10, 1, 7, 8, 9, 5, 7, 1, 3, 6, 8, 5, 6, 7, 8, 8, 3, 7, 8, 9, 3, 10, 1, 9, 10, 9, 5, 6, 10, 5, 9, 1, 3, 6, 10, 13, 10, 5, 13, 8, 13, 5, 9, 1, 13, 8, 9, 13, 3, 13, 1, 7, 13, 3, 6, 7, 13, 9, 5, 13, 6, 13, 5, 6, 10, 13, 10, 1, 13, 3, 13, 1, 7, 3, 13, 8, 13, 7, 8, 9, 13, 6, 10, 5, 8, 9, 1, 8, 1, 7, 7, 1, 3],+ [6, 2, 7, 5, 8, 1, 8, 4, 1, 7, 2, 3, 6, 8, 7, 6, 5, 8, 8, 3, 7, 8, 4, 3, 2, 1, 3, 1, 4, 3, 6, 1, 5, 6, 2, 1, 6, 13, 5, 6, 2, 13, 2, 3, 13, 7, 13, 3, 8, 13, 7, 8, 4, 13, 1, 13, 4, 5, 13, 1, 2, 1, 13, 6, 2, 13, 6, 13, 7, 7, 13, 3, 4, 3, 13, 8, 4, 13, 5, 8, 13, 5, 13, 1, 6, 2, 5, 5, 2, 1, 8, 3, 7, 8, 4, 3],+ [7, 6, 3, 3, 6, 2, 5, 8, 9, 7, 8, 3, 3, 8, 9, 3, 9, 2, 5, 2, 9, 5, 6, 2, 7, 5, 6, 7, 8, 5, 8, 9, 5, 7, 8, 3, 3, 8, 9, 3, 9, 2, 5, 2, 9, 5, 6, 2],+ [10, 5, 2, 5, 8, 2, 11, 7, 6, 2, 8, 4, 10, 11, 6, 10, 2, 11, 11, 4, 2, 11, 7, 4, 5, 8, 7, 5, 7, 6, 10, 5, 6, 7, 8, 4, 10, 5, 13, 5, 6, 13, 11, 13, 6, 7, 8, 13, 11, 7, 13, 4, 13, 8, 2, 13, 4, 10, 2, 13, 7, 6, 13, 10, 13, 6, 10, 5, 13, 5, 8, 13, 4, 13, 8, 2, 4, 13, 11, 13, 2, 11, 7, 13, 10, 5, 6, 11, 7, 8, 11, 8, 2, 2, 8, 4],+ [8, 9, 5, 6, 11, 7, 10, 1, 2, 8, 9, 5, 6, 10, 1, 6, 1, 7, 2, 7, 1, 2, 11, 7, 6, 11, 7, 8, 10, 5, 8, 2, 10, 8, 9, 1, 8, 1, 2, 10, 1, 2, 8, 11, 7, 8, 9, 11, 9, 6, 11, 9, 5, 6, 8, 9, 13, 9, 1, 13, 2, 13, 1, 2, 11, 13, 11, 7, 13, 6, 13, 7, 6, 10, 13, 10, 5, 13, 8, 13, 5, 8, 9, 13, 8, 7, 13, 11, 7, 13, 2, 11, 13, 2, 13, 1, 10, 13, 1, 6, 10, 13, 6, 13, 5, 9, 5, 13, 2, 13, 1, 9, 1, 13, 8, 9, 13, 8, 13, 7, 11, 7, 13, 6, 11, 13, 6, 13, 5, 10, 5, 13, 10, 13, 2, 8, 11, 7, 8, 1, 11, 8, 9, 1, 2, 11, 1, 6, 10,+ 5, 8, 5, 7, 6, 7, 5, 6, 11, 7, 6, 2, 11, 6, 10, 2, 10, 1, 2, 10, 5, 1, 9, 1, 5, 8, 9, 5],+ [5, 8, 1, 1, 8, 4, 7, 6, 11, 5, 6, 1, 1, 6, 11, 1, 11, 4, 7, 4, 11, 7, 8, 4, 5, 7, 8, 5, 6, 7, 6, 11, 7, 5, 6, 1, 1, 6, 11, 1, 11, 4, 7, 4, 11, 7, 8, 4],+ [7, 6, 11, 5, 8, 9, 7, 8, 11, 11, 8, 9, 11, 9, 5, 11, 5, 6],+ [0],+ [0],+ [0],+ [0],+ [6, 10, 7, 7, 10, 12, 2, 11, 3, 10, 9, 12, 6, 11, 2, 6, 2, 10, 2, 10, 9, 2, 9, 3, 7, 3, 12, 7, 11, 3, 6, 11, 7, 3, 9, 12, 6, 13, 7, 7, 13, 11, 2, 11, 13, 3, 13, 12, 2, 13, 3, 9, 12, 13, 10, 9, 13, 6, 13, 10, 3, 13, 11, 6, 11, 13, 6, 13, 7, 7, 13, 12, 9, 12, 13, 10, 13, 9, 2, 10, 13, 2, 13, 3, 6, 11, 7, 2, 12, 3, 2, 10, 12, 10, 9, 12],+ [4, 12, 3, 2, 10, 1, 11, 7, 6, 4, 12, 3, 2, 11, 7, 2, 7, 1, 6, 1, 7, 6, 10, 1, 2, 10, 1, 4, 11, 3, 4, 6, 11, 4, 12, 7, 4, 7, 6, 11, 7, 6, 4, 10, 1, 4, 12, 10, 12, 2, 10, 12, 3, 2, 4, 12, 13, 12, 7, 13, 6, 13, 7, 6, 10, 13, 10, 1, 13, 2, 13, 1, 2, 11, 13, 11, 3, 13, 4, 13, 3, 4, 12, 13, 4, 1, 13, 10, 1, 13, 6, 10, 13, 6, 13, 7, 11, 13, 7, 2, 11, 13, 2, 13, 3, 12, 3, 13, 6, 13, 7, 12, 7, 13, 4, 12, 13, 4, 13, 1, 10, 1, 13, 2, 10, 13, 2, 13, 3, 11, 3, 13, 11, 13, 6, 4, 10, 1, 4, 7, 10, 4, 12, 7, 6,+ 10, 7, 2, 11, 3, 4, 3, 1, 2, 1, 3, 2, 10, 1, 2, 6, 10, 2, 11, 6, 11, 7, 6, 11, 3, 7, 12, 7, 3, 4, 12, 3],+ [12, 3, 9, 9, 3, 1, 11, 7, 6, 12, 7, 9, 9, 7, 6, 9, 6, 1, 11, 1, 6, 11, 3, 1, 12, 11, 3, 12, 7, 11, 7, 6, 11, 12, 7, 9, 9, 7, 6, 9, 6, 1, 11, 1, 6, 11, 3, 1],+ [12, 3, 4, 11, 7, 6, 12, 7, 4, 4, 7, 6, 4, 6, 11, 4, 11, 3],+ [0],+ [0],+ [2, 3, 6, 6, 3, 7, 4, 1, 9, 2, 1, 6, 6, 1, 9, 6, 9, 7, 4, 7, 9, 4, 3, 7, 2, 4, 3, 2, 1, 4, 1, 9, 4, 2, 1, 6, 6, 1, 9, 6, 9, 7, 4, 7, 9, 4, 3, 7],+ [0],+ [2, 10, 4, 4, 10, 9, 6, 11, 7, 2, 11, 4, 4, 11, 7, 4, 7, 9, 6, 9, 7, 6, 10, 9, 2, 6, 10, 2, 11, 6, 11, 7, 6, 2, 11, 4, 4, 11, 7, 4, 7, 9, 6, 9, 7, 6, 10, 9],+ [6, 11, 7, 2, 10, 1, 6, 10, 7, 7, 10, 1, 7, 1, 2, 7, 2, 11],+ [6, 11, 7, 1, 9, 4, 6, 11, 1, 1, 11, 4, 7, 4, 11, 6, 9, 7, 6, 1, 9, 7, 9, 4],+ [0],+ [0],+ [12, 11, 8, 11, 6, 8, 9, 1, 4, 12, 11, 4, 11, 1, 4, 11, 6, 1, 9, 1, 6, 9, 6, 8, 12, 8, 9, 12, 9, 4, 4, 9, 1, 12, 11, 4, 11, 1, 4, 11, 6, 1, 9, 1, 6, 9, 6, 8],+ [6, 8, 11, 8, 12, 11, 2, 1, 10, 6, 8, 10, 8, 1, 10, 8, 12, 1, 2, 1, 12, 2, 12, 11, 6, 11, 2, 6, 2, 10, 10, 2, 1, 6, 8, 10, 8, 1, 10, 8, 12, 1, 2, 1, 12, 2, 12, 11],+ [2, 4, 11, 10, 6, 9, 6, 8, 9, 11, 4, 12, 2, 6, 11, 2, 10, 6, 6, 12, 11, 6, 8, 12, 4, 9, 12, 9, 8, 12, 2, 9, 10, 2, 4, 9, 2, 13, 10, 2, 4, 13, 4, 12, 13, 11, 13, 12, 6, 13, 11, 6, 8, 13, 9, 13, 8, 10, 13, 9, 4, 9, 13, 2, 4, 13, 2, 13, 11, 11, 13, 12, 8, 12, 13, 6, 8, 13, 10, 6, 13, 10, 13, 9, 2, 4, 10, 10, 4, 9, 6, 12, 11, 6, 8, 12],+ [0],+ [9, 1, 8, 1, 2, 8, 12, 3, 4, 8, 2, 6, 9, 12, 4, 9, 8, 12, 12, 6, 8, 12, 3, 6, 1, 2, 3, 1, 3, 4, 9, 1, 4, 3, 2, 6, 9, 1, 13, 1, 4, 13, 12, 13, 4, 3, 2, 13, 12, 3, 13, 6, 13, 2, 8, 13, 6, 9, 8, 13, 3, 4, 13, 9, 13, 4, 9, 1, 13, 1, 2, 13, 6, 13, 2, 8, 6, 13, 12, 13, 8, 12, 3, 13, 9, 1, 4, 12, 3, 2, 12, 2, 8, 8, 2, 6],+ [0],+ [8, 9, 6, 6, 9, 10, 4, 12, 3, 8, 12, 6, 6, 12, 3, 6, 3, 10, 4, 10, 3, 4, 9, 10, 8, 4, 9, 8, 12, 4, 12, 3, 4, 8, 12, 6, 6, 12, 3, 6, 3, 10, 4, 10, 3, 4, 9, 10],+ [0],+ [0],+ [1, 10, 4, 10, 6, 4, 3, 11, 2, 4, 6, 8, 1, 3, 2, 1, 4, 3, 3, 8, 4, 3, 11, 8, 10, 6, 11, 10, 11, 2, 1, 10, 2, 11, 6, 8, 1, 10, 13, 10, 2, 13, 3, 13, 2, 11, 6, 13, 3, 11, 13, 8, 13, 6, 4, 13, 8, 1, 4, 13, 11, 2, 13, 1, 13, 2, 1, 10, 13, 10, 6, 13, 8, 13, 6, 4, 8, 13, 3, 13, 4, 3, 11, 13, 1, 10, 2, 3, 11, 6, 3, 6, 4, 4, 6, 8],+ [10, 6, 9, 9, 6, 8, 11, 2, 3, 10, 2, 9, 9, 2, 3, 9, 3, 8, 11, 8, 3, 11, 6, 8, 10, 11, 6, 10, 2, 11, 2, 3, 11, 10, 2, 9, 9, 2, 3, 9, 3, 8, 11, 8, 3, 11, 6, 8],+ [0],+ [0],+ [0],+ [0],+ [0],+ [0],+ [2, 1, 11, 1, 9, 11, 6, 5, 10, 11, 9, 12, 2, 6, 10, 2, 11, 6, 6, 12, 11, 6, 5, 12, 1, 9, 5, 1, 5, 10, 2, 1, 10, 5, 9, 12, 2, 1, 13, 1, 10, 13, 6, 13, 10, 5, 9, 13, 6, 5, 13, 12, 13, 9, 11, 13, 12, 2, 11, 13, 5, 10, 13, 2, 13, 10, 2, 1, 13, 1, 9, 13, 12, 13, 9, 11, 12, 13, 6, 13, 11, 6, 5, 13, 2, 1, 10, 6, 5, 9, 6, 9, 11, 11, 9, 12],+ [11, 2, 12, 12, 2, 4, 10, 6, 5, 11, 6, 12, 12, 6, 5, 12, 5, 4, 10, 4, 5, 10, 2, 4, 11, 10, 2, 11, 6, 10, 6, 5, 10, 11, 6, 12, 12, 6, 5, 12, 5, 4, 10, 4, 5, 10, 2, 4],+ [0],+ [1, 2, 5, 5, 2, 6, 3, 4, 12, 1, 4, 5, 5, 4, 12, 5, 12, 6, 3, 6, 12, 3, 2, 6, 1, 3, 2, 1, 4, 3, 4, 12, 3, 1, 4, 5, 5, 4, 12, 5, 12, 6, 3, 6, 12, 3, 2, 6],+ [1, 9, 3, 3, 9, 12, 5, 10, 6, 1, 10, 3, 3, 10, 6, 3, 6, 12, 5, 12, 6, 5, 9, 12, 1, 5, 9, 1, 10, 5, 10, 6, 5, 1, 10, 3, 3, 10, 6, 3, 6, 12, 5, 12, 6, 5, 9, 12],+ [6, 5, 10, 12, 3, 4, 6, 5, 12, 12, 5, 4, 10, 4, 5, 6, 3, 10, 6, 12, 3, 10, 3, 4],+ [0],+ [0],+ [6, 5, 10, 2, 3, 11, 1, 9, 4, 6, 5, 10, 2, 1, 9, 2, 9, 11, 4, 11, 9, 4, 3, 11, 2, 3, 11, 6, 1, 10, 6, 4, 1, 6, 5, 9, 6, 9, 4, 1, 9, 4, 6, 3, 11, 6, 5, 3, 5, 2, 3, 5, 10, 2, 6, 5, 13, 5, 9, 13, 4, 13, 9, 4, 3, 13, 3, 11, 13, 2, 13, 11, 2, 1, 13, 1, 10, 13, 6, 13, 10, 6, 5, 13, 6, 11, 13, 3, 11, 13, 4, 3, 13, 4, 13, 9, 1, 13, 9, 2, 1, 13, 2, 13, 10, 5, 10, 13, 4, 13, 9, 5, 9, 13, 6, 5, 13, 6, 13, 11, 3, 11, 13, 2, 3, 13, 2, 13, 10, 1, 10, 13, 1, 13, 4, 6, 3, 11, 6, 9, 3, 6, 5, 9, 4, 3, 9, 2, 1, 10,+ 6, 10, 11, 2, 11, 10, 2, 3, 11, 2, 4, 3, 2, 1, 4, 1, 9, 4, 1, 10, 9, 5, 9, 10, 6, 5, 10],+ [10, 6, 5, 11, 2, 3, 10, 2, 5, 5, 2, 3, 5, 3, 11, 5, 11, 6],+ [0],+ [0],+ [5, 10, 6, 1, 9, 4, 5, 9, 6, 6, 9, 4, 6, 4, 1, 6, 1, 10],+ [0],+ [0],+ [8, 12, 5, 5, 12, 10, 4, 9, 1, 12, 11, 10, 8, 9, 4, 8, 4, 12, 4, 12, 11, 4, 11, 1, 5, 1, 10, 5, 9, 1, 8, 9, 5, 1, 11, 10, 8, 13, 5, 5, 13, 9, 4, 9, 13, 1, 13, 10, 4, 13, 1, 11, 10, 13, 12, 11, 13, 8, 13, 12, 1, 13, 9, 8, 9, 13, 8, 13, 5, 5, 13, 10, 11, 10, 13, 12, 13, 11, 4, 12, 13, 4, 13, 1, 8, 9, 5, 4, 10, 1, 4, 12, 10, 12, 11, 10],+ [0],+ [4, 12, 2, 2, 12, 11, 8, 9, 5, 4, 9, 2, 2, 9, 5, 2, 5, 11, 8, 11, 5, 8, 12, 11, 4, 8, 12, 4, 9, 8, 9, 5, 8, 4, 9, 2, 2, 9, 5, 2, 5, 11, 8, 11, 5, 8, 12, 11],+ [0],+ [2, 10, 1, 4, 12, 3, 9, 5, 8, 2, 10, 1, 4, 9, 5, 4, 5, 3, 8, 3, 5, 8, 12, 3, 4, 12, 3, 2, 9, 1, 2, 8, 9, 2, 10, 5, 2, 5, 8, 9, 5, 8, 2, 12, 3, 2, 10, 12, 10, 4, 12, 10, 1, 4, 2, 10, 13, 10, 5, 13, 8, 13, 5, 8, 12, 13, 12, 3, 13, 4, 13, 3, 4, 9, 13, 9, 1, 13, 2, 13, 1, 2, 10, 13, 2, 3, 13, 12, 3, 13, 8, 12, 13, 8, 13, 5, 9, 13, 5, 4, 9, 13, 4, 13, 1, 10, 1, 13, 8, 13, 5, 10, 5, 13, 2, 10, 13, 2, 13, 3, 12, 3, 13, 4, 12, 13, 4, 13, 1, 9, 1, 13, 9, 13, 8, 2, 12, 3, 2, 5, 12, 2, 10, 5, 8, 12, 5, 4,+ 9, 1, 2, 1, 3, 4, 3, 1, 4, 12, 3, 4, 8, 12, 4, 9, 8, 9, 5, 8, 9, 1, 5, 10, 5, 1, 2, 10, 1],+ [0],+ [8, 9, 5, 4, 12, 3, 8, 12, 5, 5, 12, 3, 5, 3, 4, 5, 4, 9],+ [0],+ [10, 1, 11, 11, 1, 3, 9, 5, 8, 10, 5, 11, 11, 5, 8, 11, 8, 3, 9, 3, 8, 9, 1, 3, 10, 9, 1, 10, 5, 9, 5, 8, 9, 10, 5, 11, 11, 5, 8, 11, 8, 3, 9, 3, 8, 9, 1, 3],+ [4, 1, 8, 8, 1, 5, 2, 3, 11, 4, 3, 8, 8, 3, 11, 8, 11, 5, 2, 5, 11, 2, 1, 5, 4, 2, 1, 4, 3, 2, 3, 11, 2, 4, 3, 8, 8, 3, 11, 8, 11, 5, 2, 5, 11, 2, 1, 5],+ [2, 3, 11, 9, 5, 8, 2, 3, 9, 9, 3, 8, 11, 8, 3, 2, 5, 11, 2, 9, 5, 11, 5, 8],+ [0],+ [10, 1, 2, 9, 5, 8, 10, 5, 2, 2, 5, 8, 2, 8, 9, 2, 9, 1],+ [0],+ [0],+ [0],+ [0],+ [0],+ [0],+ [0],+ [1, 2, 10, 3, 4, 12, 1, 4, 10, 10, 4, 12, 10, 12, 3, 10, 3, 2],+ [0],+ [0],+ [0],+ [0],+ [2, 3, 11, 4, 1, 9, 2, 1, 11, 11, 1, 9, 11, 9, 4, 11, 4, 3],+ [0],+ [0],+ [0],+ [0]+ ] + )++specialName :: [Int]+specialName = [3, 4, 6, 7, 10, 12, 13]++specialNface, specialNedge :: UV.Vector Int+specialNface = UV.fromList [1, 1, 2, 4, 3, 3, 7]+specialNedge = UV.fromList [18, 24, 48, 177, 96, 96, 816]++specialInd :: V.Vector (UV.Vector Int)+specialInd = V.fromList + (map + UV.fromList+ [+ [0, 1],+ [0, 1],+ [0, 2, 1, 3],+ [0, 8, 4, 12, 2, 10, 1, 9, 6, 14, 5, 13, 3, 11, 15, 7],+ [0, 4, 1, 5, 2, 6, 3, 7],+ [0, 4, 2, 6, 1, 5, 3, 7],+ [0, 1, 2, 4, 8, 16, 32, 3, 9, 17, 33, 6, 18, 34, 12, 20, 36, 24, 40, 35, 25, 22, 44, 19, 41, 38, 28, 83, 105, 102, 92]+ ] + )++specialPos :: V.Vector (V.Vector (UV.Vector Int))+specialPos = V.fromList+ (map+ (V.fromList . map UV.fromList)+ [ [[0 .. 5], [6 .. 17]]+ , [[0 .. 5], [6 .. 23]]+ , [[0 .. 8], [9 .. 32], [33 .. 47], [33 .. 47]]+ , [ [0 .. 8]+ , [0 .. 8]+ , [9 .. 23]+ , [9 .. 23]+ , [24 .. 38]+ , [24 .. 38]+ , [39 .. 53]+ , [39 .. 53]+ , [54 .. 80]+ , [54 .. 80]+ , [81 .. 107]+ , [81 .. 107]+ , [108 .. 134]+ , [108 .. 134]+ , [135 .. 149]+ , [150 .. 176]+ ]+ , [ [0 .. 11]+ , [12 .. 35]+ , [36 .. 59]+ , [36 .. 59]+ , [60 .. 83]+ , [60 .. 83]+ , [84 .. 95]+ , [84 .. 95]+ ]+ , [ [0 .. 11]+ , [12 .. 35]+ , [36 .. 59]+ , [36 .. 59]+ , [60 .. 83]+ , [60 .. 83]+ , [84 .. 95]+ , [84 .. 95]+ ]+ , [ [0 .. 11]+ , [12 .. 29]+ , [30 .. 47]+ , [48 .. 65]+ , [66 .. 83]+ , [84 .. 101]+ , [102 .. 119]+ , [120 .. 149]+ , [150 .. 179]+ , [180 .. 209]+ , [210 .. 239]+ , [240 .. 269]+ , [270 .. 299]+ , [300 .. 329]+ , [330 .. 359]+ , [360 .. 389]+ , [390 .. 419]+ , [420 .. 449]+ , [450 .. 479]+ , [480 .. 515]+ , [516 .. 551]+ , [552 .. 587]+ , [588 .. 623]+ , [624 .. 641]+ , [642 .. 659]+ , [660 .. 677]+ , [678 .. 695]+ , [696 .. 725]+ , [726 .. 755]+ , [756 .. 785]+ , [786 .. 815]+ ]+ ]+ )++crf :: UV.Vector Int+crf = UV.fromList+ [1, 2, 2, 3, 2, 4, 3, 6, 2, 3, 4, 6, 3, 6, 6, 9, 2, 3, 4, 6,+ 5, 7, 7, 12, 4, 6, 8, 10, 7, 15, 13, 6, 2, 4, 3, 6, 4, 8, 6,+ 10, 5, 7, 7, 15, 7, 13, 12, 6, 3, 6, 6, 9, 7, 13, 15, 6, 7, 12,+ 13, 6, 11, 7, 7, 3, 2, 5, 4, 7, 3, 7, 6, 15, 4, 7, 8, 13, 6,+ 12, 10, 6, 4, 7, 8, 13, 7, 11, 13, 7, 8, 13, 14, 8, 13, 7, 8,+ 4, 3, 7, 6, 12, 6, 13, 9, 6, 7, 11, 13, 7, 15, 7, 6, 3, 6, 15,+ 10, 6, 12, 7, 6, 3, 13, 7, 8, 4, 7, 5, 4, 2, 2, 4, 5, 7, 4, 8,+ 7, 13, 3, 6, 7, 12, 6, 10, 15, 6, 3, 6, 7, 15, 7, 13, 11, 7,+ 6, 9, 13, 6, 12, 6, 7, 3, 4, 8, 7, 13, 8, 14, 13, 8, 7, 13, 11,+ 7, 13, 8, 7, 4, 6, 10, 12, 6, 13, 8, 7, 4, 15, 6, 7, 3, 7, 4,+ 5, 2, 3, 7, 7, 11, 6, 13, 12, 7, 6, 15, 13, 7, 9, 6, 6, 3, 6,+ 12, 13, 7, 15, 7, 7, 5, 10, 6, 8, 4, 6, 3, 4, 2, 6, 13, 15, 7,+ 10, 8, 6, 4, 12, 7, 7, 5, 6, 4, 3, 2, 9, 6, 6, 3, 6, 4, 3, 2,+ 6, 3, 4, 2, 3, 2, 2, 1]
+ src/MarchingCubes/Utils.hs view
@@ -0,0 +1,102 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE FlexibleContexts #-}+module MarchingCubes.Utils+ ( module MarchingCubes.Utils+ ) where+import Data.Array.Unboxed ( (!)+ , IArray(..)+ , UArray+ )+import Data.List ( transpose )+import Data.Matrix ( (<|>)+ , Matrix(..)+ , colVector+ , getElem+ , mapPos+ , matrix+ , toLists+ )+import qualified Data.Matrix as M+import Data.Sequence ( (><)+ , Seq+ , (|>)+ )+import qualified Data.Sequence as S+import qualified Data.Vector as V+import Data.Vector.Unboxed ( Vector )+import qualified Data.Vector.Unboxed as UV++levelMatrix :: Real a => Matrix a -> a -> Bool -> Matrix Int+levelMatrix mtrx level strict = mapPos (\_ x -> if lt x then 1 else 0) mtrx+ where lt = if strict then (<) level else (<=) level++arrayToMatrix :: IArray UArray a => UArray (Int, Int, Int) a -> Int -> Matrix a+arrayToMatrix arr k = matrix (nx + 1)+ (ny + 1)+ (\(i, j) -> arr ! (i - 1, j - 1, k))+ where (_, (nx, ny, _)) = bounds arr++whichIndicesAndItems :: Matrix Int -> Seq (Int, Int)+whichIndicesAndItems mtrx = go 1 S.empty+ where+ m = nrows mtrx + 1+ n = ncols mtrx + 1+ go :: Int -> Seq (Int, Int) -> Seq (Int, Int)+ go j !out | j == n = out+ | otherwise = go (j + 1) (inner 1 j out)+ inner i !j !out | i == m = out+ | otherwise = inner (i + 1) j out'+ where+ out' =+ let x = getElem i j mtrx+ in if x > 0 && x < 255+ then out |> ((j - 1) * (m - 1) + i - 1, x)+ else out++kro1 :: Matrix Int -> Int -> Matrix Int+kro1 mtrx n = matrix p ny f+ where+ nx = nrows mtrx+ ny = ncols mtrx+ p = nx * n + 1+ f (i, j) = if i < p then getElem ((i - 1) `mod` nx + 1) j mtrx else 0++kro2 :: Matrix Int -> Int -> Matrix Int+kro2 mtrx n = matrix p ny f+ where+ nx = nrows mtrx+ ny = ncols mtrx+ p = nx * n + 1+ replicates = foldr ((><) . S.replicate n) S.empty [1 .. nx] :: Seq Int+ f (i, j) = if i < p then getElem (S.index replicates (i - 1)) j mtrx else 0++replicateEach :: [a] -> [Int] -> Seq a+replicateEach list counts = foldr (><) S.empty sequences+ where sequences = zipWith S.replicate counts list++replicateEach' :: [a] -> Int -> Seq a+replicateEach' list n = foldr ((><) . S.replicate n) S.empty list++vector2matrix :: [a] -> Int -> Matrix a+vector2matrix list ny = M.fromList (length list `div` ny) ny list++cbind :: Matrix a -> [a] -> [a] -> Matrix a+cbind mtrx col1 col2 = mtrx <|> col1' <|> col2'+ where+ col1' = colVector (V.fromList col1)+ col2' = colVector (V.fromList col2)++subMatrix :: Matrix a -> [Int] -> Vector Int -> Matrix a+subMatrix mtrx rows cols = matrix+ (length rows)+ (UV.length cols)+ (\(i, j) -> getElem (rows !! (i - 1) + 1) (cols UV.! (j - 1) + 1) mtrx)++matrix2listMinusFirstColumn :: Matrix a -> [a]+matrix2listMinusFirstColumn mtrx =+ concat $ transpose $ tail (toLists $ M.transpose mtrx)++jthColumn :: Vector Int -> Int -> Int -> Vector Int+jthColumn vec ncol j = UV.map (\i -> vec UV.! (i * ncol + j))+ (UV.enumFromN 0 nrow)+ where nrow = UV.length vec `div` ncol