import fractions
import operator

def clamp(value,a,b):
  minimum = min(a,b)
  maximum = max(a,b)
  return max(min(maximum,value),minimum)

def divout(a,b):
  div,mod = divmod(a,b)
  if (div >= 0) and (mod != 0):
    div = div+1
  return div

class Range(object):
  class Range_iterator(object):
    def __init__(self,start,step,length):
      self.start = start
      self.step = step
      self.length = length
      self.index = 0
    def __iter__(self):
      return self
    def __next__(self):
      if self.index == self.length:
        raise StopIteration
      value = (self.step * self.index) + self.start
      self.index = self.index + 1
      return value

  def __init__(self,start,stop=None,step=None):
    if stop is None:
      stop = start
      start = 0
    if step is None:
      step = 1
    if step == 0:
      message = "{0}() \"step\" argument must not be zero".format(self.__class__.__name__)
      raise ValueError(message)
    self.start = operator.index(start)
    self.stop = operator.index(stop)
    self.step = operator.index(step)

  def __repr__(self):
    message = "{0}({1}, {2}, {3})".format(
        self.__class__.__name__,
        self.start,self.stop,
        self.step)
    return(message)

  def __len__(self):
    length = divout(self.stop - self.start,self.step)
    if length>=0:
      return length
    else:
      return 0

  def __iter__(self):
    return self.Range_iterator(self.start,self.step,len(self))

  def __getitem__(self,key):
    name_class  = self.__class__.__name__
    name_key    = key.__class__.__name__
    error_index = "{0} object index out of range"
    error_value = "{0} step cannot be zero"
    error_type  = "{0} indices must be integers or slices, not {1}"
    error_type_slice = "{0} indices must be integers or None or have an __index__ method"
    if isinstance(key,int):
      length = len(self)
      if key>=0:
        if key >= length:
          raise IndexError( error_index.format(name_class) )
        return (self.step * key) + self.start
      else:
        if abs(key) > length:
          raise IndexError( error_index.format(name_class) )
        return (self.step * (key + length)) + self.start
    elif isinstance(key,slice):
      try:
        key_start = key.start if (key.start is None) else operator.index(key.start)
        key_stop  = key.stop  if (key.stop  is None) else operator.index(key.stop)
        key_step  = key.step  if (key.step  is None) else operator.index(key.step)
      except TypeError:
        raise TypeError( error_type_slice.format(name_key) )
      if key_step is None:
        key_step = 1
      elif key.step == 0:
        raise ValueError( error_value.format(name_key) )
      length = len(self)

      if key_start is None:
        if key_step<0:
          key_start = length - 1
        else:
          key_start = 0
      else:
        if key_start<0:
          key_start = key_start + length
        if key_step<0:
          key_start = clamp(key_start,-1,length-1)
        else:
          key_start = clamp(key_start,0,length)

      if key_stop is None:
        if key_step<0:
          key_stop = -1
        else:
          key_stop = length
      else:
        if key_stop<0:
          key_stop = key_stop + length
        if key_step<0:
          key_stop = clamp(key_stop,-1,key_start)
        else:
          key_stop = clamp(key_stop,key_start,length)

      start = (self.step * key_start) + self.start
      stop  = (self.step * key_stop)  + self.start
      step  = self.step * key_step
      return Range(start,stop,step)
    else:
      raise TypeError( error_type.format(name_class, name_key) )

  def max(self):
    length = len(self)
    if length == 0:
      return None
    if self.step<0:
      return self[0]
    else:
      return self[length-1]

  def min(self):
    length = len(self)
    if length == 0:
      return None
    if self.step<0:
      return self[length-1]
    else:
      return self[0]

  def __contains__(self,item):
    if isinstance(item,int):
      return (  (item<self.stop                   ) and
                (item>=self[0]                    ) and
                (((item-self.start)%self.step)==0 ) )
    else:
      return False

  def __eq__(self,other):
    if not isinstance(other,type(self)):
      return NotImplemented
    l1 = len(self)
    l2 = len(other)
    if (0 == l1 == l2):
      return True
    if (self.start == other.start):
      if (1 == l1 == l2):
        return True
      if (l1 == l2) and (self.step == other.step):
        return True
    return False

  def overlap(self,other):
    if not isinstance(other,type(self)):
      return NotImplemented
    return (max(self.min(),other.min()),
            min(self.max(),other.max()))

  def __and__(self,other):
    if not isinstance(other,type(self)):
      return NotImplemented
    l1 = len(self)
    l2 = len(other)
    if (l1>0) and (l2>0):
      le,re = self.overlap(other)
      if (le<=re):
        gcd = fractions.gcd(self.step,other.step)
        if ((self.start-other.start)%gcd==0):
          lcm = (self.step*other.step)//gcd
          idx = (self.start-other.start)//gcd
          pt  = (self.step*idx) + self.start
          offset = (pt%lcm)
          le = le + (lcm - (((le-offset-1)%lcm)+1))
          re = re - ((re-offset)%lcm)
          if (le<=re):
            return Range(le,re+lcm,lcm)
    return Range(0,0,1)

  def intersection(self,other):
    return self & other