






"""simple docstring"""





class    __lowerCamelCase    :

   def __init__(					self      )		->       Any:
       UpperCamelCase__         =    0
       UpperCamelCase__         =    0
       UpperCamelCase__         =    {}

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       Union[str, Any]:
       if vertex not in self.adjacency:
           UpperCamelCase__         =    {}
           self.num_vertices += 1

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_      )		->       Optional[int]:
       self.add_vertex(snake_case_      )
       self.add_vertex(snake_case_      )

       if head == tail:
           return

       UpperCamelCase__         =    weight
       UpperCamelCase__         =    weight

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       str:
       UpperCamelCase__         =    self.get_edges()
       for edge in edges:
           UpperCamelCase__       ,						UpperCamelCase__       ,						UpperCamelCase__         =    edge
           edges.remove((tail, head, weight)      )
       for i in range(len(snake_case_      )      ):
           UpperCamelCase__         =    list(edges[i]      )

       edges.sort(key=lambda snake_case_      : e[2]      )
       for i in range(len(snake_case_      ) - 1      ):
           if edges[i][2] >= edges[i + 1][2]:
               UpperCamelCase__         =    edges[i][2] + 1
       for edge in edges:
           UpperCamelCase__       ,						UpperCamelCase__       ,						UpperCamelCase__         =    edge
           UpperCamelCase__         =    weight
           UpperCamelCase__         =    weight

   def __str__(					self      )		->       Tuple:
       UpperCamelCase__         =    ''
       for tail in self.adjacency:
           for head in self.adjacency[tail]:
               UpperCamelCase__         =    self.adjacency[head][tail]
               string += F'{head} -> {tail} == {weight}\n'
       return string.rstrip('\n'      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Optional[int]:
       UpperCamelCase__         =    []
       for tail in self.adjacency:
           for head in self.adjacency[tail]:
               output.append((tail, head, self.adjacency[head][tail])      )
       return output

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[str]:
       return self.adjacency.keys()

   @staticmethod
   def 						SCREAMING_SNAKE_CASE__ (					snake_case_=None ,				snake_case_=None      )		->       Union[str, Any]:
       UpperCamelCase__         =    Graph()
       if vertices is None:
           UpperCamelCase__         =    []
       if edges is None:
           UpperCamelCase__         =    []
       for vertex in vertices:
           g.add_vertex(snake_case_      )
       for edge in edges:
           g.add_edge(*snake_case_      )
       return g
   class    __lowerCamelCase    :

      def __init__(					self      )		->       str:
          UpperCamelCase__         =    {}
          UpperCamelCase__         =    {}

      def __len__(					self      )		->       int:
          return len(self.parent      )

      def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       int:
          if item in self.parent:
              return self.find(snake_case_      )

          UpperCamelCase__         =    item
          UpperCamelCase__         =    0
          return item

      def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       Optional[Any]:
          if item not in self.parent:
              return self.make_set(snake_case_      )
          if item != self.parent[item]:
              UpperCamelCase__         =    self.find(self.parent[item]      )
          return self.parent[item]







      def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       List[Any]:
          UpperCamelCase__         =    self.find(snake_case_      )
          UpperCamelCase__         =    self.find(snake_case_      )

          if roota == roota:
              return roota

          if self.rank[roota] > self.rank[roota]:
              UpperCamelCase__         =    roota
              return roota

          if self.rank[roota] < self.rank[roota]:
              UpperCamelCase__         =    roota
              return roota

          if self.rank[roota] == self.rank[roota]:
              self.rank[roota] += 1
              UpperCamelCase__         =    roota
              return roota
          return None







   @staticmethod
   def 						SCREAMING_SNAKE_CASE__ (					snake_case_      )		->       int:
       UpperCamelCase__         =    graph.num_vertices

       UpperCamelCase__         =    Graph.UnionFind()
       UpperCamelCase__         =    []
       while num_components > 1:
           UpperCamelCase__         =    {}
           for vertex in graph.get_vertices():
               UpperCamelCase__         =    -1

           UpperCamelCase__         =    graph.get_edges()
           for edge in edges:
               UpperCamelCase__       ,						UpperCamelCase__       ,						UpperCamelCase__         =    edge
               edges.remove((tail, head, weight)      )
           for edge in edges:
               UpperCamelCase__       ,						UpperCamelCase__       ,						UpperCamelCase__         =    edge
               UpperCamelCase__         =    union_find.find(snake_case_      )
               UpperCamelCase__         =    union_find.find(snake_case_      )
               if seta != seta:
                   if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
                       UpperCamelCase__         =    [head, tail, weight]

                   if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
                       UpperCamelCase__         =    [head, tail, weight]
           for vertex in cheap_edge:
               if cheap_edge[vertex] != -1:
                   UpperCamelCase__       ,						UpperCamelCase__       ,						UpperCamelCase__         =    cheap_edge[vertex]
                   if union_find.find(snake_case_      ) != union_find.find(snake_case_      ):
                       union_find.union(snake_case_ ,				snake_case_      )
                       mst_edges.append(cheap_edge[vertex]      )
                       UpperCamelCase__         =    num_components - 1
       UpperCamelCase__         =    Graph.build(edges=snake_case_      )
       return mst












"""simple docstring"""





from copy import deepcopy
class    __lowerCamelCase    :

   def __init__(					self ,				snake_case_ = None ,				snake_case_ = None      )		->       None:

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

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       None:
       UpperCamelCase__         =    len(snake_case_      )
       UpperCamelCase__         =    deepcopy(snake_case_      )
       for i in range(1 ,				self.size      ):
           UpperCamelCase__         =    self.next_(snake_case_      )
           if j < self.size:
               self.tree[j] += self.tree[i]

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       list[int]:
       UpperCamelCase__         =    self.tree[:]
       for i in range(self.size - 1 ,				0 ,				-1      ):
           UpperCamelCase__         =    self.next_(snake_case_      )
           if j < self.size:
               arr[j] -= arr[i]
       return arr

   @staticmethod
   def 						SCREAMING_SNAKE_CASE__ (					snake_case_      )		->       int:
       return index + (index & (-index))

   @staticmethod
   def 						SCREAMING_SNAKE_CASE__ (					snake_case_      )		->       int:
       return index - (index & (-index))

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       None:
       if index == 0:
           self.tree[0] += value
           return
       while index < self.size:
           self.tree[index] += value
           UpperCamelCase__         =    self.next_(snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       None:
       self.add(snake_case_ ,				value - self.get(snake_case_      )      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       int:
       if right == 0:
           return 0
       UpperCamelCase__         =    self.tree[0]
       right -= 1  # make right inclusive
       while right > 0:
           result += self.tree[right]
           UpperCamelCase__         =    self.prev(snake_case_      )
       return result

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       int:
       return self.prefix(snake_case_      ) - self.prefix(snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       int:
       return self.query(snake_case_ ,				index + 1      )







   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       int:
       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()




