






"""simple docstring"""







from copy import deepcopy







class  lowerCamelCase__ :






    def __init__(			self     ,A = None     ,A = None ):

          if arr is None and size is not None:
                UpperCAmelCase          =	size
                UpperCAmelCase          =	[0] * size
          elif arr is not None:
                self.init(A )
          else:
                raise ValueError("""Either arr or size must be specified""" )






    def     _UpperCamelCase							(			self     ,A ):
          UpperCAmelCase          =	len(A )
          UpperCAmelCase          =	deepcopy(A )
          for i in range(1     ,self.size ):
                UpperCAmelCase          =	self.next_(A )
                if j < self.size:
                      self.tree[j] += self.tree[i]






    def     _UpperCamelCase							(			self ):
          UpperCAmelCase          =	self.tree[:]
          for i in range(self.size - 1     ,0     ,-1 ):
                UpperCAmelCase          =	self.next_(A )
                if j < self.size:
                      arr[j] -= arr[i]
          return arr






    @staticmethod
    def     _UpperCamelCase							(			A ):
          return index + (index & (-index))






    @staticmethod
    def     _UpperCamelCase							(			A ):
          return index - (index & (-index))






    def     _UpperCamelCase							(			self     ,A     ,A ):
          if index == 0:
                self.tree[0] += value
                return
          while index < self.size:
                self.tree[index] += value
                UpperCAmelCase          =	self.next_(A )






    def     _UpperCamelCase							(			self     ,A     ,A ):
          self.add(A     ,value - self.get(A ) )






    def     _UpperCamelCase							(			self     ,A ):
          if right == 0:
                return 0
          UpperCAmelCase          =	self.tree[0]
          right -= 1  # make right inclusive
          while right > 0:
                result += self.tree[right]
                UpperCAmelCase          =	self.prev(A )
          return result






    def     _UpperCamelCase							(			self     ,A     ,A ):
          return self.prefix(A ) - self.prefix(A )






    def     _UpperCamelCase							(			self     ,A ):
          return self.query(A     ,index + 1 )






    def     _UpperCamelCase							(			self     ,A ):
          value -= self.tree[0]
          if value < 0:
                return -1

          UpperCAmelCase          =	1  # Largest power of 2 <= size
          while j * 2 < self.size:
                j *= 2

          UpperCAmelCase          =	0

          while j > 0:
                if i + j < self.size and self.tree[i + j] <= value:
                      value -= self.tree[i + j]
                      i += j
                j //= 2
          return i


if __name__ == "__main__":
  import doctest

  doctest.testmod()











"""simple docstring"""







_UpperCamelCase					      =  [4, 1, 7, 4, 2, 6, 4, 1, 5, 3, 7, 5]
_UpperCamelCase					      =  [3, 7, 7, 4, 2, 6, 4, 1, 5, 3, 7, 5]
_UpperCamelCase					      =  {
    0: """Sunday""",
    1: """Monday""",
    2: """Tuesday""",
    3: """Wednesday""",
    4: """Thursday""",
    5: """Friday""",
    6: """Saturday""",
}

def _a			(		_snake_case				,	_snake_case				,	_snake_case							):







      """simple docstring"""






      assert len(str(_snake_case							)							) > 2, "year should be in YYYY format"
      assert 1 <= month <= 12, "month should be between 1 to 12"
      assert 1 <= day <= 31, "day should be between 1 to 31"

      # Doomsday algorithm:
      UpperCAmelCase          =	year // 100
      UpperCAmelCase          =	(5 * (century % 4) + 2) % 7
      UpperCAmelCase          =	year % 100
      UpperCAmelCase          =	centurian % 12
      UpperCAmelCase          =	(
          (centurian // 12) + centurian_m + (centurian_m // 4) + century_anchor
      ) % 7
      UpperCAmelCase          =	(
          DOOMSDAY_NOT_LEAP[month - 1]
          if (year % 4 != 0) or (centurian == 0 and (year % 400) == 0)
          else DOOMSDAY_LEAP[month - 1]
      )
      UpperCAmelCase          =	(dooms_day + day - day_anchor) % 7
      return WEEK_DAY_NAMES[week_day]


if __name__ == "__main__":
  import doctest

  doctest.testmod()



