





'''simple docstring'''


import doctest
from collections import deque

import numpy as np

class    lowerCAmelCase_		:




 def __init__(	self		)    ->							None:
     _lowerCAmelCase				=      [2, 1, 2, -1]
     _lowerCAmelCase				=      [1, 2, 3, 4]





 def 							_snake_case   (	self		)    ->							list[float]:
     _lowerCAmelCase				=      len(self.first_signal		)
     _lowerCAmelCase				=      len(self.second_signal		)

     _lowerCAmelCase				=      max(_lowerCAmelCase			,     _lowerCAmelCase		)

     # create a zero matrix of max_length x max_length
     _lowerCAmelCase				=      [[0] * max_length for i in range(_lowerCAmelCase		)]

     # fills the smaller signal with zeros to make both signals of same length
     if length_first_signal < length_second_signal:
         self.first_signal += [0] * (max_length - length_first_signal)
     elif length_first_signal > length_second_signal:
         self.second_signal += [0] * (max_length - length_second_signal)
     for i in range(_lowerCAmelCase		):
         _lowerCAmelCase				=      deque(self.second_signal		)
         rotated_signal.rotate(_lowerCAmelCase		)
         for j, item in enumerate(_lowerCAmelCase		):
             matrix[i][j] += item

        # multiply the matrix with the first signal
     _lowerCAmelCase				=      np.matmul(np.transpose(_lowerCAmelCase		)			,     np.transpose(self.first_signal		)		)

     # rounding-off to two decimal places
     return [round(_lowerCAmelCase			,     2		) for i in final_signal]


if __name__ == "__main__":
       doctest.testmod()









'''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() = }''')


