"""simple docstring"""
SCREAMING_SNAKE_CASE__      						=  range(2, 20 + 1)
SCREAMING_SNAKE_CASE__      						=  [10**k for k in range(ks[-1] + 1)]
SCREAMING_SNAKE_CASE__      						=  {}





def    lowerCAmelCase__    (			_UpperCamelCase       :				List[str] ,			_UpperCamelCase       :				str ,			_UpperCamelCase       :				Union[str, Any] ,			_UpperCamelCase       :				Dict					)					->				Optional[Any]:





      """simple docstring"""






      snake_case								=			sum(a_i[j] for j in range(lowerCamelCase__ ,			len(lowerCamelCase__					)					)					)
      snake_case								=			sum(a_i[j] * base[j] for j in range(min(len(lowerCamelCase__					) ,			lowerCamelCase__					)					)					)

      snake_case					,snake_case								=			0, 0
      snake_case								=			n - i

      snake_case								=			memo.get(lowerCamelCase__					)

      if sub_memo is not None:
            snake_case								=			sub_memo.get(lowerCamelCase__					)

            if jumps is not None and len(lowerCamelCase__					) > 0:
                  # find and make the largest jump without going over
                  snake_case								=			-1
                  for _k in range(len(lowerCamelCase__					) - 1 ,			-1 ,			-1					):
                        if jumps[_k][2] <= k and jumps[_k][1] <= max_dn:
                              snake_case								=			_k
                              break

                  if max_jump >= 0:
                        snake_case					,snake_case					,snake_case								=			jumps[max_jump]
                        # since the difference between jumps is cached, add c
                        snake_case								=			diff + c
                        for j in range(min(lowerCamelCase__ ,			len(lowerCamelCase__					)					)					):
                              snake_case					,snake_case								=			divmod(lowerCamelCase__ ,			1_0					)
                        if new_c > 0:
                              add(lowerCamelCase__ ,			lowerCamelCase__ ,			lowerCamelCase__					)

            else:
                  snake_case								=			[]
      else:
            snake_case								=			{c: []}
            snake_case								=			sub_memo

      if dn >= max_dn or c + diff >= base[k]:
            return diff, dn

      if k > ks[0]:
            while True:
                  # keep doing smaller jumps
                  snake_case					,snake_case								=			next_term(lowerCamelCase__ ,			k - 1 ,			i + dn ,			lowerCamelCase__					)
                  diff += _diff
                  dn += terms_jumped

                  if dn >= max_dn or c + diff >= base[k]:
                        break
      else:
            # would be too small a jump, just compute sequential terms instead
            snake_case					,snake_case								=			compute(lowerCamelCase__ ,			lowerCamelCase__ ,			i + dn ,			lowerCamelCase__					)
            diff += _diff
            dn += terms_jumped

      snake_case								=			sub_memo[c]

      # keep jumps sorted by # of terms skipped
      snake_case								=			0
      while j < len(lowerCamelCase__					):
            if jumps[j][1] > dn:
                  break
            j += 1

      # cache the jump for this value digitsum(b) and c
      sub_memo[c].insert(lowerCamelCase__ ,			(diff, dn, k)					)
      return (diff, dn)





def    lowerCAmelCase__    (			_UpperCamelCase       :				Tuple ,			_UpperCamelCase       :				List[Any] ,			_UpperCamelCase       :				Optional[int] ,			_UpperCamelCase       :				str					)					->				List[str]:





      """simple docstring"""






      if i >= n:
            return 0, i
      if k > len(lowerCamelCase__					):
            a_i.extend([0 for _ in range(k - len(lowerCamelCase__					)					)]					)

      # note: a_i -> b * 10^k + c
      # ds_b -> digitsum(b)
      # ds_c -> digitsum(c)
      snake_case								=			i
      snake_case					,snake_case					,snake_case								=			0, 0, 0
      for j in range(len(lowerCamelCase__					)					):
            if j >= k:
                  ds_b += a_i[j]
            else:
                  ds_c += a_i[j]

      while i < n:
            i += 1
            snake_case								=			ds_c + ds_b
            diff += addend
            snake_case								=			0
            for j in range(lowerCamelCase__					):
                  snake_case								=			a_i[j] + addend
                  snake_case					,snake_case								=			divmod(lowerCamelCase__ ,			1_0					)

                  ds_c += a_i[j]

            if addend > 0:
                  break

      if addend > 0:
            add(lowerCamelCase__ ,			lowerCamelCase__ ,			lowerCamelCase__					)
      return diff, i - start_i





def    lowerCAmelCase__    (			_UpperCamelCase       :				List[str] ,			_UpperCamelCase       :				Union[str, Any] ,			_UpperCamelCase       :				int					)					->				int:





      """simple docstring"""






      for j in range(lowerCamelCase__ ,			len(lowerCamelCase__					)					):
            snake_case								=			digits[j] + addend
            if s >= 1_0:
                  snake_case					,snake_case								=			divmod(lowerCamelCase__ ,			1_0					)
                  snake_case								=			addend // 1_0 + quotient
            else:
                  snake_case								=			s
                  snake_case								=			addend // 1_0

            if addend == 0:
                  break

      while addend > 0:
            snake_case					,snake_case								=			divmod(lowerCamelCase__ ,			1_0					)
            digits.append(lowerCamelCase__					)





def    lowerCAmelCase__    (			_UpperCamelCase       :				int = 1_0**1_5					)					->				int:





      """simple docstring"""






      snake_case								=			[1]
      snake_case								=			1
      snake_case								=			0
      while True:
            snake_case					,snake_case								=			next_term(lowerCamelCase__ ,			2_0 ,			i + dn ,			lowerCamelCase__					)
            dn += terms_jumped
            if dn == n - i:
                  break

      snake_case								=			0
      for j in range(len(lowerCamelCase__					)					):
            a_n += digits[j] * 1_0**j
      return a_n


if __name__ == "__main__":
     print(f"""{solution() = }""")



"""simple docstring"""
class   lowerCAmelCase_    (			lowerCAmelCase					):



				"""simple docstring"""
				pass





class   lowerCAmelCase_    (			lowerCAmelCase					):



				"""simple docstring"""
				pass





class   lowerCAmelCase_    :



				"""simple docstring"""

				def __init__(				self    ):






										"""simple docstring"""

										snake_case								=			[
										    [],
										    [],
										    [],
										]

				def 		snake_case (				self		,    lowerCAmelCase		,    lowerCAmelCase    ):






										"""simple docstring"""

										try:
																if len(self.queues[priority]    ) >= 1_00:
																						raise OverflowError('Maximum queue size is 100'    )
																self.queues[priority].append(lowerCAmelCase    )
										except IndexError:
																raise ValueError('Valid priorities are 0, 1, and 2'    )

				def 		snake_case (				self    ):






										"""simple docstring"""

										for queue in self.queues:
																if queue:
																						return queue.pop(0    )
										raise UnderFlowError('All queues are empty'    )

				def __str__(				self    ):






										"""simple docstring"""

										return "\n".join(F"""Priority {i}: {q}""" for i, q in enumerate(self.queues    )    )





class   lowerCAmelCase_    :



				"""simple docstring"""

				def __init__(				self    ):






										"""simple docstring"""

										snake_case								=			[]

				def 		snake_case (				self		,    lowerCAmelCase    ):






										"""simple docstring"""

										if len(self.queue    ) == 1_00:
																raise OverFlowError('Maximum queue size is 100'    )
										self.queue.append(lowerCAmelCase    )

				def 		snake_case (				self    ):






										"""simple docstring"""

										if not self.queue:
																raise UnderFlowError('The queue is empty'    )
										else:
																snake_case								=			min(self.queue    )
																self.queue.remove(lowerCAmelCase    )
																return data

				def __str__(				self    ):






										"""simple docstring"""

										return str(self.queue    )





def    lowerCAmelCase__    (			)					->				int:





						"""simple docstring"""






						snake_case								=			FixedPriorityQueue()
						fpq.enqueue(0 ,			1_0					)
						fpq.enqueue(1 ,			7_0					)
						fpq.enqueue(0 ,			1_0_0					)
						fpq.enqueue(2 ,			1					)
						fpq.enqueue(2 ,			5					)
						fpq.enqueue(1 ,			7					)
						fpq.enqueue(2 ,			4					)
						fpq.enqueue(1 ,			6_4					)
						fpq.enqueue(0 ,			1_2_8					)
						print(_UpperCamelCase					)
						print(fpq.dequeue()					)
						print(fpq.dequeue()					)
						print(fpq.dequeue()					)
						print(fpq.dequeue()					)
						print(fpq.dequeue()					)
						print(_UpperCamelCase					)
						print(fpq.dequeue()					)
						print(fpq.dequeue()					)
						print(fpq.dequeue()					)
						print(fpq.dequeue()					)
						print(fpq.dequeue()					)





def    lowerCAmelCase__    (			)					->				List[str]:





						"""simple docstring"""






						snake_case								=			ElementPriorityQueue()
						epq.enqueue(1_0					)
						epq.enqueue(7_0					)
						epq.enqueue(1_0_0					)
						epq.enqueue(1					)
						epq.enqueue(5					)
						epq.enqueue(7					)
						epq.enqueue(4					)
						epq.enqueue(6_4					)
						epq.enqueue(1_2_8					)
						print(_UpperCamelCase					)
						print(epq.dequeue()					)
						print(epq.dequeue()					)
						print(epq.dequeue()					)
						print(epq.dequeue()					)
						print(epq.dequeue()					)
						print(_UpperCamelCase					)
						print(epq.dequeue()					)
						print(epq.dequeue()					)
						print(epq.dequeue()					)
						print(epq.dequeue()					)
						print(epq.dequeue()					)


if __name__ == "__main__":
					fixed_priority_queue()
					element_priority_queue()


