text: # uncompyle6 version 2.9.10
  # Python bytecode 2.7 (62211)
  # Decompiled from: Python 3.6.0b2 (default, Oct 11 2016, 05:27:10) 
  # [GCC 6.2.0 20161005]
  # Embedded file name: bisect.py
  """Bisection algorithms."""
  
  def insort_right(a, x, lo=0, hi=None):
      """Insert item x in list a, and keep it sorted assuming a is sorted.
      
      If x is already in a, insert it to the right of the rightmost x.
      
      Optional args lo (default 0) and hi (default len(a)) bound the
      slice of a to be searched.
      """
      if lo < 0:
          raise ValueError('lo must be non-negative')
      if hi is None:
          hi = len(a)
      while lo < hi:
          mid = (lo + hi) // 2
          if x < a[mid]:
              hi = mid
          else:
              lo = mid + 1
  
      a.insert(lo, x)
      return
  
  
  insort = insort_right
  
  def bisect_right(a, x, lo=0, hi=None):
      """Return the index where to insert item x in list a, assuming a is sorted.
      
      The return value i is such that all e in a[:i] have e <= x, and all e in
      a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
      insert just after the rightmost x already there.
      
      Optional args lo (default 0) and hi (default len(a)) bound the
      slice of a to be searched.
      """
      if lo < 0:
          raise ValueError('lo must be non-negative')
      if hi is None:
          hi = len(a)
      while lo < hi:
          mid = (lo + hi) // 2
          if x < a[mid]:
              hi = mid
          else:
              lo = mid + 1
  
      return lo
  
  
  bisect = bisect_right
  
  def insort_left(a, x, lo=0, hi=None):
      """Insert item x in list a, and keep it sorted assuming a is sorted.
      
      If x is already in a, insert it to the left of the leftmost x.
      
      Optional args lo (default 0) and hi (default len(a)) bound the
      slice of a to be searched.
      """
      if lo < 0:
          raise ValueError('lo must be non-negative')
      if hi is None:
          hi = len(a)
      while lo < hi:
          mid = (lo + hi) // 2
          if a[mid] < x:
              lo = mid + 1
          else:
              hi = mid
  
      a.insert(lo, x)
      return
  
  
  def bisect_left(a, x, lo=0, hi=None):
      """Return the index where to insert item x in list a, assuming a is sorted.
      
      The return value i is such that all e in a[:i] have e < x, and all e in
      a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
      insert just before the leftmost x already there.
      
      Optional args lo (default 0) and hi (default len(a)) bound the
      slice of a to be searched.
      """
      if lo < 0:
          raise ValueError('lo must be non-negative')
      if hi is None:
          hi = len(a)
      while lo < hi:
          mid = (lo + hi) // 2
          if a[mid] < x:
              lo = mid + 1
          else:
              hi = mid
  
      return lo
  
  
  try:
      from _bisect import *
  except ImportError:
      pass