type Triangle = (Int, Int, Int)
type Segment = (Int, Int, Int)

startTriangle :: Triangle
startTriangle = (1, 32, 32)

splitOneTriangle :: Triangle -> [Triangle]
splitOneTriangle (row, column, height) = 
  [ (row, column, halfHeight)
  , (row + halfHeight, column - halfHeight, halfHeight)
  , (row + halfHeight, column + halfHeight, halfHeight)
  ]
  where halfHeight = height `div` 2

splitTriangles :: [Triangle] -> [Triangle]
splitTriangles ts = ts >>= splitOneTriangle

triangleSegments :: Triangle -> [Segment]
triangleSegments (row, column, height) =
  [(row + i, column - i, column + i) | i <- [0 .. height - 1]]

inSegment :: (Int, Int) -> Segment -> Bool
inSegment (cellRow, cellColumn) (segmentRow, leftSegmentColumn, rightSegmentColumn) =
  segmentRow == cellRow && 
  leftSegmentColumn <= cellColumn && 
  cellColumn <= rightSegmentColumn

inTriangle :: (Int, Int) -> Triangle -> Bool
inTriangle cell triangle = 
  not $ null $ filter (inSegment cell) $ triangleSegments triangle

inAnyTriangle :: (Int, Int) -> [Triangle] -> Bool
inAnyTriangle cell triangles = any (inTriangle cell) triangles

getCellChar :: (Int, Int) -> [Triangle] -> Char
getCellChar cell triangles
  | inAnyTriangle cell triangles = '1'
  | otherwise                    = '_'

renderSierpinski :: Int -> String
renderSierpinski n = unlines $ map (\row -> [getCellChar (row, column) triangles | column <- [1 .. 63]]) [1 .. 32]
  where triangles = head $ drop n $ iterate splitTriangles [startTriangle]

main = interact $ renderSierpinski . read