





'''simple docstring'''


import operator as op


_SCREAMING_SNAKE_CASE	 =							"scaler.pt"
_SCREAMING_SNAKE_CASE	 =							"pytorch_model"
_SCREAMING_SNAKE_CASE	 =							"random_states"
_SCREAMING_SNAKE_CASE	 =							"optimizer"
_SCREAMING_SNAKE_CASE	 =							"scheduler"
_SCREAMING_SNAKE_CASE	 =							"pytorch_model.bin"
_SCREAMING_SNAKE_CASE	 =							"pytorch_model.bin.index.json"
_SCREAMING_SNAKE_CASE	 =							"model.safetensors"
_SCREAMING_SNAKE_CASE	 =							"model.safetensors.index.json"
_SCREAMING_SNAKE_CASE	 =							"1.10.2"
_SCREAMING_SNAKE_CASE	 =							"py38"
_SCREAMING_SNAKE_CASE	 =							"4.17.0"
_SCREAMING_SNAKE_CASE	 =							["ml.p3.16xlarge", "ml.p3dn.24xlarge", "ml.p4dn.24xlarge"]
_SCREAMING_SNAKE_CASE	 =							["FULL_SHARD", "SHARD_GRAD_OP", "NO_SHARD", "HYBRID_SHARD", "HYBRID_SHARD_ZERO2"]
_SCREAMING_SNAKE_CASE	 =							["TRANSFORMER_BASED_WRAP", "SIZE_BASED_WRAP", "NO_WRAP"]
_SCREAMING_SNAKE_CASE	 =							["BACKWARD_PRE", "BACKWARD_POST", "NO_PREFETCH"]
_SCREAMING_SNAKE_CASE	 =							["FULL_STATE_DICT", "LOCAL_STATE_DICT", "SHARDED_STATE_DICT"]
_SCREAMING_SNAKE_CASE	 =							"2.0.1"
_SCREAMING_SNAKE_CASE	 =							["pdsh", "standard", "openmpi", "mvapich"]
_SCREAMING_SNAKE_CASE	 =							["default", "reduce-overhead", "max-autotune"]

_SCREAMING_SNAKE_CASE	 =							{">": op.gt, ">=": op.ge, "==": op.eq, "!=": op.ne, "<=": op.le, "<": op.lt}

# These are the args for `torch.distributed.launch` for pytorch < 1.9
_SCREAMING_SNAKE_CASE	 =							[
    "nnodes",
    "nproc_per_node",
    "rdzv_backend",
    "rdzv_endpoint",
    "rdzv_id",
    "rdzv_conf",
    "standalone",
    "max_restarts",
    "monitor_interval",
    "start_method",
    "role",
    "module",
    "m",
    "no_python",
    "run_path",
    "log_dir",
    "r",
    "redirects",
    "t",
    "tee",
    "node_rank",
    "master_addr",
    "master_port",
]

_SCREAMING_SNAKE_CASE	 =							["DEEPSPEED", "MULTI_GPU", "FSDP", "MEGATRON_LM"]
_SCREAMING_SNAKE_CASE	 =							["DEEPSPEED", "MULTI_XPU", "FSDP"]









'''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 	__a(SCREAMING_SNAKE_CASE_  :					Tuple		,       SCREAMING_SNAKE_CASE_  :					str		,       SCREAMING_SNAKE_CASE_  :					Any		,       SCREAMING_SNAKE_CASE_  :					List[str]    ):



    '''simple docstring'''





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

    _lowerCAmelCase			,			_lowerCAmelCase				=      0, 0
    _lowerCAmelCase				=      n - i

    _lowerCAmelCase				=      memo.get(SCREAMING_SNAKE_CASE_    )

    if sub_memo is not None:
        _lowerCAmelCase				=      sub_memo.get(SCREAMING_SNAKE_CASE_    )

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

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

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

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

    if k > ks[0]:
        while True:
            # keep doing smaller jumps
            _lowerCAmelCase			,			_lowerCAmelCase				=      next_term(SCREAMING_SNAKE_CASE_		,       k - 1		,       i + dn		,       SCREAMING_SNAKE_CASE_    )
            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
        _lowerCAmelCase			,			_lowerCAmelCase				=      compute(SCREAMING_SNAKE_CASE_		,       SCREAMING_SNAKE_CASE_		,       i + dn		,       SCREAMING_SNAKE_CASE_    )
        diff += _diff
        dn += terms_jumped

    _lowerCAmelCase				=      sub_memo[c]

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

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


def 	__a(SCREAMING_SNAKE_CASE_  :					Dict		,       SCREAMING_SNAKE_CASE_  :					int		,       SCREAMING_SNAKE_CASE_  :					Dict		,       SCREAMING_SNAKE_CASE_  :					Union[str, Any]    ):



    '''simple docstring'''





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

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

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

            ds_c += a_i[j]

        if addend > 0:
            break

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


def 	__a(SCREAMING_SNAKE_CASE_  :					List[Any]		,       SCREAMING_SNAKE_CASE_  :					int		,       SCREAMING_SNAKE_CASE_  :					Any    ):



    '''simple docstring'''





    for j in range(SCREAMING_SNAKE_CASE_		,       len(SCREAMING_SNAKE_CASE_    )    ):
        _lowerCAmelCase				=      digits[j] + addend
        if s >= 10:
            _lowerCAmelCase			,			_lowerCAmelCase				=      divmod(SCREAMING_SNAKE_CASE_		,       10    )
            _lowerCAmelCase				=      addend // 10 + quotient
        else:
            _lowerCAmelCase				=      s
            _lowerCAmelCase				=      addend // 10

        if addend == 0:
            break

    while addend > 0:
        _lowerCAmelCase			,			_lowerCAmelCase				=      divmod(SCREAMING_SNAKE_CASE_		,       10    )
        digits.append(SCREAMING_SNAKE_CASE_    )


def 	__a(SCREAMING_SNAKE_CASE_  :					int = 10**15    ):



    '''simple docstring'''





    _lowerCAmelCase				=      [1]
    _lowerCAmelCase				=      1
    _lowerCAmelCase				=      0
    while True:
        _lowerCAmelCase			,			_lowerCAmelCase				=      next_term(SCREAMING_SNAKE_CASE_		,       20		,       i + dn		,       SCREAMING_SNAKE_CASE_    )
        dn += terms_jumped
        if dn == n - i:
            break

    _lowerCAmelCase				=      0
    for j in range(len(SCREAMING_SNAKE_CASE_    )    ):
        a_n += digits[j] * 10**j
    return a_n


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


