class Node
  attr_accessor :value, :left, :right
  def initialize(val)
    @value = val   # ノードが保持する値
    @left = nil    # 左側のノード
    @right = nil   # 右側のノード
  end
 
  # 描画に必要な情報を計算 (内部用)
  def render_info(canvas, margin, x, y)
    # 左のノードがあれば、そのノード以下の木の横幅が返ってくる
    x = @left.render_info(canvas, margin, x, y + 1) + margin if @left
 
    # このノードの分の描画に必要な情報を追加
    canvas << [x, y, self]
 
    # このノードの分の描画に必要な情報を追加
    x += @value.to_s.size
    x = @right.render_info(canvas, margin, x + margin, y + 1) if @right
 
    # 呼び出した親のために横幅を返す
    x
  end
  protected :render_info
 
  # render_infoで描画情報を集めて返す (外部用)
  def render(margin)
    canvas = []
    render_info(canvas, margin, 0, 0)
    canvas
  end
end
 
 
def print_canvas(canvas)
  canvas = canvas.sort_by {|x, y, *| [y, x] }
 
  last_x = 0
  last_y = 0
 
  canvas.each do |x, y, node|
      text = node.value.to_s
 
    if y != last_y
      last_x = 0
      puts
    end
 
    print " " * (x - last_x)
    print text
 
    last_x = x + text.to_s.size
    last_y = y
  end
  puts
end
 
def print_canvas2(canvas)
  canvas = canvas.sort_by {|x, y, *| [y, x] }
 
  last_x = 0
  last_y = 0
 
  canvas.each do |x, y, node|
    text = node.value.to_s
 
    if y != last_y
      last_x = 0
      puts
    end
 
    if node.left
      ileft = canvas.index {|nx, ny, *| y + 1 == ny && x <= nx } - 1
      left_x, * = canvas[ileft]
      left_x_end = left_x + node.left.value.to_s.size
      print " " * (left_x_end - last_x)
      print "_" * (x - left_x_end)
    else
      print " " * (x - last_x)
    end
 
    print text
 
    x += text.to_s.size
 
    if node.right
      iright = canvas.index {|nx, ny, *| y + 1 == ny && x <= nx }
      right_x, * = canvas[iright]
 
      print "_" * (right_x - x)
      x = right_x
    end
 
    last_x = x
    last_y = y
  end
  puts
end
 
def print_canvas3(canvas)
  canvas = canvas.sort_by {|x, y, *| [y, x] }
  canvas_lines = canvas.group_by {|x, y, *| y }.sort.map {|_, line| line }
 
  canvas_lines.each do |line|
    slashes = []
 
    last_x = 0
    line.each do |x, y, node|
      text = node.value.to_s
 
      if node.left
        next_line = canvas_lines[y + 1]
        ileft = next_line.index {|nx, *| x <= nx } - 1
        left_x, * = next_line[ileft]
        left_x_end = left_x + node.left.value.to_s.size
        print " " * (left_x_end - last_x)
        if left_x_end < x
          print " "
          print "_" * (x - left_x_end - 1)
          slashes << [left_x_end, '/']
        end
      else
        print " " * (x - last_x)
      end
 
      print text
 
      x += text.to_s.size
 
      if node.right
        next_line = canvas_lines[y + 1]
        iright = next_line.index {|nx, *| x <= nx }
        right_x, * = next_line[iright]
 
        if x < right_x
          print "_" * (right_x - x - 1)
          print " "
          slashes << [right_x - 1, '\\']
        end
        x = right_x
      end
 
      last_x = x
    end
 
    puts
 
    last_x = 0
    slashes.each do |x, char|
      print " " * (x - last_x)
      print char
      last_x = x + 1
    end
    puts unless slashes.empty?
  end
end
 
# ツリーの宣言を短く書くために定義
def Node(val, left=nil, right=nil)
  node = Node.new(val)
  node.left = left
  node.right = right
  node
end
 
tree = Node(9, Node(4, Node(2), Node(6)), Node(15, Node(12), Node(17)))
print_canvas tree.render(0)
print_canvas2 tree.render(0)
print_canvas2 tree.render(3)
print_canvas3 tree.render(1)
print_canvas3 tree.render(2)
print_canvas3 tree.render(3)
print_canvas3 Node(4, tree, tree).render(0)
print_canvas3 Node(4, tree, tree).render(1)
print_canvas3 Node(4, Node(9, tree, nil), tree).render(2)
print_canvas3 Node(4, tree, tree).render(3)
 

Y2xhc3MgTm9kZQogIGF0dHJfYWNjZXNzb3IgOnZhbHVlLCA6bGVmdCwgOnJpZ2h0CiAgZGVmIGluaXRpYWxpemUodmFsKQogICAgQHZhbHVlID0gdmFsICAgIyDjg47jg7zjg4njgYzkv53mjIHjgZnjgovlgKQKICAgIEBsZWZ0ID0gbmlsICAgICMg5bem5YG044Gu44OO44O844OJCiAgICBAcmlnaHQgPSBuaWwgICAjIOWPs+WBtOOBruODjuODvOODiQogIGVuZAoKICAjIOaPj+eUu+OBq+W/heimgeOBquaDheWgseOCkuioiOeulyAo5YaF6YOo55SoKQogIGRlZiByZW5kZXJfaW5mbyhjYW52YXMsIG1hcmdpbiwgeCwgeSkKICAgICMg5bem44Gu44OO44O844OJ44GM44GC44KM44Gw44CB44Gd44Gu44OO44O844OJ5Lul5LiL44Gu5pyo44Gu5qiq5bmF44GM6L+U44Gj44Gm44GP44KLCiAgICB4ID0gQGxlZnQucmVuZGVyX2luZm8oY2FudmFzLCBtYXJnaW4sIHgsIHkgKyAxKSArIG1hcmdpbiBpZiBAbGVmdAoKICAgICMg44GT44Gu44OO44O844OJ44Gu5YiG44Gu5o+P55S744Gr5b+F6KaB44Gq5oOF5aCx44KS6L+95YqgCiAgICBjYW52YXMgPDwgW3gsIHksIHNlbGZdCgogICAgIyDjgZPjga7jg47jg7zjg4njga7liIbjga7mj4/nlLvjgavlv4XopoHjgarmg4XloLHjgpLov73liqAKICAgIHggKz0gQHZhbHVlLnRvX3Muc2l6ZQogICAgeCA9IEByaWdodC5yZW5kZXJfaW5mbyhjYW52YXMsIG1hcmdpbiwgeCArIG1hcmdpbiwgeSArIDEpIGlmIEByaWdodAoKICAgICMg5ZG844Gz5Ye644GX44Gf6Kaq44Gu44Gf44KB44Gr5qiq5bmF44KS6L+U44GZCiAgICB4CiAgZW5kCiAgcHJvdGVjdGVkIDpyZW5kZXJfaW5mbwoKICAjIHJlbmRlcl9pbmZv44Gn5o+P55S75oOF5aCx44KS6ZuG44KB44Gm6L+U44GZICjlpJbpg6jnlKgpCiAgZGVmIHJlbmRlcihtYXJnaW4pCiAgICBjYW52YXMgPSBbXQogICAgcmVuZGVyX2luZm8oY2FudmFzLCBtYXJnaW4sIDAsIDApCiAgICBjYW52YXMKICBlbmQKZW5kCgoKZGVmIHByaW50X2NhbnZhcyhjYW52YXMpCiAgY2FudmFzID0gY2FudmFzLnNvcnRfYnkge3x4LCB5LCAqfCBbeSwgeF0gfQoKICBsYXN0X3ggPSAwCiAgbGFzdF95ID0gMAoKICBjYW52YXMuZWFjaCBkbyB8eCwgeSwgbm9kZXwKICAgICAgdGV4dCA9IG5vZGUudmFsdWUudG9fcwoKICAgIGlmIHkgIT0gbGFzdF95CiAgICAgIGxhc3RfeCA9IDAKICAgICAgcHV0cwogICAgZW5kCgogICAgcHJpbnQgIiAiICogKHggLSBsYXN0X3gpCiAgICBwcmludCB0ZXh0CgogICAgbGFzdF94ID0geCArIHRleHQudG9fcy5zaXplCiAgICBsYXN0X3kgPSB5CiAgZW5kCiAgcHV0cwplbmQKCmRlZiBwcmludF9jYW52YXMyKGNhbnZhcykKICBjYW52YXMgPSBjYW52YXMuc29ydF9ieSB7fHgsIHksICp8IFt5LCB4XSB9CgogIGxhc3RfeCA9IDAKICBsYXN0X3kgPSAwCgogIGNhbnZhcy5lYWNoIGRvIHx4LCB5LCBub2RlfAogICAgdGV4dCA9IG5vZGUudmFsdWUudG9fcwoKICAgIGlmIHkgIT0gbGFzdF95CiAgICAgIGxhc3RfeCA9IDAKICAgICAgcHV0cwogICAgZW5kCgogICAgaWYgbm9kZS5sZWZ0CiAgICAgIGlsZWZ0ID0gY2FudmFzLmluZGV4IHt8bngsIG55LCAqfCB5ICsgMSA9PSBueSAmJiB4IDw9IG54IH0gLSAxCiAgICAgIGxlZnRfeCwgKiA9IGNhbnZhc1tpbGVmdF0KICAgICAgbGVmdF94X2VuZCA9IGxlZnRfeCArIG5vZGUubGVmdC52YWx1ZS50b19zLnNpemUKICAgICAgcHJpbnQgIiAiICogKGxlZnRfeF9lbmQgLSBsYXN0X3gpCiAgICAgIHByaW50ICJfIiAqICh4IC0gbGVmdF94X2VuZCkKICAgIGVsc2UKICAgICAgcHJpbnQgIiAiICogKHggLSBsYXN0X3gpCiAgICBlbmQKCiAgICBwcmludCB0ZXh0CgogICAgeCArPSB0ZXh0LnRvX3Muc2l6ZQoKICAgIGlmIG5vZGUucmlnaHQKICAgICAgaXJpZ2h0ID0gY2FudmFzLmluZGV4IHt8bngsIG55LCAqfCB5ICsgMSA9PSBueSAmJiB4IDw9IG54IH0KICAgICAgcmlnaHRfeCwgKiA9IGNhbnZhc1tpcmlnaHRdCgogICAgICBwcmludCAiXyIgKiAocmlnaHRfeCAtIHgpCiAgICAgIHggPSByaWdodF94CiAgICBlbmQKCiAgICBsYXN0X3ggPSB4CiAgICBsYXN0X3kgPSB5CiAgZW5kCiAgcHV0cwplbmQKCmRlZiBwcmludF9jYW52YXMzKGNhbnZhcykKICBjYW52YXMgPSBjYW52YXMuc29ydF9ieSB7fHgsIHksICp8IFt5LCB4XSB9CiAgY2FudmFzX2xpbmVzID0gY2FudmFzLmdyb3VwX2J5IHt8eCwgeSwgKnwgeSB9LnNvcnQubWFwIHt8XywgbGluZXwgbGluZSB9CgogIGNhbnZhc19saW5lcy5lYWNoIGRvIHxsaW5lfAogICAgc2xhc2hlcyA9IFtdCgogICAgbGFzdF94ID0gMAogICAgbGluZS5lYWNoIGRvIHx4LCB5LCBub2RlfAogICAgICB0ZXh0ID0gbm9kZS52YWx1ZS50b19zCgogICAgICBpZiBub2RlLmxlZnQKICAgICAgICBuZXh0X2xpbmUgPSBjYW52YXNfbGluZXNbeSArIDFdCiAgICAgICAgaWxlZnQgPSBuZXh0X2xpbmUuaW5kZXgge3xueCwgKnwgeCA8PSBueCB9IC0gMQogICAgICAgIGxlZnRfeCwgKiA9IG5leHRfbGluZVtpbGVmdF0KICAgICAgICBsZWZ0X3hfZW5kID0gbGVmdF94ICsgbm9kZS5sZWZ0LnZhbHVlLnRvX3Muc2l6ZQogICAgICAgIHByaW50ICIgIiAqIChsZWZ0X3hfZW5kIC0gbGFzdF94KQogICAgICAgIGlmIGxlZnRfeF9lbmQgPCB4CiAgICAgICAgICBwcmludCAiICIKICAgICAgICAgIHByaW50ICJfIiAqICh4IC0gbGVmdF94X2VuZCAtIDEpCiAgICAgICAgICBzbGFzaGVzIDw8IFtsZWZ0X3hfZW5kLCAnLyddCiAgICAgICAgZW5kCiAgICAgIGVsc2UKICAgICAgICBwcmludCAiICIgKiAoeCAtIGxhc3RfeCkKICAgICAgZW5kCgogICAgICBwcmludCB0ZXh0CgogICAgICB4ICs9IHRleHQudG9fcy5zaXplCgogICAgICBpZiBub2RlLnJpZ2h0CiAgICAgICAgbmV4dF9saW5lID0gY2FudmFzX2xpbmVzW3kgKyAxXQogICAgICAgIGlyaWdodCA9IG5leHRfbGluZS5pbmRleCB7fG54LCAqfCB4IDw9IG54IH0KICAgICAgICByaWdodF94LCAqID0gbmV4dF9saW5lW2lyaWdodF0KCiAgICAgICAgaWYgeCA8IHJpZ2h0X3gKICAgICAgICAgIHByaW50ICJfIiAqIChyaWdodF94IC0geCAtIDEpCiAgICAgICAgICBwcmludCAiICIKICAgICAgICAgIHNsYXNoZXMgPDwgW3JpZ2h0X3ggLSAxLCAnXFwnXQogICAgICAgIGVuZAogICAgICAgIHggPSByaWdodF94CiAgICAgIGVuZAoKICAgICAgbGFzdF94ID0geAogICAgZW5kCgogICAgcHV0cwoKICAgIGxhc3RfeCA9IDAKICAgIHNsYXNoZXMuZWFjaCBkbyB8eCwgY2hhcnwKICAgICAgcHJpbnQgIiAiICogKHggLSBsYXN0X3gpCiAgICAgIHByaW50IGNoYXIKICAgICAgbGFzdF94ID0geCArIDEKICAgIGVuZAogICAgcHV0cyB1bmxlc3Mgc2xhc2hlcy5lbXB0eT8KICBlbmQKZW5kCgojIOODhOODquODvOOBruWuo+iogOOCkuefreOBj+abuOOBj+OBn+OCgeOBq+Wumue+qQpkZWYgTm9kZSh2YWwsIGxlZnQ9bmlsLCByaWdodD1uaWwpCiAgbm9kZSA9IE5vZGUubmV3KHZhbCkKICBub2RlLmxlZnQgPSBsZWZ0CiAgbm9kZS5yaWdodCA9IHJpZ2h0CiAgbm9kZQplbmQKCnRyZWUgPSBOb2RlKDksIE5vZGUoNCwgTm9kZSgyKSwgTm9kZSg2KSksIE5vZGUoMTUsIE5vZGUoMTIpLCBOb2RlKDE3KSkpCnByaW50X2NhbnZhcyB0cmVlLnJlbmRlcigwKQpwcmludF9jYW52YXMyIHRyZWUucmVuZGVyKDApCnByaW50X2NhbnZhczIgdHJlZS5yZW5kZXIoMykKcHJpbnRfY2FudmFzMyB0cmVlLnJlbmRlcigxKQpwcmludF9jYW52YXMzIHRyZWUucmVuZGVyKDIpCnByaW50X2NhbnZhczMgdHJlZS5yZW5kZXIoMykKcHJpbnRfY2FudmFzMyBOb2RlKDQsIHRyZWUsIHRyZWUpLnJlbmRlcigwKQpwcmludF9jYW52YXMzIE5vZGUoNCwgdHJlZSwgdHJlZSkucmVuZGVyKDEpCnByaW50X2NhbnZhczMgTm9kZSg0LCBOb2RlKDksIHRyZWUsIG5pbCksIHRyZWUpLnJlbmRlcigyKQpwcmludF9jYW52YXMzIE5vZGUoNCwgdHJlZSwgdHJlZSkucmVuZGVyKDMpCg==