# Utility functions
def intersect(line0, line1)
  def aux(line0,line1)
    a,b = line0[0]
    c,d = line0[1]
    e,f = b-d,c-a
    p0x,p0y = line1[0][0]-a, line1[0][1]-b
    p1x,p1y = line1[1][0]-a, line1[1][1]-b
 
    (e*p0x+f*p0y)*(e*p1x+f*p1y) < 0.0
  end
 
  aux(line0,line1) && aux(line1,line0)
end
 
def i2r_x(i)
  @bounds[0][0] + i*@grid_width + @delta
end
 
def i2r_y(i)
  @bounds[1][0] + i*@grid_width + @delta
end
 
def grid_to_cartesian(p)
  [i2r_x(p[0]), i2r_y(p[1])]
end
 
def reducible?(p0,p1)
  line = [grid_to_cartesian(p0), grid_to_cartesian(p1)]
  @boards.each do |board|
    return false if intersect(line, board)
  end
 
  true
end
 
def reduce(src)
  r = []
  loop do
    if src.length < 3
      r << src[0]
      r << src[1]
      break
    else
      if reducible?(src[0],src[2])
        src.delete_at(1)
      else
        r << src.shift
      end
    end
  end
 
  r
end
 
def make_taboo(grid_n)
  def template(grid_n, type, r)
    (grid_n-type).times do |j|
      (grid_n-(1-type)).times do |i|
        p0,p1 = type == 0 ? [[i,j],[i+1,j]] : [[i,j],[i,j+1]]
        line0 = [grid_to_cartesian(p0),grid_to_cartesian(p1)]
        @boards.each do |line1|
          if intersect(line0, line1)
            r[p0] ||= []
            r[p1] ||= []
            r[p0] << p1
            r[p1] << p0
          end
        end
      end
    end
  end
  r = {}
  template(grid_n, 0, r)
  template(grid_n, 1, r)
 
  r
end
 
def make_taboo_fast(grid_n)
  def w2g_x(r)
    (r - @bounds[0][0] - @delta) / @grid_width
  end
  def w2g_y(r)
    (r - @bounds[1][0] - @delta) / @grid_width
  end
  def cartesian_to_grid(p0)
    [w2g_x(p0[0]), w2g_y(p0[1])]
  end
  def line_to_coverrange(line)
    x0,y0 = cartesian_to_grid(line[0])
    x1,y1 = cartesian_to_grid(line[1])
    x_min,x_max = [x0,x1].minmax
    y_min,y_max = [y0,y1].minmax
    [[x_min.floor, x_max.ceil],[y_min.floor, y_max.ceil]]
  end
  def add(r,p0,p1)
    r[p0] ||= []
    r[p1] ||= []
    r[p0] << p1
    r[p1] << p0
  end
  r = {}
  @boards.each do |b|
    line = [cartesian_to_grid(b[0]), cartesian_to_grid(b[1])]
    x_range,y_range = line_to_coverrange(b)
    xd = line[1][0]-line[0][0]
    yd = line[1][1]-line[0][1]
 
    if xd != 0.0
      i = x_range[0] + 1
      i = 0 if i < 0
      while i < x_range[1]
        y_f = yd * (i.to_f-line[0][0]) / xd + line[0][1]
        y = y_f.floor
        add(r,[i,y],[i,y+1])
        i += 1
      end
    end
 
    if yd != 0.0
      i = y_range[0] + 1
      i = 0 if i < 0
      while i < y_range[1]
        x_f = xd * (i.to_f-line[0][1]) / yd + line[0][0]
        x = x_f.floor
        add(r,[x,i],[x+1,i])
        i += 1
      end
    end
  end
 
  r
end
 
# Search on Grid (Beam Search) Definition
class Search
  def initialize(grid_n, taboo, start_pos, target_pos)
    @grid_n = grid_n
    @taboo = taboo
    @start_pos, @target_pos = start_pos, target_pos
    @has_answer = false
    @answer = nil
  end
  def h(pos)
    # Manhattan distance
    (@target_pos[0]-pos[0]).abs+(@target_pos[1]-pos[1]).abs
  end
  def successors(pos)
    r = []
    [[1,0],[0,1],[-1,0],[0,-1]].each do |d|
      i,j = pos[0]+d[0], pos[1]+d[1]
      next unless 0 <= i && i < @grid_n && 0 <= j && j < @grid_n
      succ = [i,j]
      r << succ unless @taboo[pos] && @taboo[pos].include?(succ)
    end
 
    r
  end
  def calc(beamwidth)
    states = [@start_pos]
    history = {}
    tmp = []
    loop do
      break unless 0 < states.length
 
      states.each do |cur_pos|
        succs = []
        successors(cur_pos).each do |succ|
          if succ == @target_pos
            result = [@target_pos, cur_pos]
            pos = cur_pos
            while prev_pos = history[pos]
              result << prev_pos
              break if prev_pos == @start_pos
              pos = prev_pos
            end
            return [true, result.reverse]
          end
          unless history[succ]
            history[succ] = cur_pos
            succs << [h(succ), succ]
          end
        end
        tmp.concat(succs)
      end
 
      tmp.sort!
      states.clear
 
      n = [tmp.length, beamwidth].min
      n.times do |i|
        states << tmp[i][1]
      end
 
      tmp.clear
    end
 
    [false, nil]
  end
end
 
# Simulated Anealing Definition
class SimulatedAnealing
  def initialize(energy_func, neighbour_func, temparature_func, probablity_func)
    @energy = energy_func # state -> float(energy)
    @neighbour = neighbour_func # state -> state
    @temparature = temparature_func # float(progress degree) -> float(temparature)
    @probability = probablity_func # float(energy_src) -> float(energy_dst) -> temparature -> float(probablity)
  end
  def calc(start_state, max_iter, goal_energy)
    state = start_state
    e = @energy.call(state)
    best_state = state
    best_e = e
    max_iter.times do |iter|
      next_state = @neighbour.call(state)
      next_e = @energy.call(next_state)
      if next_e <= best_e
        best_state = next_state
        best_e = next_e
        if best_e <= goal_energy
          return best_state
        end
      end
 
      t = @temparature.call(iter.to_f / max_iter)
      prob = @probability.call(e, next_e, t)
      if Random.rand <= prob
        state = next_state
        e = next_e
      end
    end
 
    best_state
  end
end
 
# Setting functions
def set_boards(n) # parallel zigzag pattern
  dy = (@bounds[1][1] - @bounds[1][0]) / (n+1)
 
  n.times do |i|
    y0 = @bounds[1][0]
    yval = y0+dy*(i+1)
    board =
      if i%2 == 0
        [[0.0, yval], [0.66, yval]]
      else
        [[0.33, yval], [1.0, yval]]
      end
    @boards << board
  end
end
 
def set_boards2(n) # diagonal zigzag pattern
  def add(delta,width,x,y)
    p0 = [x*width-delta, y*width+delta]
    p1 = [(x+1)*width+delta, (y-1)*width-delta]
    @boards << [p0, p1]
  end
  delta = 0.00001
  width = 1.0 / (n-1)
 
  (2..(2*(n-2))).each do |k|
    iter_num = k < n ? k : (2*(n-1)-k)
    pass_index0 = Random.rand(iter_num)
    pass_index1 = Random.rand(iter_num)
    iter_num.times do |i|
      next if i == pass_index0 || i == pass_index1
      x,y = k < n ? [i,k-i] : [k-n+1+i,n-1-i]
      add(delta,width,x,y)
    end
  end
end
 
def set_boards3(k)
  def add(d,w,sx,sy,x0,y0,x1,y1)
    if y0 == y1
      #horizontal
      x0,x1,y0,y1 = x1,x0,y1,y0 if x1 < x0
    else
      #vertical
      x0,x1,y0,y1 = x1,x0,y1,y0 if y1 < y0
    end
    p0 = [sx+x0*w-d, sy+y0*w-d]
    p1 = [sx+x1*w+d, sy+y1*w+d]
    p2 = [sx+x0*w-d, sy+y0*w+d]
    p3 = [sx+x1*w+d, sy+y1*w-d]
    @boards << [p0, p1]
    @boards << [p2, p3]
  end
  def sub(delta, max_width, sx, sy, n)
    width = max_width / (n-1)
 
    (n-2).times do |j|
      (n-2).times do |i|
        dir_i = Random.rand(j == 0 ? 4 : 3)
        dx,dy = [[-1,0],[0,1],[1,0],[0,-1]][dir_i]
        x0,y0 = i+1,j+1
        x1,y1 = x0+dx,y0+dy
        add(delta,width,sx,sy,x0,y0,x1,y1)
      end
    end
  end
  delta = 0.00001
  sub(delta, 1.0, 0.0, 0.0, k)
end
 
# Main functions
def grid_search(grid_n, taboo, beam_width)
  n = grid_n
  start_pos = [0,0]
  end_pos = [n-1,n-1]
 
  Search.new(n, taboo, start_pos, end_pos).calc(beam_width)
end
 
def make_sa_params
  grid_n = @grid_n
  e_func = lambda{|state|
    state.length.to_f
  }
  n_func = lambda{|state|
    return state if state.length < 3
    i = 1 + Random.rand(state.length-2)
    np = state[i]
    x,y = np
 
    100.times do
      nx,ny = Random.rand(grid_n), Random.rand(grid_n)
      if 0 <= nx && nx < grid_n && 0 <= ny && ny < grid_n
        tp = [nx,ny]
        if reducible?(state[i-1], tp) && reducible?(tp, state[i+1])
          np = tp
          break
        end
      end
    end
 
    new_state = state.dup
    new_state[i] = np
 
    if 0 <= i-2 && reducible?(new_state[i-2], np)
      new_state.delete_at(i-1)
      i -= 1
    end
    if i+2 < new_state.length && reducible?(np, new_state[i+2])
      new_state.delete_at(i+1)
    end
 
    new_state
  }
  t_func = lambda{|progress|
    a = 0.3
    Math.exp(progress*Math.log(a))
  }
  p_func = lambda{|e0,e1,t|
    if e0 >= e1
      1.0
    else
      k = 1.0
      Math.exp((e0-e1) / (k*t))
    end
  }
  max_iter = 1000
  goal_e = 0.0
 
  [e_func, n_func, t_func, p_func, max_iter, goal_e]
end
 
def reduce_by_sa(init_state)
  energy,neighbour,temparature,probability,max_iter,goal_e = make_sa_params
  sa = SimulatedAnealing.new(energy, neighbour, temparature, probability)
 
  sa.calc(init_state, max_iter, goal_e)
end
 
def display_answer(answer)
  puts answer.length
  puts answer.map{|e| "%.3f %.3f" % e}
end
 
def output_json(seed, prof, boards, intermediate, answer)
  require 'json'
  puts JSON.pretty_generate({"seed" => seed}.merge(prof.merge({"answer" => answer, "intermediate" => intermediate, "boards" => boards})))
end
 
def prof_exec(result, id_name, &f)
  start_time = Time.now
  f.call
  t = Time.now - start_time
  result[id_name] = t
end
 
# Run
@bounds = [[0.0,1.0],[0.0,1.0]]
@boards = []
@delta = 0.0001
@grid_n = 132
@grid_width = (1.0-@delta*2)/(@grid_n-1)
 
seed = Random.rand(1000)
seed = 13
prof = {}
taboo,found,route,reduced,final_state = nil,nil,nil,nil,nil
 
srand(seed)
 
prof_exec(prof, "set_boards") do
  set_boards2(6)
  set_boards3(31)
end
 
prof_exec(prof, "make_taboo") do
  taboo = make_taboo_fast(@grid_n)
end
 
prof_exec(prof, "grid_search") do
  found, route = grid_search(@grid_n, taboo, 1000)
end
 
unless found
  output_json(seed,prof,@boards,[],[])
  exit
end
 
prof_exec(prof, "reduce_greedy") do
  reduced = reduce(route)
end
 
prof_exec(prof, "reduce_by_sa") do
  final_state = []
  final_state = reduce_by_sa(reduced)
end
 
output_json(seed,
            prof,
            @boards,
            reduced.map{|e| grid_to_cartesian(e)},
            final_state.map{|e| grid_to_cartesian(e)})
#display_answer(final_state.map{|e| grid_to_cartesian(e)})

IyBVdGlsaXR5IGZ1bmN0aW9ucwpkZWYgaW50ZXJzZWN0KGxpbmUwLCBsaW5lMSkKICBkZWYgYXV4KGxpbmUwLGxpbmUxKQogICAgYSxiID0gbGluZTBbMF0KICAgIGMsZCA9IGxpbmUwWzFdCiAgICBlLGYgPSBiLWQsYy1hCiAgICBwMHgscDB5ID0gbGluZTFbMF1bMF0tYSwgbGluZTFbMF1bMV0tYgogICAgcDF4LHAxeSA9IGxpbmUxWzFdWzBdLWEsIGxpbmUxWzFdWzFdLWIKCiAgICAoZSpwMHgrZipwMHkpKihlKnAxeCtmKnAxeSkgPCAwLjAKICBlbmQKCiAgYXV4KGxpbmUwLGxpbmUxKSAmJiBhdXgobGluZTEsbGluZTApCmVuZAoKZGVmIGkycl94KGkpCiAgQGJvdW5kc1swXVswXSArIGkqQGdyaWRfd2lkdGggKyBAZGVsdGEKZW5kCgpkZWYgaTJyX3koaSkKICBAYm91bmRzWzFdWzBdICsgaSpAZ3JpZF93aWR0aCArIEBkZWx0YQplbmQKCmRlZiBncmlkX3RvX2NhcnRlc2lhbihwKQogIFtpMnJfeChwWzBdKSwgaTJyX3kocFsxXSldCmVuZAoKZGVmIHJlZHVjaWJsZT8ocDAscDEpCiAgbGluZSA9IFtncmlkX3RvX2NhcnRlc2lhbihwMCksIGdyaWRfdG9fY2FydGVzaWFuKHAxKV0KICBAYm9hcmRzLmVhY2ggZG8gfGJvYXJkfAogICAgcmV0dXJuIGZhbHNlIGlmIGludGVyc2VjdChsaW5lLCBib2FyZCkKICBlbmQKCiAgdHJ1ZQplbmQKCmRlZiByZWR1Y2Uoc3JjKQogIHIgPSBbXQogIGxvb3AgZG8KICAgIGlmIHNyYy5sZW5ndGggPCAzCiAgICAgIHIgPDwgc3JjWzBdCiAgICAgIHIgPDwgc3JjWzFdCiAgICAgIGJyZWFrCiAgICBlbHNlCiAgICAgIGlmIHJlZHVjaWJsZT8oc3JjWzBdLHNyY1syXSkKICAgICAgICBzcmMuZGVsZXRlX2F0KDEpCiAgICAgIGVsc2UKICAgICAgICByIDw8IHNyYy5zaGlmdAogICAgICBlbmQKICAgIGVuZAogIGVuZAoKICByCmVuZAoKZGVmIG1ha2VfdGFib28oZ3JpZF9uKQogIGRlZiB0ZW1wbGF0ZShncmlkX24sIHR5cGUsIHIpCiAgICAoZ3JpZF9uLXR5cGUpLnRpbWVzIGRvIHxqfAogICAgICAoZ3JpZF9uLSgxLXR5cGUpKS50aW1lcyBkbyB8aXwKICAgICAgICBwMCxwMSA9IHR5cGUgPT0gMCA/IFtbaSxqXSxbaSsxLGpdXSA6IFtbaSxqXSxbaSxqKzFdXQogICAgICAgIGxpbmUwID0gW2dyaWRfdG9fY2FydGVzaWFuKHAwKSxncmlkX3RvX2NhcnRlc2lhbihwMSldCiAgICAgICAgQGJvYXJkcy5lYWNoIGRvIHxsaW5lMXwKICAgICAgICAgIGlmIGludGVyc2VjdChsaW5lMCwgbGluZTEpCiAgICAgICAgICAgIHJbcDBdIHx8PSBbXQogICAgICAgICAgICByW3AxXSB8fD0gW10KICAgICAgICAgICAgcltwMF0gPDwgcDEKICAgICAgICAgICAgcltwMV0gPDwgcDAKICAgICAgICAgIGVuZAogICAgICAgIGVuZAogICAgICBlbmQKICAgIGVuZAogIGVuZAogIHIgPSB7fQogIHRlbXBsYXRlKGdyaWRfbiwgMCwgcikKICB0ZW1wbGF0ZShncmlkX24sIDEsIHIpCgogIHIKZW5kCgpkZWYgbWFrZV90YWJvb19mYXN0KGdyaWRfbikKICBkZWYgdzJnX3gocikKICAgIChyIC0gQGJvdW5kc1swXVswXSAtIEBkZWx0YSkgLyBAZ3JpZF93aWR0aAogIGVuZAogIGRlZiB3MmdfeShyKQogICAgKHIgLSBAYm91bmRzWzFdWzBdIC0gQGRlbHRhKSAvIEBncmlkX3dpZHRoCiAgZW5kCiAgZGVmIGNhcnRlc2lhbl90b19ncmlkKHAwKQogICAgW3cyZ194KHAwWzBdKSwgdzJnX3kocDBbMV0pXQogIGVuZAogIGRlZiBsaW5lX3RvX2NvdmVycmFuZ2UobGluZSkKICAgIHgwLHkwID0gY2FydGVzaWFuX3RvX2dyaWQobGluZVswXSkKICAgIHgxLHkxID0gY2FydGVzaWFuX3RvX2dyaWQobGluZVsxXSkKICAgIHhfbWluLHhfbWF4ID0gW3gwLHgxXS5taW5tYXgKICAgIHlfbWluLHlfbWF4ID0gW3kwLHkxXS5taW5tYXgKICAgIFtbeF9taW4uZmxvb3IsIHhfbWF4LmNlaWxdLFt5X21pbi5mbG9vciwgeV9tYXguY2VpbF1dCiAgZW5kCiAgZGVmIGFkZChyLHAwLHAxKQogICAgcltwMF0gfHw9IFtdCiAgICByW3AxXSB8fD0gW10KICAgIHJbcDBdIDw8IHAxCiAgICByW3AxXSA8PCBwMAogIGVuZAogIHIgPSB7fQogIEBib2FyZHMuZWFjaCBkbyB8YnwKICAgIGxpbmUgPSBbY2FydGVzaWFuX3RvX2dyaWQoYlswXSksIGNhcnRlc2lhbl90b19ncmlkKGJbMV0pXQogICAgeF9yYW5nZSx5X3JhbmdlID0gbGluZV90b19jb3ZlcnJhbmdlKGIpCiAgICB4ZCA9IGxpbmVbMV1bMF0tbGluZVswXVswXQogICAgeWQgPSBsaW5lWzFdWzFdLWxpbmVbMF1bMV0KCiAgICBpZiB4ZCAhPSAwLjAKICAgICAgaSA9IHhfcmFuZ2VbMF0gKyAxCiAgICAgIGkgPSAwIGlmIGkgPCAwCiAgICAgIHdoaWxlIGkgPCB4X3JhbmdlWzFdCiAgICAgICAgeV9mID0geWQgKiAoaS50b19mLWxpbmVbMF1bMF0pIC8geGQgKyBsaW5lWzBdWzFdCiAgICAgICAgeSA9IHlfZi5mbG9vcgogICAgICAgIGFkZChyLFtpLHldLFtpLHkrMV0pCiAgICAgICAgaSArPSAxCiAgICAgIGVuZAogICAgZW5kCgogICAgaWYgeWQgIT0gMC4wCiAgICAgIGkgPSB5X3JhbmdlWzBdICsgMQogICAgICBpID0gMCBpZiBpIDwgMAogICAgICB3aGlsZSBpIDwgeV9yYW5nZVsxXQogICAgICAgIHhfZiA9IHhkICogKGkudG9fZi1saW5lWzBdWzFdKSAvIHlkICsgbGluZVswXVswXQogICAgICAgIHggPSB4X2YuZmxvb3IKICAgICAgICBhZGQocixbeCxpXSxbeCsxLGldKQogICAgICAgIGkgKz0gMQogICAgICBlbmQKICAgIGVuZAogIGVuZAoKICByCmVuZAoKIyBTZWFyY2ggb24gR3JpZCAoQmVhbSBTZWFyY2gpIERlZmluaXRpb24KY2xhc3MgU2VhcmNoCiAgZGVmIGluaXRpYWxpemUoZ3JpZF9uLCB0YWJvbywgc3RhcnRfcG9zLCB0YXJnZXRfcG9zKQogICAgQGdyaWRfbiA9IGdyaWRfbgogICAgQHRhYm9vID0gdGFib28KICAgIEBzdGFydF9wb3MsIEB0YXJnZXRfcG9zID0gc3RhcnRfcG9zLCB0YXJnZXRfcG9zCiAgICBAaGFzX2Fuc3dlciA9IGZhbHNlCiAgICBAYW5zd2VyID0gbmlsCiAgZW5kCiAgZGVmIGgocG9zKQogICAgIyBNYW5oYXR0YW4gZGlzdGFuY2UKICAgIChAdGFyZ2V0X3Bvc1swXS1wb3NbMF0pLmFicysoQHRhcmdldF9wb3NbMV0tcG9zWzFdKS5hYnMKICBlbmQKICBkZWYgc3VjY2Vzc29ycyhwb3MpCiAgICByID0gW10KICAgIFtbMSwwXSxbMCwxXSxbLTEsMF0sWzAsLTFdXS5lYWNoIGRvIHxkfAogICAgICBpLGogPSBwb3NbMF0rZFswXSwgcG9zWzFdK2RbMV0KICAgICAgbmV4dCB1bmxlc3MgMCA8PSBpICYmIGkgPCBAZ3JpZF9uICYmIDAgPD0gaiAmJiBqIDwgQGdyaWRfbgogICAgICBzdWNjID0gW2ksal0KICAgICAgciA8PCBzdWNjIHVubGVzcyBAdGFib29bcG9zXSAmJiBAdGFib29bcG9zXS5pbmNsdWRlPyhzdWNjKQogICAgZW5kCgogICAgcgogIGVuZAogIGRlZiBjYWxjKGJlYW13aWR0aCkKICAgIHN0YXRlcyA9IFtAc3RhcnRfcG9zXQogICAgaGlzdG9yeSA9IHt9CiAgICB0bXAgPSBbXQogICAgbG9vcCBkbwogICAgICBicmVhayB1bmxlc3MgMCA8IHN0YXRlcy5sZW5ndGgKCiAgICAgIHN0YXRlcy5lYWNoIGRvIHxjdXJfcG9zfAogICAgICAgIHN1Y2NzID0gW10KICAgICAgICBzdWNjZXNzb3JzKGN1cl9wb3MpLmVhY2ggZG8gfHN1Y2N8CiAgICAgICAgICBpZiBzdWNjID09IEB0YXJnZXRfcG9zCiAgICAgICAgICAgIHJlc3VsdCA9IFtAdGFyZ2V0X3BvcywgY3VyX3Bvc10KICAgICAgICAgICAgcG9zID0gY3VyX3BvcwogICAgICAgICAgICB3aGlsZSBwcmV2X3BvcyA9IGhpc3RvcnlbcG9zXQogICAgICAgICAgICAgIHJlc3VsdCA8PCBwcmV2X3BvcwogICAgICAgICAgICAgIGJyZWFrIGlmIHByZXZfcG9zID09IEBzdGFydF9wb3MKICAgICAgICAgICAgICBwb3MgPSBwcmV2X3BvcwogICAgICAgICAgICBlbmQKICAgICAgICAgICAgcmV0dXJuIFt0cnVlLCByZXN1bHQucmV2ZXJzZV0KICAgICAgICAgIGVuZAogICAgICAgICAgdW5sZXNzIGhpc3Rvcnlbc3VjY10KICAgICAgICAgICAgaGlzdG9yeVtzdWNjXSA9IGN1cl9wb3MKICAgICAgICAgICAgc3VjY3MgPDwgW2goc3VjYyksIHN1Y2NdCiAgICAgICAgICBlbmQKICAgICAgICBlbmQKICAgICAgICB0bXAuY29uY2F0KHN1Y2NzKQogICAgICBlbmQKCiAgICAgIHRtcC5zb3J0IQogICAgICBzdGF0ZXMuY2xlYXIKCiAgICAgIG4gPSBbdG1wLmxlbmd0aCwgYmVhbXdpZHRoXS5taW4KICAgICAgbi50aW1lcyBkbyB8aXwKICAgICAgICBzdGF0ZXMgPDwgdG1wW2ldWzFdCiAgICAgIGVuZAoKICAgICAgdG1wLmNsZWFyCiAgICBlbmQKCiAgICBbZmFsc2UsIG5pbF0KICBlbmQKZW5kCgojIFNpbXVsYXRlZCBBbmVhbGluZyBEZWZpbml0aW9uCmNsYXNzIFNpbXVsYXRlZEFuZWFsaW5nCiAgZGVmIGluaXRpYWxpemUoZW5lcmd5X2Z1bmMsIG5laWdoYm91cl9mdW5jLCB0ZW1wYXJhdHVyZV9mdW5jLCBwcm9iYWJsaXR5X2Z1bmMpCiAgICBAZW5lcmd5ID0gZW5lcmd5X2Z1bmMgIyBzdGF0ZSAtPiBmbG9hdChlbmVyZ3kpCiAgICBAbmVpZ2hib3VyID0gbmVpZ2hib3VyX2Z1bmMgIyBzdGF0ZSAtPiBzdGF0ZQogICAgQHRlbXBhcmF0dXJlID0gdGVtcGFyYXR1cmVfZnVuYyAjIGZsb2F0KHByb2dyZXNzIGRlZ3JlZSkgLT4gZmxvYXQodGVtcGFyYXR1cmUpCiAgICBAcHJvYmFiaWxpdHkgPSBwcm9iYWJsaXR5X2Z1bmMgIyBmbG9hdChlbmVyZ3lfc3JjKSAtPiBmbG9hdChlbmVyZ3lfZHN0KSAtPiB0ZW1wYXJhdHVyZSAtPiBmbG9hdChwcm9iYWJsaXR5KQogIGVuZAogIGRlZiBjYWxjKHN0YXJ0X3N0YXRlLCBtYXhfaXRlciwgZ29hbF9lbmVyZ3kpCiAgICBzdGF0ZSA9IHN0YXJ0X3N0YXRlCiAgICBlID0gQGVuZXJneS5jYWxsKHN0YXRlKQogICAgYmVzdF9zdGF0ZSA9IHN0YXRlCiAgICBiZXN0X2UgPSBlCiAgICBtYXhfaXRlci50aW1lcyBkbyB8aXRlcnwKICAgICAgbmV4dF9zdGF0ZSA9IEBuZWlnaGJvdXIuY2FsbChzdGF0ZSkKICAgICAgbmV4dF9lID0gQGVuZXJneS5jYWxsKG5leHRfc3RhdGUpCiAgICAgIGlmIG5leHRfZSA8PSBiZXN0X2UKICAgICAgICBiZXN0X3N0YXRlID0gbmV4dF9zdGF0ZQogICAgICAgIGJlc3RfZSA9IG5leHRfZQogICAgICAgIGlmIGJlc3RfZSA8PSBnb2FsX2VuZXJneQogICAgICAgICAgcmV0dXJuIGJlc3Rfc3RhdGUKICAgICAgICBlbmQKICAgICAgZW5kCgogICAgICB0ID0gQHRlbXBhcmF0dXJlLmNhbGwoaXRlci50b19mIC8gbWF4X2l0ZXIpCiAgICAgIHByb2IgPSBAcHJvYmFiaWxpdHkuY2FsbChlLCBuZXh0X2UsIHQpCiAgICAgIGlmIFJhbmRvbS5yYW5kIDw9IHByb2IKICAgICAgICBzdGF0ZSA9IG5leHRfc3RhdGUKICAgICAgICBlID0gbmV4dF9lCiAgICAgIGVuZAogICAgZW5kCgogICAgYmVzdF9zdGF0ZQogIGVuZAplbmQKCiMgU2V0dGluZyBmdW5jdGlvbnMKZGVmIHNldF9ib2FyZHMobikgIyBwYXJhbGxlbCB6aWd6YWcgcGF0dGVybgogIGR5ID0gKEBib3VuZHNbMV1bMV0gLSBAYm91bmRzWzFdWzBdKSAvIChuKzEpCgogIG4udGltZXMgZG8gfGl8CiAgICB5MCA9IEBib3VuZHNbMV1bMF0KICAgIHl2YWwgPSB5MCtkeSooaSsxKQogICAgYm9hcmQgPQogICAgICBpZiBpJTIgPT0gMAogICAgICAgIFtbMC4wLCB5dmFsXSwgWzAuNjYsIHl2YWxdXQogICAgICBlbHNlCiAgICAgICAgW1swLjMzLCB5dmFsXSwgWzEuMCwgeXZhbF1dCiAgICAgIGVuZAogICAgQGJvYXJkcyA8PCBib2FyZAogIGVuZAplbmQKCmRlZiBzZXRfYm9hcmRzMihuKSAjIGRpYWdvbmFsIHppZ3phZyBwYXR0ZXJuCiAgZGVmIGFkZChkZWx0YSx3aWR0aCx4LHkpCiAgICBwMCA9IFt4KndpZHRoLWRlbHRhLCB5KndpZHRoK2RlbHRhXQogICAgcDEgPSBbKHgrMSkqd2lkdGgrZGVsdGEsICh5LTEpKndpZHRoLWRlbHRhXQogICAgQGJvYXJkcyA8PCBbcDAsIHAxXQogIGVuZAogIGRlbHRhID0gMC4wMDAwMQogIHdpZHRoID0gMS4wIC8gKG4tMSkKCiAgKDIuLigyKihuLTIpKSkuZWFjaCBkbyB8a3wKICAgIGl0ZXJfbnVtID0gayA8IG4gPyBrIDogKDIqKG4tMSktaykKICAgIHBhc3NfaW5kZXgwID0gUmFuZG9tLnJhbmQoaXRlcl9udW0pCiAgICBwYXNzX2luZGV4MSA9IFJhbmRvbS5yYW5kKGl0ZXJfbnVtKQogICAgaXRlcl9udW0udGltZXMgZG8gfGl8CiAgICAgIG5leHQgaWYgaSA9PSBwYXNzX2luZGV4MCB8fCBpID09IHBhc3NfaW5kZXgxCiAgICAgIHgseSA9IGsgPCBuID8gW2ksay1pXSA6IFtrLW4rMStpLG4tMS1pXQogICAgICBhZGQoZGVsdGEsd2lkdGgseCx5KQogICAgZW5kCiAgZW5kCmVuZAoKZGVmIHNldF9ib2FyZHMzKGspCiAgZGVmIGFkZChkLHcsc3gsc3kseDAseTAseDEseTEpCiAgICBpZiB5MCA9PSB5MQogICAgICAjaG9yaXpvbnRhbAogICAgICB4MCx4MSx5MCx5MSA9IHgxLHgwLHkxLHkwIGlmIHgxIDwgeDAKICAgIGVsc2UKICAgICAgI3ZlcnRpY2FsCiAgICAgIHgwLHgxLHkwLHkxID0geDEseDAseTEseTAgaWYgeTEgPCB5MAogICAgZW5kCiAgICBwMCA9IFtzeCt4MCp3LWQsIHN5K3kwKnctZF0KICAgIHAxID0gW3N4K3gxKncrZCwgc3kreTEqdytkXQogICAgcDIgPSBbc3greDAqdy1kLCBzeSt5MCp3K2RdCiAgICBwMyA9IFtzeCt4MSp3K2QsIHN5K3kxKnctZF0KICAgIEBib2FyZHMgPDwgW3AwLCBwMV0KICAgIEBib2FyZHMgPDwgW3AyLCBwM10KICBlbmQKICBkZWYgc3ViKGRlbHRhLCBtYXhfd2lkdGgsIHN4LCBzeSwgbikKICAgIHdpZHRoID0gbWF4X3dpZHRoIC8gKG4tMSkKCiAgICAobi0yKS50aW1lcyBkbyB8anwKICAgICAgKG4tMikudGltZXMgZG8gfGl8CiAgICAgICAgZGlyX2kgPSBSYW5kb20ucmFuZChqID09IDAgPyA0IDogMykKICAgICAgICBkeCxkeSA9IFtbLTEsMF0sWzAsMV0sWzEsMF0sWzAsLTFdXVtkaXJfaV0KICAgICAgICB4MCx5MCA9IGkrMSxqKzEKICAgICAgICB4MSx5MSA9IHgwK2R4LHkwK2R5CiAgICAgICAgYWRkKGRlbHRhLHdpZHRoLHN4LHN5LHgwLHkwLHgxLHkxKQogICAgICBlbmQKICAgIGVuZAogIGVuZAogIGRlbHRhID0gMC4wMDAwMQogIHN1YihkZWx0YSwgMS4wLCAwLjAsIDAuMCwgaykKZW5kCgojIE1haW4gZnVuY3Rpb25zCmRlZiBncmlkX3NlYXJjaChncmlkX24sIHRhYm9vLCBiZWFtX3dpZHRoKQogIG4gPSBncmlkX24KICBzdGFydF9wb3MgPSBbMCwwXQogIGVuZF9wb3MgPSBbbi0xLG4tMV0KCiAgU2VhcmNoLm5ldyhuLCB0YWJvbywgc3RhcnRfcG9zLCBlbmRfcG9zKS5jYWxjKGJlYW1fd2lkdGgpCmVuZAoKZGVmIG1ha2Vfc2FfcGFyYW1zCiAgZ3JpZF9uID0gQGdyaWRfbgogIGVfZnVuYyA9IGxhbWJkYXt8c3RhdGV8CiAgICBzdGF0ZS5sZW5ndGgudG9fZgogIH0KICBuX2Z1bmMgPSBsYW1iZGF7fHN0YXRlfAogICAgcmV0dXJuIHN0YXRlIGlmIHN0YXRlLmxlbmd0aCA8IDMKICAgIGkgPSAxICsgUmFuZG9tLnJhbmQoc3RhdGUubGVuZ3RoLTIpCiAgICBucCA9IHN0YXRlW2ldCiAgICB4LHkgPSBucAoKICAgIDEwMC50aW1lcyBkbwogICAgICBueCxueSA9IFJhbmRvbS5yYW5kKGdyaWRfbiksIFJhbmRvbS5yYW5kKGdyaWRfbikKICAgICAgaWYgMCA8PSBueCAmJiBueCA8IGdyaWRfbiAmJiAwIDw9IG55ICYmIG55IDwgZ3JpZF9uCiAgICAgICAgdHAgPSBbbngsbnldCiAgICAgICAgaWYgcmVkdWNpYmxlPyhzdGF0ZVtpLTFdLCB0cCkgJiYgcmVkdWNpYmxlPyh0cCwgc3RhdGVbaSsxXSkKICAgICAgICAgIG5wID0gdHAKICAgICAgICAgIGJyZWFrCiAgICAgICAgZW5kCiAgICAgIGVuZAogICAgZW5kCgogICAgbmV3X3N0YXRlID0gc3RhdGUuZHVwCiAgICBuZXdfc3RhdGVbaV0gPSBucAoKICAgIGlmIDAgPD0gaS0yICYmIHJlZHVjaWJsZT8obmV3X3N0YXRlW2ktMl0sIG5wKQogICAgICBuZXdfc3RhdGUuZGVsZXRlX2F0KGktMSkKICAgICAgaSAtPSAxCiAgICBlbmQKICAgIGlmIGkrMiA8IG5ld19zdGF0ZS5sZW5ndGggJiYgcmVkdWNpYmxlPyhucCwgbmV3X3N0YXRlW2krMl0pCiAgICAgIG5ld19zdGF0ZS5kZWxldGVfYXQoaSsxKQogICAgZW5kCgogICAgbmV3X3N0YXRlCiAgfQogIHRfZnVuYyA9IGxhbWJkYXt8cHJvZ3Jlc3N8CiAgICBhID0gMC4zCiAgICBNYXRoLmV4cChwcm9ncmVzcypNYXRoLmxvZyhhKSkKICB9CiAgcF9mdW5jID0gbGFtYmRhe3xlMCxlMSx0fAogICAgaWYgZTAgPj0gZTEKICAgICAgMS4wCiAgICBlbHNlCiAgICAgIGsgPSAxLjAKICAgICAgTWF0aC5leHAoKGUwLWUxKSAvIChrKnQpKQogICAgZW5kCiAgfQogIG1heF9pdGVyID0gMTAwMAogIGdvYWxfZSA9IDAuMAoKICBbZV9mdW5jLCBuX2Z1bmMsIHRfZnVuYywgcF9mdW5jLCBtYXhfaXRlciwgZ29hbF9lXQplbmQKCmRlZiByZWR1Y2VfYnlfc2EoaW5pdF9zdGF0ZSkKICBlbmVyZ3ksbmVpZ2hib3VyLHRlbXBhcmF0dXJlLHByb2JhYmlsaXR5LG1heF9pdGVyLGdvYWxfZSA9IG1ha2Vfc2FfcGFyYW1zCiAgc2EgPSBTaW11bGF0ZWRBbmVhbGluZy5uZXcoZW5lcmd5LCBuZWlnaGJvdXIsIHRlbXBhcmF0dXJlLCBwcm9iYWJpbGl0eSkKCiAgc2EuY2FsYyhpbml0X3N0YXRlLCBtYXhfaXRlciwgZ29hbF9lKQplbmQKCmRlZiBkaXNwbGF5X2Fuc3dlcihhbnN3ZXIpCiAgcHV0cyBhbnN3ZXIubGVuZ3RoCiAgcHV0cyBhbnN3ZXIubWFwe3xlfCAiJS4zZiAlLjNmIiAlIGV9CmVuZAoKZGVmIG91dHB1dF9qc29uKHNlZWQsIHByb2YsIGJvYXJkcywgaW50ZXJtZWRpYXRlLCBhbnN3ZXIpCiAgcmVxdWlyZSAnanNvbicKICBwdXRzIEpTT04ucHJldHR5X2dlbmVyYXRlKHsic2VlZCIgPT4gc2VlZH0ubWVyZ2UocHJvZi5tZXJnZSh7ImFuc3dlciIgPT4gYW5zd2VyLCAiaW50ZXJtZWRpYXRlIiA9PiBpbnRlcm1lZGlhdGUsICJib2FyZHMiID0+IGJvYXJkc30pKSkKZW5kCgpkZWYgcHJvZl9leGVjKHJlc3VsdCwgaWRfbmFtZSwgJmYpCiAgc3RhcnRfdGltZSA9IFRpbWUubm93CiAgZi5jYWxsCiAgdCA9IFRpbWUubm93IC0gc3RhcnRfdGltZQogIHJlc3VsdFtpZF9uYW1lXSA9IHQKZW5kCgojIFJ1bgpAYm91bmRzID0gW1swLjAsMS4wXSxbMC4wLDEuMF1dCkBib2FyZHMgPSBbXQpAZGVsdGEgPSAwLjAwMDEKQGdyaWRfbiA9IDEzMgpAZ3JpZF93aWR0aCA9ICgxLjAtQGRlbHRhKjIpLyhAZ3JpZF9uLTEpCgpzZWVkID0gUmFuZG9tLnJhbmQoMTAwMCkKc2VlZCA9IDEzCnByb2YgPSB7fQp0YWJvbyxmb3VuZCxyb3V0ZSxyZWR1Y2VkLGZpbmFsX3N0YXRlID0gbmlsLG5pbCxuaWwsbmlsLG5pbAoKc3JhbmQoc2VlZCkKCnByb2ZfZXhlYyhwcm9mLCAic2V0X2JvYXJkcyIpIGRvCiAgc2V0X2JvYXJkczIoNikKICBzZXRfYm9hcmRzMygzMSkKZW5kCgpwcm9mX2V4ZWMocHJvZiwgIm1ha2VfdGFib28iKSBkbwogIHRhYm9vID0gbWFrZV90YWJvb19mYXN0KEBncmlkX24pCmVuZAoKcHJvZl9leGVjKHByb2YsICJncmlkX3NlYXJjaCIpIGRvCiAgZm91bmQsIHJvdXRlID0gZ3JpZF9zZWFyY2goQGdyaWRfbiwgdGFib28sIDEwMDApCmVuZAoKdW5sZXNzIGZvdW5kCiAgb3V0cHV0X2pzb24oc2VlZCxwcm9mLEBib2FyZHMsW10sW10pCiAgZXhpdAplbmQKCnByb2ZfZXhlYyhwcm9mLCAicmVkdWNlX2dyZWVkeSIpIGRvCiAgcmVkdWNlZCA9IHJlZHVjZShyb3V0ZSkKZW5kCgpwcm9mX2V4ZWMocHJvZiwgInJlZHVjZV9ieV9zYSIpIGRvCiAgZmluYWxfc3RhdGUgPSBbXQogIGZpbmFsX3N0YXRlID0gcmVkdWNlX2J5X3NhKHJlZHVjZWQpCmVuZAoKb3V0cHV0X2pzb24oc2VlZCwKICAgICAgICAgICAgcHJvZiwKICAgICAgICAgICAgQGJvYXJkcywKICAgICAgICAgICAgcmVkdWNlZC5tYXB7fGV8IGdyaWRfdG9fY2FydGVzaWFuKGUpfSwKICAgICAgICAgICAgZmluYWxfc3RhdGUubWFwe3xlfCBncmlkX3RvX2NhcnRlc2lhbihlKX0pCiNkaXNwbGF5X2Fuc3dlcihmaW5hbF9zdGF0ZS5tYXB7fGV8IGdyaWRfdG9fY2FydGVzaWFuKGUpfSk=