import random
import itertools
 
# dungeon size
width = 80
height = 40
 
# how big are rooms?
room_width_max = 8
room_width_min = 3
room_height_max = 8
room_height_min = 3
 
# display style
tiles = {False:'#',True:'.'}
 
# how is connectivity defined?
dirs4 = [(0,1),(0,-1),(1,0),(-1,0)]
dirs8 = dirs4 + [(1,1),(1,-1),(-1,1),(-1,-1)]
 
# is (x,y) in the level rectangle?
def in_range(x,y):
  return x >= 0 and y >= 0 and x < width and y < height
 
# unique integer index for each tile
def index(x,y):
  return y*width+x
 
# print walls and floors nicely
def render(m):
  for row in m:
    print ''.join(map(lambda x: tiles[x], row))
  print "\n"
 
# width * height grid of walls
def empty_map():
  m = [[False]*width for y in range(height)]
  return m
 
# n randomly placed rooms of various sizes.
# can overlap. no corridors
def disconnected_map(n):
  m = empty_map()
  for i in range(n):
    # room size
    room_width = random.randint(room_width_min,room_width_max)
    room_height = random.randint(room_height_min,room_height_max)
    # room location. mustn't be out of range.
    room_x = random.randint(0,width-room_width)
    room_y = random.randint(0,height-room_height)
    # make floors in the designated area
    for x in range(room_x,room_x+room_width):
      for y in range(room_y,room_y+room_height):
        m[y][x] = True
  return m
 
# find and mark the connected component that contains a given location
# m: wall map
# f: floodfill map
# (x,y): seed coordinate
# forbid: treat this tile as a wall
# returns component size
def floodfill_sub(m,f,(x,y),forbid=(-1,-1)):
  # don't floodfill from wall tiles
  if m[y][x] == False or f[y][x] != -1 or (x,y) == forbid:
    return 0
  # this is the number to tag tiles in this connected component with
  my_index = index(x,y)
  # coordinates that might be in this connected component
  boundary = [(x,y)]
  # how big is the connected component?
  size = 0
  while len(boundary) > 0:
    (xx,yy) = boundary.pop()
    # ignore tiles that are already claimed, walls, not in range, or forbidden
    if (xx,yy) == forbid: continue
    if not in_range(xx,yy): continue
    if not m[yy][xx]: continue
    if f[yy][xx] != -1: continue
    # mark the tile
    size += 1
    f[yy][xx] = my_index
    # queue all neighbouring tiles
    for (dx,dy) in dirs4:
      boundary.append((xx+dx,yy+dy))
  return size
 
# take a list of up to 8 coordinates and check whether they
# form a single connected component. some effect duplication
# with floodfill_sub.
def connected_neighbourhood(neighbours):
  # store whether each neighbour has been connected to the first
  m_neighbours = dict(zip(neighbours,itertools.repeat(False)))
  # store neighbours that need to be expanded
  boundary = [neighbours[0]]
  while len(boundary) > 0:
    (x,y) = boundary.pop()
    # mark as explored
    m_neighbours[(x,y)] = True
    for (dx,dy) in dirs4:
      # only consider listed neighbours
      try:
        if m_neighbours[(x+dx,y+dy)] == False:
          boundary.append((x+dx,y+dy))
      except KeyError: pass
  # are all the neighbours in the same component?
  components = set(m_neighbours.values())
  return components == set([True])
 
# check if the whole floodfill can be skipped
def skip_floodfill(m,(x,y),connected=False):
  if connected: # if the base map is not connected we can't skip
    good_neighbours = []
    for (dx,dy) in dirs8:
      (xx,yy) = (x+dx,y+dy)
      # if the neighbourhood of the forbidden square is connected and the
      #map is connected, then the forbidden square is not a bridge
      if in_range(xx,yy) and m[yy][xx]:
        good_neighbours.append((xx,yy))
    if connected_neighbourhood(good_neighbours):
      return True
  # the forbidden square may be a bridge or the map is disconnected
  return False
 
 
# find all connected components of map m, treating forbidden tile as a wall.
# cheat when the map is known to be connected.
def floodfill(m, forbid=(-1,-1), connected=False):
  if skip_floodfill(m,forbid,connected):
    return [],{}
  # initialise floodfill map with no tiles claimed
  f = [[-1]*width for y in range(height)]
  components = {}
  for y in range(height):
    for x in range(width):
      # claim all tiles in the same component as (x,y)
      ff_return = floodfill_sub(m,f,(x,y),forbid)
      if ff_return > 0:
        # make a note of components' size
        components[(x,y)] = ff_return
  return f,components
 
# find a corridor that connects the first two connected components of m,
# based on a precomputed floodfill f
def find_connector(m,f,components, forbid=(-1,-1)):
  if len(components) < 2:
    return None # nothing to be done
  # seed locations of two randomly chosen connected components
  # can be altered to connect all components but just two is enough
  keys = components.keys()
  random.shuffle(keys)
  # values in the floodfill map are indices, not coordinates
  index_a = index(*keys[0])
  index_b = index(*keys[1])
  # list all members of the connected components and choose two at random
  component_a_coords = [(x,y) for x in range(width)
                              for y in range(height)
                              if f[y][x] == index_a]
  component_b_coords = [(x,y) for x in range(width)
                              for y in range(height)
                              if f[y][x] == index_b]
  ax,ay = random.choice(component_a_coords)
  bx,by = random.choice(component_b_coords)
  # which direction is (bx,by) from (ax,ay)?
  dx,dy = cmp(bx,ax),cmp(by,ay)
  # sequence of coordinates up to but not including bx,by
  ax_bx = range(ax,bx,dx) if dx != 0 else [ax]
  ay_by = range(ay,by,dy) if dy != 0 else [ay]
  # try going horizontally then vertically
  connect_h = zip(ax_bx,[ay]*len(ax_bx)) + \
              zip([bx]*len(ay_by),ay_by) + \
              [(bx,by)]
  # try instead going vertically then horizontally
  connect_v = zip([ax]*len(ay_by),ay_by) + \
              zip(ax_bx,[by]*len(ax_bx)) + \
              [(bx,by)]
  # the connector is no use if a tile is forbidden
  if forbid in connect_h:
    connect = connect_v
  elif forbid in connect_v:
    connect = connect_h
  else: # choose randomly if possible
    connect = random.choice([connect_h,connect_v])
  a_idx = 0
  b_idx = 0
  # what's the last tile in component a before the first tile in component b?
  for (i,(x,y)) in zip(itertools.count(),connect):
    if f[y][x] == index_a:
      a_idx = i
    elif f[y][x] == index_b:
      b_idx = i
      break
  # cut out all unnecessary coordinates from the connector and return
  connect = connect[a_idx+1:b_idx]
  return connect
 
# take any map with at least 2 floor tiles and make it biconnected.
# there will be at least 2 disjoint paths between any pair of floor tiles.
def biconnected_map(m):
  # queue all floor tiles for testing
  c =[(x,y) for x in range(width) for y in range(height) if m[y][x]]
  random.shuffle(c)
  connected = False
  while len(c) > 0:
    (x,y) = c.pop()
    # treat the chosen tile as wall, making an induced subgraph.
    # What are the components of this subgraph?
    f,components = floodfill(m,(x,y), connected)
    if len(components) <= 1:
      connected = True
      continue
    # If there's more than one connected component,
    # find a way to connect them (not including (x,y)
    connector = find_connector(m,f,components,(x,y))
    if connector != None:
      # check the tile in case any more needs to be done
      c.append((x,y))
      # add some of the new connector tiles for checking if necessary
      if not connected:
        c.append(connector[0])
        c.append(connector[-1])
      # alter the wall map
      for (xx,yy) in connector:
        m[yy][xx] = True
  return m
 
# example usage
if __name__ == '__main__':
  # start with something that has < 1 connected component
  m = disconnected_map(20)
  # print non-biconnected map for reference
  render(m)
  m = biconnected_map(m)
  # print the map in order to gloat about the biconnected magicalness
  render(m)
 
# This is free and unencumbered software released into the public domain.
 
# Anyone is free to copy, modify, publish, use, compile, sell, or
# distribute this software, either in source code form or as a compiled
# binary, for any purpose, commercial or non-commercial, and by any
# means.
 
# In jurisdictions that recognize copyright laws, the author or authors
# of this software dedicate any and all copyright interest in the
# software to the public domain. We make this dedication for the benefit
# of the public at large and to the detriment of our heirs and
# successors. We intend this dedication to be an overt act of
# relinquishment in perpetuity of all present and future rights to this
# software under copyright law.
 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
# IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
# OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
# ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# OTHER DEALINGS IN THE SOFTWARE.
 
# For more information, please refer to <http://u...content-available-to-author-only...e.org/>

aW1wb3J0IHJhbmRvbQppbXBvcnQgaXRlcnRvb2xzCgojIGR1bmdlb24gc2l6ZQp3aWR0aCA9IDgwCmhlaWdodCA9IDQwCgojIGhvdyBiaWcgYXJlIHJvb21zPwpyb29tX3dpZHRoX21heCA9IDgKcm9vbV93aWR0aF9taW4gPSAzCnJvb21faGVpZ2h0X21heCA9IDgKcm9vbV9oZWlnaHRfbWluID0gMwoKIyBkaXNwbGF5IHN0eWxlCnRpbGVzID0ge0ZhbHNlOicjJyxUcnVlOicuJ30KCiMgaG93IGlzIGNvbm5lY3Rpdml0eSBkZWZpbmVkPwpkaXJzNCA9IFsoMCwxKSwoMCwtMSksKDEsMCksKC0xLDApXQpkaXJzOCA9IGRpcnM0ICsgWygxLDEpLCgxLC0xKSwoLTEsMSksKC0xLC0xKV0KCiMgaXMgKHgseSkgaW4gdGhlIGxldmVsIHJlY3RhbmdsZT8KZGVmIGluX3JhbmdlKHgseSk6CiAgcmV0dXJuIHggPj0gMCBhbmQgeSA+PSAwIGFuZCB4IDwgd2lkdGggYW5kIHkgPCBoZWlnaHQKCiMgdW5pcXVlIGludGVnZXIgaW5kZXggZm9yIGVhY2ggdGlsZQpkZWYgaW5kZXgoeCx5KToKICByZXR1cm4geSp3aWR0aCt4CgojIHByaW50IHdhbGxzIGFuZCBmbG9vcnMgbmljZWx5CmRlZiByZW5kZXIobSk6CiAgZm9yIHJvdyBpbiBtOgogICAgcHJpbnQgJycuam9pbihtYXAobGFtYmRhIHg6IHRpbGVzW3hdLCByb3cpKQogIHByaW50ICJcbiIKCiMgd2lkdGggKiBoZWlnaHQgZ3JpZCBvZiB3YWxscwpkZWYgZW1wdHlfbWFwKCk6CiAgbSA9IFtbRmFsc2VdKndpZHRoIGZvciB5IGluIHJhbmdlKGhlaWdodCldCiAgcmV0dXJuIG0KCiMgbiByYW5kb21seSBwbGFjZWQgcm9vbXMgb2YgdmFyaW91cyBzaXplcy4KIyBjYW4gb3ZlcmxhcC4gbm8gY29ycmlkb3JzCmRlZiBkaXNjb25uZWN0ZWRfbWFwKG4pOgogIG0gPSBlbXB0eV9tYXAoKQogIGZvciBpIGluIHJhbmdlKG4pOgogICAgIyByb29tIHNpemUKICAgIHJvb21fd2lkdGggPSByYW5kb20ucmFuZGludChyb29tX3dpZHRoX21pbixyb29tX3dpZHRoX21heCkKICAgIHJvb21faGVpZ2h0ID0gcmFuZG9tLnJhbmRpbnQocm9vbV9oZWlnaHRfbWluLHJvb21faGVpZ2h0X21heCkKICAgICMgcm9vbSBsb2NhdGlvbi4gbXVzdG4ndCBiZSBvdXQgb2YgcmFuZ2UuCiAgICByb29tX3ggPSByYW5kb20ucmFuZGludCgwLHdpZHRoLXJvb21fd2lkdGgpCiAgICByb29tX3kgPSByYW5kb20ucmFuZGludCgwLGhlaWdodC1yb29tX2hlaWdodCkKICAgICMgbWFrZSBmbG9vcnMgaW4gdGhlIGRlc2lnbmF0ZWQgYXJlYQogICAgZm9yIHggaW4gcmFuZ2Uocm9vbV94LHJvb21feCtyb29tX3dpZHRoKToKICAgICAgZm9yIHkgaW4gcmFuZ2Uocm9vbV95LHJvb21feStyb29tX2hlaWdodCk6CiAgICAgICAgbVt5XVt4XSA9IFRydWUKICByZXR1cm4gbQoKIyBmaW5kIGFuZCBtYXJrIHRoZSBjb25uZWN0ZWQgY29tcG9uZW50IHRoYXQgY29udGFpbnMgYSBnaXZlbiBsb2NhdGlvbgojIG06IHdhbGwgbWFwCiMgZjogZmxvb2RmaWxsIG1hcAojICh4LHkpOiBzZWVkIGNvb3JkaW5hdGUKIyBmb3JiaWQ6IHRyZWF0IHRoaXMgdGlsZSBhcyBhIHdhbGwKIyByZXR1cm5zIGNvbXBvbmVudCBzaXplCmRlZiBmbG9vZGZpbGxfc3ViKG0sZiwoeCx5KSxmb3JiaWQ9KC0xLC0xKSk6CiAgIyBkb24ndCBmbG9vZGZpbGwgZnJvbSB3YWxsIHRpbGVzCiAgaWYgbVt5XVt4XSA9PSBGYWxzZSBvciBmW3ldW3hdICE9IC0xIG9yICh4LHkpID09IGZvcmJpZDoKICAgIHJldHVybiAwCiAgIyB0aGlzIGlzIHRoZSBudW1iZXIgdG8gdGFnIHRpbGVzIGluIHRoaXMgY29ubmVjdGVkIGNvbXBvbmVudCB3aXRoCiAgbXlfaW5kZXggPSBpbmRleCh4LHkpCiAgIyBjb29yZGluYXRlcyB0aGF0IG1pZ2h0IGJlIGluIHRoaXMgY29ubmVjdGVkIGNvbXBvbmVudAogIGJvdW5kYXJ5ID0gWyh4LHkpXQogICMgaG93IGJpZyBpcyB0aGUgY29ubmVjdGVkIGNvbXBvbmVudD8KICBzaXplID0gMAogIHdoaWxlIGxlbihib3VuZGFyeSkgPiAwOgogICAgKHh4LHl5KSA9IGJvdW5kYXJ5LnBvcCgpCiAgICAjIGlnbm9yZSB0aWxlcyB0aGF0IGFyZSBhbHJlYWR5IGNsYWltZWQsIHdhbGxzLCBub3QgaW4gcmFuZ2UsIG9yIGZvcmJpZGRlbgogICAgaWYgKHh4LHl5KSA9PSBmb3JiaWQ6IGNvbnRpbnVlCiAgICBpZiBub3QgaW5fcmFuZ2UoeHgseXkpOiBjb250aW51ZQogICAgaWYgbm90IG1beXldW3h4XTogY29udGludWUKICAgIGlmIGZbeXldW3h4XSAhPSAtMTogY29udGludWUKICAgICMgbWFyayB0aGUgdGlsZQogICAgc2l6ZSArPSAxCiAgICBmW3l5XVt4eF0gPSBteV9pbmRleAogICAgIyBxdWV1ZSBhbGwgbmVpZ2hib3VyaW5nIHRpbGVzCiAgICBmb3IgKGR4LGR5KSBpbiBkaXJzNDoKICAgICAgYm91bmRhcnkuYXBwZW5kKCh4eCtkeCx5eStkeSkpCiAgcmV0dXJuIHNpemUKICAKIyB0YWtlIGEgbGlzdCBvZiB1cCB0byA4IGNvb3JkaW5hdGVzIGFuZCBjaGVjayB3aGV0aGVyIHRoZXkKIyBmb3JtIGEgc2luZ2xlIGNvbm5lY3RlZCBjb21wb25lbnQuIHNvbWUgZWZmZWN0IGR1cGxpY2F0aW9uCiMgd2l0aCBmbG9vZGZpbGxfc3ViLgpkZWYgY29ubmVjdGVkX25laWdoYm91cmhvb2QobmVpZ2hib3Vycyk6CiAgIyBzdG9yZSB3aGV0aGVyIGVhY2ggbmVpZ2hib3VyIGhhcyBiZWVuIGNvbm5lY3RlZCB0byB0aGUgZmlyc3QKICBtX25laWdoYm91cnMgPSBkaWN0KHppcChuZWlnaGJvdXJzLGl0ZXJ0b29scy5yZXBlYXQoRmFsc2UpKSkKICAjIHN0b3JlIG5laWdoYm91cnMgdGhhdCBuZWVkIHRvIGJlIGV4cGFuZGVkCiAgYm91bmRhcnkgPSBbbmVpZ2hib3Vyc1swXV0KICB3aGlsZSBsZW4oYm91bmRhcnkpID4gMDoKICAgICh4LHkpID0gYm91bmRhcnkucG9wKCkKICAgICMgbWFyayBhcyBleHBsb3JlZAogICAgbV9uZWlnaGJvdXJzWyh4LHkpXSA9IFRydWUKICAgIGZvciAoZHgsZHkpIGluIGRpcnM0OgogICAgICAjIG9ubHkgY29uc2lkZXIgbGlzdGVkIG5laWdoYm91cnMKICAgICAgdHJ5OgogICAgICAgIGlmIG1fbmVpZ2hib3Vyc1soeCtkeCx5K2R5KV0gPT0gRmFsc2U6CiAgICAgICAgICBib3VuZGFyeS5hcHBlbmQoKHgrZHgseStkeSkpCiAgICAgIGV4Y2VwdCBLZXlFcnJvcjogcGFzcwogICMgYXJlIGFsbCB0aGUgbmVpZ2hib3VycyBpbiB0aGUgc2FtZSBjb21wb25lbnQ/CiAgY29tcG9uZW50cyA9IHNldChtX25laWdoYm91cnMudmFsdWVzKCkpCiAgcmV0dXJuIGNvbXBvbmVudHMgPT0gc2V0KFtUcnVlXSkKICAKIyBjaGVjayBpZiB0aGUgd2hvbGUgZmxvb2RmaWxsIGNhbiBiZSBza2lwcGVkCmRlZiBza2lwX2Zsb29kZmlsbChtLCh4LHkpLGNvbm5lY3RlZD1GYWxzZSk6CiAgaWYgY29ubmVjdGVkOiAjIGlmIHRoZSBiYXNlIG1hcCBpcyBub3QgY29ubmVjdGVkIHdlIGNhbid0IHNraXAKICAgIGdvb2RfbmVpZ2hib3VycyA9IFtdCiAgICBmb3IgKGR4LGR5KSBpbiBkaXJzODoKICAgICAgKHh4LHl5KSA9ICh4K2R4LHkrZHkpCiAgICAgICMgaWYgdGhlIG5laWdoYm91cmhvb2Qgb2YgdGhlIGZvcmJpZGRlbiBzcXVhcmUgaXMgY29ubmVjdGVkIGFuZCB0aGUKICAgICAgI21hcCBpcyBjb25uZWN0ZWQsIHRoZW4gdGhlIGZvcmJpZGRlbiBzcXVhcmUgaXMgbm90IGEgYnJpZGdlCiAgICAgIGlmIGluX3JhbmdlKHh4LHl5KSBhbmQgbVt5eV1beHhdOgogICAgICAgIGdvb2RfbmVpZ2hib3Vycy5hcHBlbmQoKHh4LHl5KSkKICAgIGlmIGNvbm5lY3RlZF9uZWlnaGJvdXJob29kKGdvb2RfbmVpZ2hib3Vycyk6CiAgICAgIHJldHVybiBUcnVlCiAgIyB0aGUgZm9yYmlkZGVuIHNxdWFyZSBtYXkgYmUgYSBicmlkZ2Ugb3IgdGhlIG1hcCBpcyBkaXNjb25uZWN0ZWQKICByZXR1cm4gRmFsc2UKICAgICAgCgojIGZpbmQgYWxsIGNvbm5lY3RlZCBjb21wb25lbnRzIG9mIG1hcCBtLCB0cmVhdGluZyBmb3JiaWRkZW4gdGlsZSBhcyBhIHdhbGwuCiMgY2hlYXQgd2hlbiB0aGUgbWFwIGlzIGtub3duIHRvIGJlIGNvbm5lY3RlZC4KZGVmIGZsb29kZmlsbChtLCBmb3JiaWQ9KC0xLC0xKSwgY29ubmVjdGVkPUZhbHNlKToKICBpZiBza2lwX2Zsb29kZmlsbChtLGZvcmJpZCxjb25uZWN0ZWQpOgogICAgcmV0dXJuIFtdLHt9CiAgIyBpbml0aWFsaXNlIGZsb29kZmlsbCBtYXAgd2l0aCBubyB0aWxlcyBjbGFpbWVkCiAgZiA9IFtbLTFdKndpZHRoIGZvciB5IGluIHJhbmdlKGhlaWdodCldCiAgY29tcG9uZW50cyA9IHt9CiAgZm9yIHkgaW4gcmFuZ2UoaGVpZ2h0KToKICAgIGZvciB4IGluIHJhbmdlKHdpZHRoKToKICAgICAgIyBjbGFpbSBhbGwgdGlsZXMgaW4gdGhlIHNhbWUgY29tcG9uZW50IGFzICh4LHkpCiAgICAgIGZmX3JldHVybiA9IGZsb29kZmlsbF9zdWIobSxmLCh4LHkpLGZvcmJpZCkKICAgICAgaWYgZmZfcmV0dXJuID4gMDoKICAgICAgICAjIG1ha2UgYSBub3RlIG9mIGNvbXBvbmVudHMnIHNpemUKICAgICAgICBjb21wb25lbnRzWyh4LHkpXSA9IGZmX3JldHVybgogIHJldHVybiBmLGNvbXBvbmVudHMKCiMgZmluZCBhIGNvcnJpZG9yIHRoYXQgY29ubmVjdHMgdGhlIGZpcnN0IHR3byBjb25uZWN0ZWQgY29tcG9uZW50cyBvZiBtLAojIGJhc2VkIG9uIGEgcHJlY29tcHV0ZWQgZmxvb2RmaWxsIGYKZGVmIGZpbmRfY29ubmVjdG9yKG0sZixjb21wb25lbnRzLCBmb3JiaWQ9KC0xLC0xKSk6CiAgaWYgbGVuKGNvbXBvbmVudHMpIDwgMjoKICAgIHJldHVybiBOb25lICMgbm90aGluZyB0byBiZSBkb25lCiAgIyBzZWVkIGxvY2F0aW9ucyBvZiB0d28gcmFuZG9tbHkgY2hvc2VuIGNvbm5lY3RlZCBjb21wb25lbnRzCiAgIyBjYW4gYmUgYWx0ZXJlZCB0byBjb25uZWN0IGFsbCBjb21wb25lbnRzIGJ1dCBqdXN0IHR3byBpcyBlbm91Z2gKICBrZXlzID0gY29tcG9uZW50cy5rZXlzKCkKICByYW5kb20uc2h1ZmZsZShrZXlzKQogICMgdmFsdWVzIGluIHRoZSBmbG9vZGZpbGwgbWFwIGFyZSBpbmRpY2VzLCBub3QgY29vcmRpbmF0ZXMKICBpbmRleF9hID0gaW5kZXgoKmtleXNbMF0pCiAgaW5kZXhfYiA9IGluZGV4KCprZXlzWzFdKQogICMgbGlzdCBhbGwgbWVtYmVycyBvZiB0aGUgY29ubmVjdGVkIGNvbXBvbmVudHMgYW5kIGNob29zZSB0d28gYXQgcmFuZG9tCiAgY29tcG9uZW50X2FfY29vcmRzID0gWyh4LHkpIGZvciB4IGluIHJhbmdlKHdpZHRoKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICBmb3IgeSBpbiByYW5nZShoZWlnaHQpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmIGZbeV1beF0gPT0gaW5kZXhfYV0KICBjb21wb25lbnRfYl9jb29yZHMgPSBbKHgseSkgZm9yIHggaW4gcmFuZ2Uod2lkdGgpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGZvciB5IGluIHJhbmdlKGhlaWdodCkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgZlt5XVt4XSA9PSBpbmRleF9iXQogIGF4LGF5ID0gcmFuZG9tLmNob2ljZShjb21wb25lbnRfYV9jb29yZHMpCiAgYngsYnkgPSByYW5kb20uY2hvaWNlKGNvbXBvbmVudF9iX2Nvb3JkcykKICAjIHdoaWNoIGRpcmVjdGlvbiBpcyAoYngsYnkpIGZyb20gKGF4LGF5KT8KICBkeCxkeSA9IGNtcChieCxheCksY21wKGJ5LGF5KQogICMgc2VxdWVuY2Ugb2YgY29vcmRpbmF0ZXMgdXAgdG8gYnV0IG5vdCBpbmNsdWRpbmcgYngsYnkKICBheF9ieCA9IHJhbmdlKGF4LGJ4LGR4KSBpZiBkeCAhPSAwIGVsc2UgW2F4XQogIGF5X2J5ID0gcmFuZ2UoYXksYnksZHkpIGlmIGR5ICE9IDAgZWxzZSBbYXldCiAgIyB0cnkgZ29pbmcgaG9yaXpvbnRhbGx5IHRoZW4gdmVydGljYWxseQogIGNvbm5lY3RfaCA9IHppcChheF9ieCxbYXldKmxlbihheF9ieCkpICsgXAogICAgICAgICAgICAgIHppcChbYnhdKmxlbihheV9ieSksYXlfYnkpICsgXAogICAgICAgICAgICAgIFsoYngsYnkpXQogICMgdHJ5IGluc3RlYWQgZ29pbmcgdmVydGljYWxseSB0aGVuIGhvcml6b250YWxseQogIGNvbm5lY3RfdiA9IHppcChbYXhdKmxlbihheV9ieSksYXlfYnkpICsgXAogICAgICAgICAgICAgIHppcChheF9ieCxbYnldKmxlbihheF9ieCkpICsgXAogICAgICAgICAgICAgIFsoYngsYnkpXQogICMgdGhlIGNvbm5lY3RvciBpcyBubyB1c2UgaWYgYSB0aWxlIGlzIGZvcmJpZGRlbgogIGlmIGZvcmJpZCBpbiBjb25uZWN0X2g6CiAgICBjb25uZWN0ID0gY29ubmVjdF92CiAgZWxpZiBmb3JiaWQgaW4gY29ubmVjdF92OgogICAgY29ubmVjdCA9IGNvbm5lY3RfaAogIGVsc2U6ICMgY2hvb3NlIHJhbmRvbWx5IGlmIHBvc3NpYmxlCiAgICBjb25uZWN0ID0gcmFuZG9tLmNob2ljZShbY29ubmVjdF9oLGNvbm5lY3Rfdl0pCiAgYV9pZHggPSAwCiAgYl9pZHggPSAwCiAgIyB3aGF0J3MgdGhlIGxhc3QgdGlsZSBpbiBjb21wb25lbnQgYSBiZWZvcmUgdGhlIGZpcnN0IHRpbGUgaW4gY29tcG9uZW50IGI/CiAgZm9yIChpLCh4LHkpKSBpbiB6aXAoaXRlcnRvb2xzLmNvdW50KCksY29ubmVjdCk6CiAgICBpZiBmW3ldW3hdID09IGluZGV4X2E6CiAgICAgIGFfaWR4ID0gaQogICAgZWxpZiBmW3ldW3hdID09IGluZGV4X2I6CiAgICAgIGJfaWR4ID0gaQogICAgICBicmVhawogICMgY3V0IG91dCBhbGwgdW5uZWNlc3NhcnkgY29vcmRpbmF0ZXMgZnJvbSB0aGUgY29ubmVjdG9yIGFuZCByZXR1cm4KICBjb25uZWN0ID0gY29ubmVjdFthX2lkeCsxOmJfaWR4XQogIHJldHVybiBjb25uZWN0CiAgCiMgdGFrZSBhbnkgbWFwIHdpdGggYXQgbGVhc3QgMiBmbG9vciB0aWxlcyBhbmQgbWFrZSBpdCBiaWNvbm5lY3RlZC4KIyB0aGVyZSB3aWxsIGJlIGF0IGxlYXN0IDIgZGlzam9pbnQgcGF0aHMgYmV0d2VlbiBhbnkgcGFpciBvZiBmbG9vciB0aWxlcy4KZGVmIGJpY29ubmVjdGVkX21hcChtKToKICAjIHF1ZXVlIGFsbCBmbG9vciB0aWxlcyBmb3IgdGVzdGluZwogIGMgPVsoeCx5KSBmb3IgeCBpbiByYW5nZSh3aWR0aCkgZm9yIHkgaW4gcmFuZ2UoaGVpZ2h0KSBpZiBtW3ldW3hdXQogIHJhbmRvbS5zaHVmZmxlKGMpCiAgY29ubmVjdGVkID0gRmFsc2UKICB3aGlsZSBsZW4oYykgPiAwOgogICAgKHgseSkgPSBjLnBvcCgpCiAgICAjIHRyZWF0IHRoZSBjaG9zZW4gdGlsZSBhcyB3YWxsLCBtYWtpbmcgYW4gaW5kdWNlZCBzdWJncmFwaC4KICAgICMgV2hhdCBhcmUgdGhlIGNvbXBvbmVudHMgb2YgdGhpcyBzdWJncmFwaD8KICAgIGYsY29tcG9uZW50cyA9IGZsb29kZmlsbChtLCh4LHkpLCBjb25uZWN0ZWQpCiAgICBpZiBsZW4oY29tcG9uZW50cykgPD0gMToKICAgICAgY29ubmVjdGVkID0gVHJ1ZQogICAgICBjb250aW51ZQogICAgIyBJZiB0aGVyZSdzIG1vcmUgdGhhbiBvbmUgY29ubmVjdGVkIGNvbXBvbmVudCwKICAgICMgZmluZCBhIHdheSB0byBjb25uZWN0IHRoZW0gKG5vdCBpbmNsdWRpbmcgKHgseSkKICAgIGNvbm5lY3RvciA9IGZpbmRfY29ubmVjdG9yKG0sZixjb21wb25lbnRzLCh4LHkpKQogICAgaWYgY29ubmVjdG9yICE9IE5vbmU6CiAgICAgICMgY2hlY2sgdGhlIHRpbGUgaW4gY2FzZSBhbnkgbW9yZSBuZWVkcyB0byBiZSBkb25lCiAgICAgIGMuYXBwZW5kKCh4LHkpKQogICAgICAjIGFkZCBzb21lIG9mIHRoZSBuZXcgY29ubmVjdG9yIHRpbGVzIGZvciBjaGVja2luZyBpZiBuZWNlc3NhcnkKICAgICAgaWYgbm90IGNvbm5lY3RlZDoKICAgICAgICBjLmFwcGVuZChjb25uZWN0b3JbMF0pCiAgICAgICAgYy5hcHBlbmQoY29ubmVjdG9yWy0xXSkKICAgICAgIyBhbHRlciB0aGUgd2FsbCBtYXAKICAgICAgZm9yICh4eCx5eSkgaW4gY29ubmVjdG9yOgogICAgICAgIG1beXldW3h4XSA9IFRydWUKICByZXR1cm4gbQoKIyBleGFtcGxlIHVzYWdlCmlmIF9fbmFtZV9fID09ICdfX21haW5fXyc6CiAgIyBzdGFydCB3aXRoIHNvbWV0aGluZyB0aGF0IGhhcyA8IDEgY29ubmVjdGVkIGNvbXBvbmVudAogIG0gPSBkaXNjb25uZWN0ZWRfbWFwKDIwKQogICMgcHJpbnQgbm9uLWJpY29ubmVjdGVkIG1hcCBmb3IgcmVmZXJlbmNlCiAgcmVuZGVyKG0pCiAgbSA9IGJpY29ubmVjdGVkX21hcChtKQogICMgcHJpbnQgdGhlIG1hcCBpbiBvcmRlciB0byBnbG9hdCBhYm91dCB0aGUgYmljb25uZWN0ZWQgbWFnaWNhbG5lc3MKICByZW5kZXIobSkKICAKIyBUaGlzIGlzIGZyZWUgYW5kIHVuZW5jdW1iZXJlZCBzb2Z0d2FyZSByZWxlYXNlZCBpbnRvIHRoZSBwdWJsaWMgZG9tYWluLgoKIyBBbnlvbmUgaXMgZnJlZSB0byBjb3B5LCBtb2RpZnksIHB1Ymxpc2gsIHVzZSwgY29tcGlsZSwgc2VsbCwgb3IKIyBkaXN0cmlidXRlIHRoaXMgc29mdHdhcmUsIGVpdGhlciBpbiBzb3VyY2UgY29kZSBmb3JtIG9yIGFzIGEgY29tcGlsZWQKIyBiaW5hcnksIGZvciBhbnkgcHVycG9zZSwgY29tbWVyY2lhbCBvciBub24tY29tbWVyY2lhbCwgYW5kIGJ5IGFueQojIG1lYW5zLgoKIyBJbiBqdXJpc2RpY3Rpb25zIHRoYXQgcmVjb2duaXplIGNvcHlyaWdodCBsYXdzLCB0aGUgYXV0aG9yIG9yIGF1dGhvcnMKIyBvZiB0aGlzIHNvZnR3YXJlIGRlZGljYXRlIGFueSBhbmQgYWxsIGNvcHlyaWdodCBpbnRlcmVzdCBpbiB0aGUKIyBzb2Z0d2FyZSB0byB0aGUgcHVibGljIGRvbWFpbi4gV2UgbWFrZSB0aGlzIGRlZGljYXRpb24gZm9yIHRoZSBiZW5lZml0CiMgb2YgdGhlIHB1YmxpYyBhdCBsYXJnZSBhbmQgdG8gdGhlIGRldHJpbWVudCBvZiBvdXIgaGVpcnMgYW5kCiMgc3VjY2Vzc29ycy4gV2UgaW50ZW5kIHRoaXMgZGVkaWNhdGlvbiB0byBiZSBhbiBvdmVydCBhY3Qgb2YKIyByZWxpbnF1aXNobWVudCBpbiBwZXJwZXR1aXR5IG9mIGFsbCBwcmVzZW50IGFuZCBmdXR1cmUgcmlnaHRzIHRvIHRoaXMKIyBzb2Z0d2FyZSB1bmRlciBjb3B5cmlnaHQgbGF3LgoKIyBUSEUgU09GVFdBUkUgSVMgUFJPVklERUQgIkFTIElTIiwgV0lUSE9VVCBXQVJSQU5UWSBPRiBBTlkgS0lORCwKIyBFWFBSRVNTIE9SIElNUExJRUQsIElOQ0xVRElORyBCVVQgTk9UIExJTUlURUQgVE8gVEhFIFdBUlJBTlRJRVMgT0YKIyBNRVJDSEFOVEFCSUxJVFksIEZJVE5FU1MgRk9SIEEgUEFSVElDVUxBUiBQVVJQT1NFIEFORCBOT05JTkZSSU5HRU1FTlQuCiMgSU4gTk8gRVZFTlQgU0hBTEwgVEhFIEFVVEhPUlMgQkUgTElBQkxFIEZPUiBBTlkgQ0xBSU0sIERBTUFHRVMgT1IKIyBPVEhFUiBMSUFCSUxJVFksIFdIRVRIRVIgSU4gQU4gQUNUSU9OIE9GIENPTlRSQUNULCBUT1JUIE9SIE9USEVSV0lTRSwKIyBBUklTSU5HIEZST00sIE9VVCBPRiBPUiBJTiBDT05ORUNUSU9OIFdJVEggVEhFIFNPRlRXQVJFIE9SIFRIRSBVU0UgT1IKIyBPVEhFUiBERUFMSU5HUyBJTiBUSEUgU09GVFdBUkUuCgojIEZvciBtb3JlIGluZm9ybWF0aW9uLCBwbGVhc2UgcmVmZXIgdG8gPGh0dHA6Ly91Li4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5lLm9yZy8+